Network cloning unfolds the effect of clustering on dynamical processes

Symbiotic and antagonistic disease dynamics on networks using bond percolation

In this paper we introduce a description of the equilibrium state of a bond percolation process on random graphs using the exact method of generating functions. This allows us to find the expected size of the giant connected component (GCC) of two sequential bond percolation processes in which the bond occupancy probability of the second process is modulated (increased or decreased) by a node being inside or outside of the GCC created by the first process. In the context of epidemic spreading this amounts to both an antagonistic partial immunity and a synergistic partial coinfection interaction between the two sequential diseases. We examine configuration model networks with tunable clustering. We find that the emergent evolutionary behavior of the second strain is highly dependent on the details of the coupling between the strains. Contact clustering generally reduces the outbreak size of the second strain relative to unclustered topologies; however, positive assortativity induced by clustered contacts inverts this conclusion for highly transmissible disease dynamics.

Emergence of power laws in noncritical neuronal systems

Experimental and computational studies provide compelling evidence that neuronal systems are characterized by power-law distributions of neuronal avalanche sizes. This fact is interpreted as an indication that these systems are operating near criticality, and, in turn, typical properties of critical dynamical processes, such as optimal information transmission and stability, are attributed to neuronal systems. The purpose of this Rapid Communication is to show that the presence of power-law distributions for the size of neuronal avalanches is not a sufficient condition for the system to operate near criticality. Specifically, we consider a simplistic model of neuronal dynamics on networks and show that the degree distribution of the underlying neuronal network may trigger power-law distributions for neuronal avalanches even when the system is not in its critical regime. To certify and explain our findings we develop an analytical approach based on percolation theory and branching processes techniques.

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.

A framework for analyzing contagion in assortative banking networks

We introduce a probabilistic framework that represents stylized banking networks with the aim of predicting the size of contagion events. Most previous work on random financial networks assumes independent connections between banks, whereas our framework explicitly allows for (dis)assortative edge probabilities (i.e., a tendency for small banks to link to large banks). We analyze default cascades triggered by shocking the network and find that the cascade can be understood as an explicit iterated mapping on a set of edge probabilities that converges to a fixed point. We derive a cascade condition, analogous to the basic reproduction number R₀ in epidemic modelling, that characterizes whether or not a single initially defaulted bank can trigger a cascade that extends to a finite fraction of the infinite network. This cascade condition is an easily computed measure of the systemic risk inherent in a given banking network topology. We use percolation theory for random networks to derive a formula for the frequency of global cascades. These analytical results are shown to provide limited quantitative agreement with Monte Carlo simulation studies of finite-sized networks. We show that edge-assortativity, the propensity of nodes to connect to similar nodes, can have a strong effect on the level of systemic risk as measured by the cascade condition. However, the effect of assortativity on systemic risk is subtle, and we propose a simple graph theoretic quantity, which we call the graph-assortativity coefficient, that can be used to assess systemic risk.

Limitations of discrete-time approaches to continuous-time contagion dynamics

Continuous-time Markov process models of contagions are widely studied, not least because of their utility in predicting the evolution of real-world contagions and in formulating control measures. It is often the case, however, that discrete-time approaches are employed to analyze such models or to simulate them numerically. In such cases, time is discretized into uniform steps and transition rates between states are replaced by transition probabilities. In this paper, we illustrate potential limitations to this approach. We show how discretizing time leads to a restriction on the values of the model parameters that can accurately be studied. We examine numerical simulation schemes employed in the literature, showing how synchronous-type updating schemes can bias discrete-time formalisms when compared against continuous-time formalisms. Event-based simulations, such as the Gillespie algorithm, are proposed as optimal simulation schemes both in terms of replicating the continuous-time process and computational speed. Finally, we show how discretizing time can affect the value of the epidemic threshold for large values of the infection rate and the recovery rate, even if the ratio between the former and the latter is small.

Emergence of coexisting percolating clusters in networks

It is commonly assumed in percolation theories that at most one percolating cluster can exist in a network. We show that several coexisting percolating clusters (CPCs) can emerge in networks due to limited mixing, i.e., a finite and sufficiently small number of interlinks between network modules. We develop an approach called modular message passing (MMP) to describe and verify these observations. We demonstrate that the appearance of CPCs is an important source of inaccuracy in previously introduced percolation theories, such as the message passing (MP) approach, which is a state-of-the-art theory based on the belief propagation method. Moreover, we show that the MMP theory improves significantly over the predictions of MP for percolation on synthetic networks with limited mixing and also on several real-world networks. These findings have important implications for understanding the robustness of networks and in quantifying epidemic outbreaks in the susceptible-infected-recovered (SIR) model of disease spread.

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.