Component sizes in networks with arbitrary degree distributions

Abstract

We give an exact solution for the complete distribution of component sizes in random networks with arbitrary degree distributions. The solution tells us the probability that a randomly chosen node belongs to a component of size s, for any s. We apply our results to networks with the three most commonly studied degree distributions -- Poisson, exponential, and power-law -- as well as to the calculation of cluster sizes for bond percolation on networks, which correspond to the sizes of outbreaks of SIR epidemic processes on the same networks. For the particular case of the power-law degree distribution, we show that the component size distribution itself follows a power law everywhere below the phase transition at which a giant component forms, but takes an exponential form when a giant component is present.

5 pages, 1 figure

References in corpus (8)

• The structure and function of complex networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Evolution of networks
• Classes of behavior of small-world networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks

Cited by in corpus (24)

• Multilayer Networks
• Critical phenomena in complex networks
• Percolation on complex networks: Theory and application
• A Scalable Generative Graph Model with Community Structure
• Core percolation on complex networks
• Cascades on a class of clustered random networks
• Link overlap, viability, and mutual percolation in multiplex networks
• Breaking of the site-bond percolation universality in networks
• Cooperative epidemics on multiplex networks
• Effect of edge removal on topological and functional robustness of complex networks
• Bond percolation on a class of correlated and clustered random graphs
• General expression for the component size distribution in infinite configuration networks
• Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions
• Degree correlations in graphs with clique clustering
• Statistical analysis of edges and bredges in configuration model networks
• Push- and Pull-based Epidemic Spreading in Networks: Thresholds and Deeper Insights
• Degree and component size distributions in generalized uniform recursive tree
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Scaling and universality for percolation in random networks: A unified view
• The network epidemiology of an Ebola epidemic
• Default contagion risks in Russian interbank market
• The distribution of the number of cycles in directed and undirected random 2-regular graphs
• Connected components in networks with higher-order interactions
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment