Predicting percolation thresholds in networks

Heterogeneous K-core percolation on hypergraphs

In complex systems, there are pairwise and multiple interactions among elements, which can be described as hypergraphs. K-core percolation is widely utilized in the investigation of the robustness of systems subject to random or targeted attacks. However, the robustness of nodes usually correlates with their characteristics, such as degree, and exhibits heterogeneity while lacking a theoretical study on the K-core percolation on a hypergraph. To this end, we constructed a hyperedge K-core percolation model that introduces heterogeneity parameters to divide the active hyperedges into two parts, where hyperedges are inactive unless they have a certain number of active nodes. In the stage of pruning process, when the number of active nodes contained in a hyperedge is less than its set value, it will be pruned, which will result in the deletion of other hyperedges and ultimately trigger cascading failures. We studied the magnitude of the giant connected component and the percolation threshold of the model by mapping a random hypergraph to a factor graph. Subsequently, we conducted a large number of simulation experiments, and the theoretical values matched well with the simulated values. The heterogeneity parameters of the proposed model have a significant impact on the magnitude of the giant connected component and the type of phase transition in the network. We found that decreasing the value of heterogeneity parameters renders the network more fragile, while increasing the value of heterogeneity parameters makes it more resilient under random attacks. Meanwhile, as the heterogeneity parameter decreases to 0, it may cause a change in the nature of network phase transition, and the network shows a hybrid transition.

Heterogeneous message passing for heterogeneous networks

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

Influence maximization: Divide and conquer

The problem of influence maximization, i.e., finding the set of nodes having maximal influence on a network, is of great importance for several applications. In the past two decades, many heuristic metrics to spot influencers have been proposed. Here, we introduce a framework to boost the performance of such metrics. The framework consists in dividing the network into sectors of influence, and then selecting the most influential nodes within these sectors. We explore three different methodologies to find sectors in a network: graph partitioning, graph hyperbolic embedding, and community structure. The framework is validated with a systematic analysis of real and synthetic networks. We show that the gain in performance generated by dividing a network into sectors before selecting the influential spreaders increases as the modularity and heterogeneity of the network increase. Also, we show that the division of the network into sectors can be efficiently performed in a time that scales linearly with the network size, thus making the framework applicable to large-scale influence maximization problems.

A sampling-guided unsupervised learning method to capture percolation in complex networks

The use of machine learning methods in classical and quantum systems has led to novel techniques to classify ordered and disordered phases, as well as uncover transition points in critical phenomena. Efforts to extend these methods to dynamical processes in complex networks is a field of active research. Network-percolation, a measure of resilience and robustness to structural failures, as well as a proxy for spreading processes, has numerous applications in social, technological, and infrastructural systems. A particular challenge is to identify the existence of a percolation cluster in a network in the face of noisy data. Here, we consider bond-percolation, and introduce a sampling approach that leverages the core-periphery structure of such networks at a microscopic scale, using onion decomposition, a refined version of the k-core. By selecting subsets of nodes in a particular layer of the onion spectrum that follow similar trajectories in the percolation process, percolating phases can be distinguished from non-percolating ones through an unsupervised clustering method. Accuracy in the initial step is essential for extracting samples with information-rich content, that are subsequently used to predict the critical transition point through the confusion scheme, a recently introduced learning method. The method circumvents the difficulty of missing data or noisy measurements, as it allows for sampling nodes from both the core and periphery, as well as intermediate layers. We validate the effectiveness of our sampling strategy on a spectrum of synthetic network topologies, as well as on two real-word case studies: the integration time of the US domestic airport network, and the identification of the epidemic cluster of COVID-19 outbreaks in three major US states. The method proposed here allows for identifying phase transitions in empirical time-varying networks.

Permeability of polydisperse solid foams

The effect of polydispersity on foam permeability is investigated by numerical simulations. Foam structures are first generated by Laguerre tessellations via the Neper software and relaxed to minimize the surface energy via the Surface Evolver software. The fluid flow and permeability are then calculated by means of pore-network simulations, by considering either fully open-cell foams or foams with randomly selected closed windows. Different configurations of window aperture are used, including identical window aperture size, identical window aperture ratio, or random window aperture ratio. The main results are obtained for the case of foams having identical and uniform window aperture ratios. For such foams and at constant mean pore size, foam permeability is found to strongly increase with the polydispersity degree. The numerical results are employed to discuss the validity of the mean pressure field assumption used to calculate the foam permeability, the effect of small pores, and the definition of an equivalent Kelvin foam size. We show that as long as the fluctuations of the window aperture ratio remain low, foam permeability can be estimated by using the mean pressure field hypothesis. The weak effect of small pores on permeability is related to their small contribution to the overall fluid volume fraction. Finally, various estimations of the equivalent Kelvin foam size based on pore-size distribution are proposed.

Approximating nonbacktracking centrality and localization phenomena in large networks

Message-passing theories have proved to be invaluable tools in studying percolation, nonrecurrent epidemics, and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix, whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighboring nodes. Our findings suggest that in most networks, degree-degree correlations beyond nearest neighbor are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is, when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

The localization of non-backtracking centrality in networks and its physical consequences

The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculate the largest eigenvalue of the non-backtracking matrix and the associated non-backtracking centrality for uncorrelated random networks, finding expressions in excellent agreement with numerical results. We show however that the same formulas do not work well for many real-world networks. We identify the mechanism responsible for this violation in the localization of the non-backtracking centrality on network subgraphs whose formation is highly unlikely in uncorrelated networks, but rather common in real-world structures. Exploiting this knowledge we present an heuristic generalized formula for the largest eigenvalue, which is remarkably accurate for all networks of a large empirical dataset. We show that this newly uncovered localization phenomenon allows to understand the failure of the message-passing prediction for the percolation threshold in many real-world structures.

High prevalence regimes in the pair-quenched mean-field theory for the susceptible-infected-susceptible model on networks

Reckoning of pairwise dynamical correlations significantly improves the accuracy of mean-field theories and plays an important role in the investigation of dynamical processes in complex networks. In this work, we perform a nonperturbative numerical analysis of the quenched mean-field theory (QMF) and the inclusion of dynamical correlations by means of the pair quenched mean-field (PQMF) theory for the susceptible-infected-susceptible model on synthetic and real networks. We show that the PQMF considerably outperforms the standard QMF theory on synthetic networks of distinct levels of heterogeneity and degree correlations, providing extremely accurate predictions when the system is not too close to the epidemic threshold, while the QMF theory deviates substantially from simulations for networks with a degree exponent γ>2.5. The scenario for real networks is more complicated, still with PQMF significantly outperforming the QMF theory. However, despite its high accuracy for most investigated networks, in a few cases PQMF deviations from simulations are not negligible. We found correlations between accuracy and average shortest path, while other basic network metrics seem to be uncorrelated with the theory accuracy. Our results show the viability of the PQMF theory to investigate the high-prevalence regimes of recurrent-state epidemic processes in networks, a regime of high applicability.

Influencer identification in dynamical complex systems

The integrity and functionality of many real-world complex systems hinge on a small set of pivotal nodes, or influencers. In different contexts, these influencers are defined as either structurally important nodes that maintain the connectivity of networks, or dynamically crucial units that can disproportionately impact certain dynamical processes. In practice, identification of the optimal set of influencers in a given system has profound implications in a variety of disciplines. In this review, we survey recent advances in the study of influencer identification developed from different perspectives, and present state-of-the-art solutions designed for different objectives. In particular, we first discuss the problem of finding the minimal number of nodes whose removal would breakdown the network (i.e. the optimal percolation or network dismantle problem), and then survey methods to locate the essential nodes that are capable of shaping global dynamics with either continuous (e.g. independent cascading models) or discontinuous phase transitions (e.g. threshold models). We conclude the review with a summary and an outlook.

Systematic comparison between methods for the detection of influential spreaders in complex networks

Influence maximization is the problem of finding the set of nodes of a network that maximizes the size of the outbreak of a spreading process occurring on the network. Solutions to this problem are important for strategic decisions in marketing and political campaigns. The typical setting consists in the identification of small sets of initial spreaders in very large networks. This setting makes the optimization problem computationally infeasible for standard greedy optimization algorithms that account simultaneously for information about network topology and spreading dynamics, leaving space only to heuristic methods based on the drastic approximation of relying on the geometry of the network alone. The literature on the subject is plenty of purely topological methods for the identification of influential spreaders in networks. However, it is unclear how far these methods are from being optimal. Here, we perform a systematic test of the performance of a multitude of heuristic methods for the identification of influential spreaders. We quantify the performance of the various methods on a corpus of 100 real-world networks; the corpus consists of networks small enough for the application of greedy optimization so that results from this algorithm are used as the baseline needed for the analysis of the performance of the other methods on the same corpus of networks. We find that relatively simple network metrics, such as adaptive degree or closeness centralities, are able to achieve performances very close to the baseline value, thus providing good support for the use of these metrics in large-scale problem settings. Also, we show that a further 2–5% improvement towards the baseline performance is achievable by hybrid algorithms that combine two or more topological metrics together. This final result is validated on a small collection of large graphs where greedy optimization is not applicable.

Spectral properties and the accuracy of mean-field approaches for epidemics on correlated power-law networks

We present a comparison between stochastic simulations and mean-field theories for the epidemic threshold of the susceptible-infected-susceptible model on correlated networks (both assortative and disassortative) with a power-law degree distribution P(k)∼k−γ. We confirm the vanishing of the threshold regardless of the correlation pattern and the degree exponent γ. Thresholds determined numerically are compared with quenched mean-field (QMF) and pair quenched mean-field (PQMF) theories. Correlations do not change the overall picture: The QMF and PQMF theories provide estimates that are asymptotically correct for large sizes for γ<5/2, while they only capture the vanishing of the threshold for γ>5/2, failing to reproduce quantitatively how this occurs. For a given size, PQMF theory is more accurate. We relate the variations in the accuracy of QMF and PQMF predictions with changes in the spectral properties (spectral gap and localization) of standard and modified adjacency matrices, which rule the epidemic prevalence near the transition point, depending on the theoretical framework. We also show that, for γ<5/2, while QMF theory provides an estimate of the epidemic threshold that is asymptotically exact, it fails to reproduce the singularity of the prevalence around the transition.

Multiple phase transitions in networks of directed networks

The robustness in real-world complex systems with dependency connectivities differs from that in isolated networks. Although most complex network research has focused on interdependent undirected systems, many real-world networks-such as gene regulatory networks and traffic networks-are directed. We thus develop an analytical framework for examining the robustness of networks made up of directed networks of differing topologies. We use it to predict the phase transitions that occur during node failures and to generate the phase diagrams of a number of different systems, including treelike and random regular (RR) networks of directed Erdős-Rényi (ER) networks and scale-free networks. We find that the the phase transition and phase diagram of networks of directed networks differ from those of networks of undirected networks. For example, the RR networks of directed ER networks show a hybrid phase transition that does not occur in networks of undirected ER networks. In addition, system robustness is affected by network topology in networks of directed networks. As coupling strength q increases, treelike networks of directed ER networks change from a second-order phase transition to a first-order phase transition, and RR networks of directed ER networks change from a second-order phase transition to a hybrid phase transition, then to a first-order phase transition, and finally to a region of collapse. We also find that heterogenous network systems are more robust than homogeneous network systems. We note that there are multiple phase transitions and triple points in the phase diagram of RR networks of directed networks and this helps us understand how to increase network robustness when designing interdependent infrastructure systems.

Relevance of backtracking paths in recurrent-state epidemic spreading on networks

The understanding of epidemics on networks has greatly benefited from the recent application of message-passing approaches, which allow us to derive exact results for irreversible spreading (i.e., diseases with permanent acquired immunity) in locally treelike topologies. This success has suggested the application of the same approach to recurrent-state epidemics, for which an individual can contract the epidemic and recover repeatedly. The underlying assumption is that backtracking paths (i.e., an individual is reinfected by a neighbor he or she previously infected) do not play a relevant role. In this paper we show that this is not the case for recurrent-state epidemics since the neglect of backtracking paths leads to a formula for the epidemic threshold that is qualitatively incorrect in the large size limit. Moreover, we define a modified recurrent-state dynamics which explicitly forbids direct backtracking events and show that this modification completely upsets the phenomenology.

Generalized Erdős numbers for network analysis

The identification of relationships in complex networks is critical in a variety of scientific contexts. This includes the identification of globally central nodes and analysing the importance of pairwise relationships between nodes. In this paper, we consider the concept of topological proximity (or 'closeness') between nodes in a weighted network using the generalized Erdős numbers (GENs). This measure satisfies a number of desirable properties for networks with nodes that share a finite resource. These include: (i) real-valuedness, (ii) non-locality and (iii) asymmetry. We show that they can be used to define a personalized measure of the importance of nodes in a network with a natural interpretation that leads to new methods to measure centrality. We show that the square of the leading eigenvector of an importance matrix defined using the GENs is strongly correlated with well-known measures such as PageRank, and define a personalized measure of centrality that is also well correlated with other existing measures. The utility of this measure of topological proximity is demonstrated by showing the asymmetries in both the dynamics of random walks and the mean infection time in epidemic spreading are better predicted by the topological definition of closeness provided by the GENs than they are by other measures.

NETWORK-ENSEMBLE COMPARISONS WITH STOCHASTIC REWIRING AND VON NEUMANN ENTROPY

Assessing whether a given network is typical or atypical for a random-network ensemble (i.e., network-ensemble comparison) has widespread applications ranging from null-model selection and hypothesis testing to clustering and classifying networks. We develop a framework for network-ensemble comparison by subjecting the network to stochastic rewiring. We study two rewiring processes-uniform and degree-preserved rewiring-which yield random-network ensembles that converge to the Erdős-Rényi and configuration-model ensembles, respectively. We study convergence through von Neumann entropy (VNE)-a network summary statistic measuring information content based on the spectra of a Laplacian matrix-and develop a perturbation analysis for the expected effect of rewiring on VNE. Our analysis yields an estimate for how many rewires are required for a given network to resemble a typical network from an ensemble, offering a computationally efficient quantity for network-ensemble comparison that does not require simulation of the corresponding rewiring process.

The interdependent network of gene regulation and metabolism is robust where it needs to be

Despite being highly interdependent, the major biochemical networks of the living cell-the networks of interacting genes and of metabolic reactions, respectively-have been approached mostly as separate systems so far. Recently, a framework for interdependent networks has emerged in the context of statistical physics. In a first quantitative application of this framework to systems biology, here we study the interdependent network of gene regulation and metabolism for the model organism Escherichia coli in terms of a biologically motivated percolation model. Particularly, we approach the system's conflicting tasks of reacting rapidly to (internal and external) perturbations, while being robust to minor environmental fluctuations. Considering its response to perturbations that are localized with respect to functional criteria, we find the interdependent system to be sensitive to gene regulatory and protein-level perturbations, yet robust against metabolic changes. We expect this approach to be applicable to a range of other interdependent networks.Although networks of interacting genes and metabolic reactions are interdependent, they have largely been treated as separate systems. Here the authors apply a statistical framework for interdependent networks to E. coli, and show that it is sensitive to gene and protein perturbations but robust against metabolic changes.

Quantification of network structural dissimilarities

Identifying and quantifying dissimilarities among graphs is a fundamental and challenging problem of practical importance in many fields of science. Current methods of network comparison are limited to extract only partial information or are computationally very demanding. Here we propose an efficient and precise measure for network comparison, which is based on quantifying differences among distance probability distributions extracted from the networks. Extensive experiments on synthetic and real-world networks show that this measure returns non-zero values only when the graphs are non-isomorphic. Most importantly, the measure proposed here can identify and quantify structural topological differences that have a practical impact on the information flow through the network, such as the presence or absence of critical links that connect or disconnect connected components.

Identifying and quantifying dissimilarities among graphs is a problem of practical importance, but current approaches are either limited or computationally demanding. Here, the authors propose an efficiently computable measure for network comparison that can identify structural topological differences.

Percolation in real multiplex networks

We present an exact mathematical framework able to describe site-percolation transitions in real multiplex networks. Specifically, we consider the average percolation diagram valid over an infinite number of random configurations where nodes are present in the system with given probability. The approach relies on the locally treelike ansatz, so that it is expected to accurately reproduce the true percolation diagram of sparse multiplex networks with negligible number of short loops. The performance of our theory is tested in social, biological, and transportation multiplex graphs. When compared against previously introduced methods, we observe improvements in the prediction of the percolation diagrams in all networks analyzed. Results from our method confirm previous claims about the robustness of real multiplex networks, in the sense that the average connectedness of the system does not exhibit any significant abrupt change as its individual components are randomly destroyed.

Observability transition in real networks

We consider the observability model in networks with arbitrary topologies. We introduce a system of coupled nonlinear equations, valid under the locally treelike ansatz, to describe the size of the largest observable cluster as a function of the fraction of directly observable nodes present in the network. We perform a systematic analysis on 95 real-world graphs and compare our theoretical predictions with numerical simulations of the observability model. Our method provides almost perfect predictions in the majority of the cases, even for networks with very large values of the clustering coefficient. Potential applications of our theory include the development of efficient and scalable algorithms for real-time surveillance of social networks, and monitoring of technological networks.

Complexity and robustness in hypernetwork models of metabolism

Metabolic reaction data is commonly modelled using a complex network approach, whereby nodes represent the chemical species present within the organism of interest, and connections are formed between those nodes participating in the same chemical reaction. Unfortunately, such an approach provides an inadequate description of the metabolic process in general, as a typical chemical reaction will involve more than two nodes, thus risking oversimplification of the system of interest in a potentially significant way. In this paper, we employ a complex hypernetwork formalism to investigate the robustness of bacterial metabolic hypernetworks by extending the concept of a percolation process to hypernetworks. Importantly, this provides a novel method for determining the robustness of these systems and thus for quantifying their resilience to random attacks/errors. Moreover, we performed a site percolation analysis on a large cohort of bacterial metabolic networks and found that hypernetworks that evolved in more variable environments displayed increased levels of robustness and topological complexity.

Predicting the epidemic threshold of the susceptible-infected-recovered model

Researchers have developed several theoretical methods for predicting epidemic thresholds, including the mean-field like (MFL) method, the quenched mean-field (QMF) method, and the dynamical message passing (DMP) method. When these methods are applied to predict epidemic threshold they often produce differing results and their relative levels of accuracy are still unknown. We systematically analyze these two issues-relationships among differing results and levels of accuracy-by studying the susceptible-infected-recovered (SIR) model on uncorrelated configuration networks and a group of 56 real-world networks. In uncorrelated configuration networks the MFL and DMP methods yield identical predictions that are larger and more accurate than the prediction generated by the QMF method. As for the 56 real-world networks, the epidemic threshold obtained by the DMP method is more likely to reach the accurate epidemic threshold because it incorporates full network topology information and some dynamical correlations. We find that in most of the networks with positive degree-degree correlations, an eigenvector localized on the high k-core nodes, or a high level of clustering, the epidemic threshold predicted by the MFL method, which uses the degree distribution as the only input information, performs better than the other two methods.

The robustness of multiplex networks under layer node-based attack

From transportation networks to complex infrastructures, and to social and economic networks, a large variety of systems can be described in terms of multiplex networks formed by a set of nodes interacting through different network layers. Network robustness, as one of the most successful application areas of complex networks, has attracted great interest in a myriad of research realms. In this regard, how multiplex networks respond to potential attack is still an open issue. Here we study the robustness of multiplex networks under layer node-based random or targeted attack, which means that nodes just suffer attacks in a given layer yet no additional influence to their connections beyond this layer. A theoretical analysis framework is proposed to calculate the critical threshold and the size of giant component of multiplex networks when nodes are removed randomly or intentionally. Via numerous simulations, it is unveiled that the theoretical method can accurately predict the threshold and the size of giant component, irrespective of attack strategies. Moreover, we also compare the robustness of multiplex networks under multiplex node-based attack and layer node-based attack, and find that layer node-based attack makes multiplex networks more vulnerable, regardless of average degree and underlying topology.

Beyond the locally treelike approximation for percolation on real networks

Theoretical attempts proposed so far to describe ordinary percolation processes on real-world networks rely on the locally treelike ansatz. Such an approximation, however, holds only to a limited extent, because real graphs are often characterized by high frequencies of short loops. We present here a theoretical framework able to overcome such a limitation for the case of site percolation. Our method is based on a message passing algorithm that discounts redundant paths along triangles in the graph. We systematically test the approach on 98 real-world graphs and on synthetic networks. We find excellent accuracy in the prediction of the whole percolation diagram, with significant improvement with respect to the prediction obtained under the locally treelike approximation. Residual discrepancies between theory and simulations do not depend on clustering and can be attributed to the presence of loops longer than three edges. We present also a method to account for clustering in bond percolation, but the improvement with respect to the method based on the treelike approximation is much less apparent.

Breaking of the site-bond percolation universality in networks

The stochastic addition of either vertices or connections in a network leads to the observation of the percolation transition, a structural change with the appearance of a connected component encompassing a finite fraction of the system. Percolation has always been regarded as a substrate-dependent but model-independent process, in the sense that the critical exponents of the transition are determined by the geometry of the system, but they are identical for the bond and site percolation models. Here, we report a violation of such assumption. We provide analytical and numerical evidence of a difference in the values of the critical exponents between the bond and site percolation models in networks with null percolation thresholds, such as scale-free graphs with diverging second moment of the degree distribution. We discuss possible implications of our results in real networks, and provide additional insights on the anomalous nature of the percolation transition with null threshold.

The percolation transition has been regarded as model-independent, namely determined by the geometry of a system but otherwise identical for bond or site percolation models. Here, the authors show the violation of this assumption both analytically and numerically for networks with null percolation thresholds.

Abnormal Behavior in Cascading Dynamics with Node Weight

Considering a preferential selection mechanism of load destination, we introduce a new method to quantify initial load distribution and subsequently construct a simple cascading model. By attacking the node with the highest load, we investigate the cascading dynamics in some synthetic networks. Surprisingly, we observe that for several networks of different structural patterns, a counterintuitive phenomenon emerges if the highest load attack is applied to the system, i.e., investing more resources to protect every node in a network inversely makes the whole network more vulnerable. We explain this ability paradox by analyzing the micro-structural components of the underlying network and therefore reveals how specific structural patterns may influence the cascading dynamics. We discover that the robustness of the network oscillates as the capacity of each node increases. The conclusion of the paper may shed lights on future investigations to avoid the demonstrated ability paradox and subsequent cascading failures in real-world networks.

Predicting the Lifetime of Dynamic Networks Experiencing Persistent Random Attacks

Estimating the critical points at which complex systems abruptly flip from one state to another is one of the remaining challenges in network science. Due to lack of knowledge about the underlying stochastic processes controlling critical transitions, it is widely considered difficult to determine the location of critical points for real-world networks, and it is even more difficult to predict the time at which these potentially catastrophic failures occur. We analyse a class of decaying dynamic networks experiencing persistent failures in which the magnitude of the overall failure is quantified by the probability that a potentially permanent internal failure will occur. When the fraction of active neighbours is reduced to a critical threshold, cascading failures can trigger a total network failure. For this class of network we find that the time to network failure, which is equivalent to network lifetime, is inversely dependent upon the magnitude of the failure and logarithmically dependent on the threshold. We analyse how permanent failures affect network robustness using network lifetime as a measure. These findings provide new methodological insight into system dynamics and, in particular, of the dynamic processes of networks. We illustrate the network model by selected examples from biology, and social science.

Influence maximization in complex networks through optimal percolation

The whole frame of interconnections in complex networks hinges on a specific set of structural nodes, much smaller than the total size, which, if activated, would cause the spread of information to the whole network, or, if immunized, would prevent the diffusion of a large scale epidemic. Localizing this optimal, that is, minimal, set of structural nodes, called influencers, is one of the most important problems in network science. Despite the vast use of heuristic strategies to identify influential spreaders, the problem remains unsolved. Here we map the problem onto optimal percolation in random networks to identify the minimal set of influencers, which arises by minimizing the energy of a many-body system, where the form of the interactions is fixed by the non-backtracking matrix of the network. Big data analyses reveal that the set of optimal influencers is much smaller than the one predicted by previous heuristic centralities. Remarkably, a large number of previously neglected weakly connected nodes emerges among the optimal influencers. These are topologically tagged as low-degree nodes surrounded by hierarchical coronas of hubs, and are uncovered only through the optimal collective interplay of all the influencers in the network. The present theoretical framework may hold a larger degree of universality, being applicable to other hard optimization problems exhibiting a continuous transition from a known phase.