The unreasonable effectiveness of tree-based theory for networks with clustering

Abstract

We demonstrate that a tree-based theory for various dynamical processes yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance $\ell$ is sufficiently small - i.e., as long as it is close to the value of $\ell$ in a random network with negligible clustering and the same degree-degree correlations. We confirm this hypothesis numerically using real-world networks from various domains and on several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks provided that the networks are "sufficiently small" worlds.

12 pages, 8 figures

References in corpus (12)

• Synchronization in complex networks
• Critical phenomena in complex networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Random graphs with clustering
• Percolation and Epidemic Thresholds in Clustered Networks
• Clustering in complex networks. I. General formalism
• Percolation on correlated networks
• Clustering in complex networks. II. Percolation properties
• Bond percolation on a class of clustered random networks
• Organization of modular networks
• Ring structures and mean first passage time in networks
• Communication and correlation among communities

Cited by in corpus (77)

• Multilayer Networks
• The Kuramoto model in complex networks
• Suppressing cascades of load in interdependent networks
• The Statistical Physics of Real-World Networks
• Percolation in real interdependent networks
• Explosive Phenomena in Complex Networks
• Binary-state dynamics on complex networks: pair approximation and beyond
• Network models of financial systemic risk: A review
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Branching Dynamics of Viral Information Spreading
• Multi-Stage Complex Contagions
• The limitations of discrete-time approaches to continuous-time contagion dynamics
• The effects of network structure, competition and memory time on social spreading phenomena
• Statistical Properties of Avalanches in Networks
• Deciphering the global organization of clustering in real complex networks
• Structural inference for uncertain networks
• Efficient collective influence maximization in cascading processes with first-order transitions
• Beyond the locally tree-like approximation for percolation on real networks
• Temporal profiles of avalanches on networks
• A message-passing approach to epidemic tracing and mitigation with apps
• Dynamics on Modular Networks with Heterogeneous Correlations
• Co-circulation of infectious diseases on networks
• Network cloning unfolds the effect of clustering on dynamical processes
• Percolation in real multiplex networks
• Influence of trust in the spreading of information
• Hipsters on Networks: How a Small Group of Individuals Can Lead to an Anti-Establishment Majority
• Layer-switching cost and optimality in information spreading on multiplex networks
• Criticality in spreading processes without time-scale separation and the critical brain hypothesis
• Contact-based model for epidemic spreading on temporal networks
• Assessing node risk and vulnerability in epidemics on networks
• How Damage Diversification Can Reduce Systemic Risk
• Social Clustering in Epidemic Spread on Coevolving Networks
• Network Modularity Controls the Speed of Information Diffusion
• Percolation on random networks with arbitrary k-core structure
• Ising model in clustered scale-free networks
• A framework for analyzing contagion in assortative banking networks
• Network Dynamics on Graphops
• Spreading of Memes on Multiplex Networks
• Message-Passing Methods for Complex Contagions
• Dynamical Instability in Boolean Networks as a Percolation Problem
• Percolation and the effective structure of complex networks
• Targeted influence maximization in complex networks
• Stability of Boolean networks: The joint effects of topology and update rules
• Exact solutions for social and biological contagion models on mixed directed and undirected, degree-correlated random networks
• Tweaking Synchronisation by Link Addition
• Dynamic range maximization in excitable networks
• Uncertainty Reduction for Stochastic Processes on Complex Networks
• Complex Contagions with Timers
• Random walk on temporal networks with lasting edges
• Dynamics of diffusion on monoplex and multiplex networks: A message-passing approach
• Competition and dual users in complex contagion processes
• Nonlinear consensus on networks: equilibria, effective resistance and trees of motifs
• Heterogeneous message passing for heterogeneous networks
• Dynamical influence processes on networks: General theory and applications to social contagion
• Spectra of random networks in the weak clustering regime
• Predicting the diversity of early epidemic spread on networks
• Cycles and Clustering in Multiplex Networks
• Degree correlations in graphs with clique clustering
• Emergence of coexisting percolating clusters in networks
• Effectiveness of Contact Tracing on Networks with Cliques
• A network-specific approach to percolation in networks with bidirectional links
• Concurrency and reachability in tree-like temporal networks
• Belief propagation on networks with cliques and chordless cycles
• Degree-targeted cascades in modular, degree-heterogeneous networks
• Observability transition in real networks
• Temporal Dynamics of Connectivity and Epidemic Properties of Growing Networks
• On Watts' Cascade Model with Random Link Weights
• Backtracking activation impacts the criticality of excitable networks
• Critical Network Cascades with Re-excitable nodes: Why tree-like approximations usually work, when they breakdown, and how to correct them
• Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
• Exact analytical solution of irreversible binary dynamics on networks
• An approximation for return time distributions of random walks on sparse networks
• Vaccination with partial transmission and social distancing on contact networks
• On-off Threshold Models of Social Contagion
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Systemic Cascades On Inhomogeneous Random Financial Networks