2018/04/25 by Ido Tishby, Ofer Biham, Eytan Katzav +1 · 30 citations
Mathematics · Physics and Astronomy · #Combinatorics #Complex Network Analysis Techniques #Complex network #Component (thermodynamics) #Degree (music) #Degree distribution #Giant component #Graph #Graph theory and applications #Mathematics #Opinion Dynamics and Social Influence #Physics #Random graph #Statistical physics #Statistics #Uncorrelated #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.97.042318
published in Physical review. E 97(4), 042318 (American Physical Society) · 30 pages, 13 figures
openalex publication_date 2018/04/25 · arxiv created 2018/04/26 · arxiv updated 2018/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The microstructure of the giant component of the Erdő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 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.