Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles

Abstract

The micro-structure of the giant component of the Erd{\H o}s-Rényi network and other configuration model networks is analyzed using generating function methods. While configuration model networks are uncorrelated, the giant component exhibits a degree distribution which is different from the overall degree distribution of the network and includes degree-degree correlations of all orders. We present exact analytical results for the degree distributions as well as higher order degree-degree correlations on the giant components of configuration model networks. We show that the degree-degree correlations are essential for the integrity of the giant component, in the sense that the degree distribution alone cannot guarantee that it will consist of a single connected component. To demonstrate the importance and broad applicability of these results, we apply them to the study of the distribution of shortest path lengths on the giant component, percolation on the giant component and the spectra of sparse matrices defined on the giant component. We show that by using the degree distribution on the giant component, one obtains high quality results for these properties, which can be further improved by taking the degree-degree correlations into account. This suggests that many existing methods, currently used for the analysis of the whole network, can be adapted in a straightforward fashion to yield results conditioned on the giant component.

arXiv comment30 pages, 13 figures

References in corpus (28)

• Statistical mechanics of complex networks
• Assortative mixing in networks
• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• The phase transition in inhomogeneous random graphs
• A message passing approach for general epidemic models
• Introduction to Random Matrices - Theory and Practice
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• The entropic origin of disassortativity in complex networks
• Spectra of Sparse Random Matrices
• First Passage Properties of the Erdos-Renyi Random Graph
• A single defect approximation for localized states on random lattices
• On large deviation properties of Erdos-Renyi random graphs
• Distance distribution in random graphs and application to networks exploration
• Degree correlations in directed scale-free networks
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Assessing node risk and vulnerability in epidemics on networks
• Distribution of shortest cycle lengths in random networks
• Heterogeneous micro-structure of percolation in sparse networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• The average number of distinct sites visited by a random walker on random graphs
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• Duality in inhomogeneous random graphs, and the cut metric

Cited by in corpus (21)

• Percolation on complex networks: Theory and application
• Disassortativity of percolating clusters in random networks
• Large deviations of random walks on random graphs
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Statistical analysis of articulation points in configuration model networks
• Structure of percolating clusters in random clustered networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Degree correlations in graphs with clique clustering
• Statistical analysis of edges and bredges in configuration model networks
• Topological conditions drive stability in meta-ecosystems
• Phases of Small Worlds: A Mean Field Formulation
• The Fate of Articulation Points and Bredges in Percolation
• Emergence of Long-Range Correlations in Random Networks
• Generating random networks that consist of a single connected component with a given degree distribution
• A Random Walk Perspective on Hide-and-Seek Games
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Emergent networks in fractional percolation
• Vaccination with partial transmission and social distancing on contact networks
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment