Beyond the locally treelike approximation for percolation on real networks

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.

The interplay between disease spreading and awareness diffusion in multiplex networks with activity-driven structure

The interplay between disease and awareness has been extensively studied in static networks. However, most networks in reality will evolve over time. Based on this, we propose a novel epidemiological model in multiplex networks. In this model, the disease spreading layer is a time-varying network generated by the activity-driven model, while the awareness diffusion layer is a static network, and the heterogeneity of individual infection and recovery ability is considered. First, we extend the microscopic Markov chain approach to analytically obtain the epidemic threshold of the model. Then, we simulate the spread of disease and find that stronger heterogeneity in the individual activities of a physical layer can promote disease spreading, while stronger heterogeneity of the virtual layer network will hinder the spread of disease. Interestingly, we find that when the individual infection ability follows Gaussian distribution, the heterogeneity of infection ability has little effect on the spread of disease, but it will significantly affect the epidemic threshold when the individual infection ability follows power-law distribution. Finally, we find the emergence of a metacritical point where the diffusion of awareness is able to control the onset of the epidemics. Our research could cast some light on exploring the dynamics of epidemic spreading in time-varying multiplex networks.

Percolation in random graphs with higher-order clustering

Percolation theory can be used to describe the structural properties of complex networks using the generating function formulation. This mapping assumes that the network is locally treelike and does not contain short-range loops between neighbors. In this paper we use the generating function formulation to examine clustered networks that contain simple cycles and cliques of any order. We use the natural generalization to the Molloy-Reed criterion for these networks to describe their critical properties and derive an approximate analytical description of the size of the giant component, providing solutions for Poisson and power-law networks. We find that networks comprising larger simple cycles behave increasingly more treelike. Conversely, clustering composed of larger cliques increasingly deviate from the treelike solution, although the behavior is strongly dependent on the degree-assortativity.

Random graphs with arbitrary clustering and their applications

The structure of many real networks is not locally treelike and, hence, network analysis fails to characterize their bond percolation properties. In a recent paper [P. Mann, V. A. Smith, J. B. O. Mitchell, and S. Dobson, arXiv:2006.06744], we developed analytical solutions to the percolation properties of random networks with homogeneous clustering (clusters whose nodes are degree equivalent). In this paper, we extend this model to investigate networks that contain clusters whose nodes are not degree equivalent, including multilayer networks. Through numerical examples, we show how this method can be used to investigate the properties of random complex networks with arbitrary clustering, extending the applicability of the configuration model and generating function formulation.

Critical network cascades with re-excitable nodes: Why treelike approximations usually work, when they break down, and how to correct them

Network science is a rapidly expanding field, with a large and growing body of work on network-based dynamical processes. Most theoretical results in this area rely on the so-called locally treelike approximation. This is, however, usually an "uncontrolled" approximation, in the sense that the magnitudes of the error are typically unknown, although numerical results show that this error is often surprisingly small. In this paper we place this approximation on more rigorous footing by calculating the magnitude of deviations away from tree-based theories in the context of discrete-time critical network cascades with re-excitable nodes. We discuss the conditions under which tree-like approximations give good results for calculating network criticality, and also explain the reasons for deviation from this approximation, in terms of the density of certain kinds of network motifs. Using this understanding, we derive results for network criticality that apply to general networks that explicitly do not satisfy the locally treelike approximation. In particular, we focus on the biparallel motif, the smallest motif relevant to the failure of a tree-based theory in this context, and we derive the corrections due to such motifs on the conditions for criticality. We verify our claims on computer-generated networks, and we confirm that our theory accurately predicts the observed deviations from criticality. Using our theory, we explain why numerical simulations often show that deviations from a tree-based theory are surprisingly small. More specifically, we show that these deviations are negligible for networks whose average degree is even modestly large compared to one, justifying why tree-based theories appear to work well for most real-world networks.

Message-passing theory for cooperative epidemics

The interaction among spreading processes on a complex network is a nontrivial phenomenon of great importance. It has recently been realized that cooperative effects among infective diseases can give rise to qualitative changes in the phenomenology of epidemic spreading, leading, for instance, to abrupt transitions and hysteresis. Here, we consider a simple model for two interacting pathogens on a network and we study it by using the message-passing approach. In this way, we are able to provide detailed predictions for the behavior of the model in the whole phase-diagram for any given network structure. Numerical simulations on synthetic networks (both homogeneous and heterogeneous) confirm the great accuracy of the theoretical results. We finally consider the issue of identifying the nodes where it is better to seed the infection in order to maximize the probability of observing an extensive outbreak. The message-passing approach provides an accurate solution also for this problem.

Optimizing spreading dynamics in interconnected networks

Adding edges between layers of interconnected networks is an important way to optimize the spreading dynamics. While previous studies mostly focused on the case of adding a single edge, the theoretical optimal strategy for adding multiple edges still need to be studied. In this study, based on the susceptible-infected-susceptible model, we investigate the problem of maximizing the stationary spreading prevalence in interconnected networks. For two isolated networks, we maximize the spreading prevalence near the critical point by choosing multiple interconnecting edges. We present a theoretical analysis based on the discrete-time Markov chain approach to derive the approximate optimal strategy. The optimal interlayer structure predicted by the strategy maximizes the spreading prevalence, meanwhile minimizing the spreading outbreak threshold for the interconnected network simultaneously. Numerical simulations on synthetic and real-world networks show that near the critical point, the proposed strategy gives better performance than connecting large degree nodes and randomly connecting.

Contact-Based Model for Epidemic Spreading on Temporal Networks

We present a contact-based model to study the spreading of epidemics by means of extending the dynamic message-passing approach to temporal networks. The shift in perspective from node- to edge-centric quantities enables accurate modeling of Markovian susceptible-infected-recovered outbreaks on time-varying trees, i.e., temporal networks with a loop-free underlying topology. On arbitrary graphs, the proposed contact-based model incorporates potential structural and temporal heterogeneities of the contact network and improves analytic estimations with respect to the individual-based (node-centric) approach at a low computational and conceptual cost. Within this new framework, we derive an analytical expression for the epidemic threshold on temporal networks and demonstrate the feasibility of this method on empirical data.

The spread of infection, information, computer malware, or any contagionlike process is often described by disease models on complex networks with a time-varying topology. Recurrent, or flulike, spreading can be modeled accurately by taking an “individual-based” approach that focuses on nodes in a network. Here, we instead focus on the interactions—the links in a network—and present a contact-based model that accurately describes a second group of contagion processes: those that lead to permanent immunization. Taking this new perspective, we derive a criterion that separates local outbreaks from global epidemics, a crucial tool for risk assessment and control of, for instance, viral marketing.

To develop our model, we integrate time-varying network topologies into dynamic message passing, a widely used approach to describe unidirectional contagion processes. Based on this generalized model, we derive a spectral criterion for the stability of the disease-free solution, which determines the critical disease parameters. Through numerous numerical studies, we provide evidence that the contact-based perspective improves the individual-based approach. Finally, we investigate the epidemic risk based on the German cattle-trade network with over 180 000 nodes. Results from the individual-based and contact-based approaches deviate considerably, and thus justify this paradigmatic shift.

Our contact-based model is conceptually similar to those that focus on individuals, so we expect that numerous individual-based findings as well as results from networks with a static topology can be transferred in the future. These may include general epidemic models with a non-Poissonian transition process that go beyond the assumption of treelike topologies, stochastic effects, and temporal networks that evolve continuously in time.

Morphological organization of point-to-point transport in complex networks

We investigate the structural organization of the point-to-point electric, diffusive or hydraulic transport in complex scale-free networks. The random choice of two nodes, a source and a drain, to which a potential difference is applied, selects two tree-like structures, one emerging from the source and the other converging to the drain. These trees merge into a large cluster of the remaining nodes that is found to be quasi-equipotential and thus presents almost no resistance to transport. Such a global “tree-cluster-tree” structure is universal and leads to a power law decay of the currents distribution. Its exponent, −2, is determined by the multiplicative decrease of currents at successive branching points of a tree and is found to be independent of the network connectivity degree and resistance distribution.

Self-avoiding walks and connective constants in clustered scale-free networks

Various types of walks on complex networks have been used in recent years to model search and navigation in several kinds of systems, with particular emphasis on random walks. This gives valuable information on network properties, but self-avoiding walks (SAWs) may be more suitable than unrestricted random walks to study long-distance characteristics of complex systems. Here we study SAWs in clustered scale-free networks, characterized by a degree distribution of the form P(k)∼k^{-γ} for large k. Clustering is introduced in these networks by inserting three-node loops (triangles). The long-distance behavior of SAWs gives us information on asymptotic characteristics of such networks. The number of self-avoiding walks, a_{n}, has been obtained by direct enumeration, allowing us to determine the connective constant μ of these networks as the large-n limit of the ratio a_{n}/a_{n-1}. An analytical approach is presented to account for the results derived from walk enumeration, and both methods give results agreeing with each other. In general, the average number of SAWs a_{n} is larger for clustered networks than for unclustered ones with the same degree distribution. The asymptotic limit of the connective constant for large system size N depends on the exponent γ of the degree distribution: For γ>3, μ converges to a finite value as N→∞; for γ=3, the size-dependent μ_{N} diverges as lnN, and for γ<3 we have μ_{N}∼N^{(3-γ)/2}.

Multiple structural transitions in interacting networks

Many real-world systems can be modeled as interconnected multilayer networks, namely, a set of networks interacting with each other. Here, we present a perturbative approach to study the properties of a general class of interconnected networks as internetwork interactions are established. We reveal multiple structural transitions for the algebraic connectivity of such systems, between regimes in which each network layer keeps its independent identity or drives diffusive processes over the whole system, thus generalizing previous results reporting a single transition point. Furthermore, we show that, at first order in perturbation theory, the growth of the algebraic connectivity of each layer depends only on the degree configuration of the interaction network (projected on the respective Fiedler vector), and not on the actual interaction topology. Our findings can have important implications in the design of robust interconnected networked systems, particularly in the presence of network layers whose integrity is more crucial for the functioning of the entire system. We finally show results of perturbation theory applied to the adjacency matrix of the interconnected network, which can be useful to characterize percolation processes on such systems.

Modelling indirect interactions during failure spreading in a project activity network

Spreading broadly refers to the notion of an entity propagating throughout a networked system via its interacting components. Evidence of its ubiquity and severity can be seen in a range of phenomena, from disease epidemics to financial systemic risk. In order to understand the dynamics of these critical phenomena, computational models map the probability of propagation as a function of direct exposure, typically in the form of pairwise interactions between components. By doing so, the important role of indirect interactions remains unexplored. In response, we develop a simple model that accounts for the effect of both direct and subsequent exposure, which we deploy in the novel context of failure propagation within a real-world engineering project. We show that subsequent exposure has a significant effect in key aspects, including the: (a) final spreading event size, (b) propagation rate, and (c) spreading event structure. In addition, we demonstrate the existence of 'hidden influentials' in large-scale spreading events, and evaluate the role of direct and subsequent exposure in their emergence. Given the evidence of the importance of subsequent exposure, our findings offer new insight on particular aspects that need to be included when modelling network dynamics in general, and spreading processes specifically.

Epidemic Threshold in Continuous-Time Evolving Networks

Current understanding of the critical outbreak condition on temporal networks relies on approximations (time scale separation, discretization) that may bias the results. We propose a theoretical framework to compute the epidemic threshold in continuous time through the infection propagator approach. We introduce the weak commutation condition allowing the interpretation of annealed networks, activity-driven networks, and time scale separation into one formalism. Our work provides a coherent connection between discrete and continuous time representations applicable to realistic scenarios.

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.

Accurate ranking of influential spreaders in networks based on dynamically asymmetric link weights

We propose an efficient and accurate measure for ranking spreaders and identifying the influential ones in spreading processes in networks. While the edges determine the connections among the nodes, their specific role in spreading should be considered explicitly. An edge connecting nodes i and j may differ in its importance for spreading from i to j and from j to i. The key issue is whether node j, after infected by i through the edge, would reach out to other nodes that i itself could not reach directly. It becomes necessary to invoke two unequal weights w_{ij} and w_{ji} characterizing the importance of an edge according to the neighborhoods of nodes i and j. The total asymmetric directional weights originating from a node leads to a novel measure s_{i}, which quantifies the impact of the node in spreading processes. An s-shell decomposition scheme further assigns an s-shell index or weighted coreness to the nodes. The effectiveness and accuracy of rankings based on s_{i} and the weighted coreness are demonstrated by applying them to nine real-world networks. Results show that they generally outperform rankings based on the nodes' degree and k-shell index while maintaining a low computational complexity. Our work represents a crucial step towards understanding and controlling the spread of diseases, rumors, information, trends, and innovations in networks.

Nonbacktracking expansion of finite graphs

Message passing equations yield a sharp percolation transition in finite graphs, as an artifact of the locally treelike approximation. For an arbitrary finite, connected, undirected graph we construct an infinite tree having the same local structural properties as this finite graph, when observed by a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of the Bethe lattice. We indicate an infinite, locally treelike, random network whose local structure is exactly given by this infinite tree. Message passing equations for various cooperative models on this construction are the same as for the original finite graph, but here they provide the exact solutions of the corresponding cooperative problems. These solutions are good approximations to observables for the models on the original graph when it is sufficiently large and not strongly correlated. We show how to express these solutions in the critical region in terms of the principal eigenvector components of the nonbacktracking matrix. As representative examples we formulate the problems of the random and optimal destruction of a connected graph in terms of our construction, the nonbacktracking expansion. We analyze the limitations and the accuracy of the message passing algorithms for different classes of networks and compare the complexity of the message passing calculations to that of direct numerical simulations. Notably, in a range of important cases, simulations turn out to be more efficient computationally than the message passing.

Unification of theoretical approaches for epidemic spreading on complex networks

Models of epidemic spreading on complex networks have attracted great attention among researchers in physics, mathematics, and epidemiology due to their success in predicting and controlling scenarios of epidemic spreading in real-world scenarios. To understand the interplay between epidemic spreading and the topology of a contact network, several outstanding theoretical approaches have been developed. An accurate theoretical approach describing the spreading dynamics must take both the network topology and dynamical correlations into consideration at the expense of increasing the complexity of the equations. In this short survey we unify the most widely used theoretical approaches for epidemic spreading on complex networks in terms of increasing complexity, including the mean-field, the heterogeneous mean-field, the quench mean-field, dynamical message-passing, link percolation, and pairwise approximation. We build connections among these approaches to provide new insights into developing an accurate theoretical approach to spreading dynamics on complex networks.

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.

Fragmenting networks by targeting collective influencers at a mesoscopic level

A practical approach to protecting networks against epidemic processes such as spreading of infectious diseases, malware, and harmful viral information is to remove some influential nodes beforehand to fragment the network into small components. Because determining the optimal order to remove nodes is a computationally hard problem, various approximate algorithms have been proposed to efficiently fragment networks by sequential node removal. Morone and Makse proposed an algorithm employing the non-backtracking matrix of given networks, which outperforms various existing algorithms. In fact, many empirical networks have community structure, compromising the assumption of local tree-like structure on which the original algorithm is based. We develop an immunization algorithm by synergistically combining the Morone-Makse algorithm and coarse graining of the network in which we regard a community as a supernode. In this way, we aim to identify nodes that connect different communities at a reasonable computational cost. The proposed algorithm works more efficiently than the Morone-Makse and other algorithms on networks with community structure.

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.

Message passing theory for percolation models on multiplex networks with link overlap

Multiplex networks describe a large variety of complex systems, including infrastructures, transportation networks, and biological systems. Most of these networks feature a significant link overlap. It is therefore of particular importance to characterize the mutually connected giant component in these networks. Here we provide a message passing theory for characterizing the percolation transition in multiplex networks with link overlap and an arbitrary number of layers M. Specifically we propose and compare two message passing algorithms that generalize the algorithm widely used to study the percolation transition in multiplex networks without link overlap. The first algorithm describes a directed percolation transition and admits an epidemic spreading interpretation. The second algorithm describes the emergence of the mutually connected giant component, that is the percolation transition, but does not preserve the epidemic spreading interpretation. We obtain the phase diagrams for the percolation and directed percolation transition in simple representative cases. We demonstrate that for the same multiplex network structure, in which the directed percolation transition has nontrivial tricritical points, the percolation transition has a discontinuous phase transition, with the exception of the trivial case in which all the layers completely overlap.

Clustering Implies Geometry in Networks

Network models with latent geometry have been used successfully in many applications in network science and other disciplines, yet it is usually impossible to tell if a given real network is geometric, meaning if it is a typical element in an ensemble of random geometric graphs. Here we identify structural properties of networks that guarantee that random graphs having these properties are geometric. Specifically we show that random graphs in which expected degree and clustering of every node are fixed to some constants are equivalent to random geometric graphs on the real line, if clustering is sufficiently strong. Large numbers of triangles, homogeneously distributed across all nodes as in real networks, are thus a consequence of network geometricity. The methods we use to prove this are quite general and applicable to other network ensembles, geometric or not, and to certain problems in quantum gravity.