On the robustness of power-law random graphs in the finite mean, infinite variance region

2008/01/07 by Ilkka Norros, I. Norros, Norros, I. +3
Mathematics · Physics and Astronomy · #05C80 #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #math.PR #msc:05C80

paper · pdf · doi:10.48550/arxiv.0801.1079

13 pages

arxiv created 2008/01/07 · openalex publication_date 2008/01/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a conditionally Poissonian random graph model where the mean degrees, `capacities', follow a power-tailed distribution with finite mean and infinite variance. Such a graph of size N has a giant component which is super-small in the sense that the typical distance between vertices is of the order of loglog N. The shortest paths travel through a core consisting of nodes with high mean degrees. In this paper we derive upper bounds of the typical distance when an upper part of the core is removed, including the case that the whole core is removed.

Related

• Universality for the distance in finite variance random graphs: Extended version
• Distances in random graphs with finite variance degrees
• Random graphs with arbitrary i.i.d. degrees
• Distances in random graphs with infinite mean degrees
• Distances in random graphs with finite mean and infinite variance degrees