Random networks with tunable degree distribution and clustering

2004/05/31 by Erik Volz
Mathematics · Physics and Astronomy · #Algorithm #Closure (psychology) #Cluster analysis #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Degree (music) #Degree distribution #Exponential distribution #Giant component #Mathematics #Opinion Dynamics and Social Influence #Physics #Point process #Poisson distribution #Random graph #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Theoretical computer science #cond-mat.dis-nn #cond-mat.stat-mech

paper · pdf · doi:10.1103/physreve.70.056115

9 pages, 13 figures corrected typos, added two references, reorganized references

arxiv created 2004/06/04 · openalex publication_date 2004/11/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present an algorithm for generating random networks with arbitrary degree distribution and clustering (frequency of triadic closure). We use this algorithm to generate networks with exponential, power law, and Poisson degree distributions with variable levels of clustering. Such networks may be used as models of social networks and as a testable null hypothesis about network structure. Finally, we explore the effects of clustering on the point of the phase transition where a giant component forms in a random network, and on the size of the giant component. Some analysis of these effects is presented.

Citations

• On the uniform generation of random graphs with prescribed degree sequences
• How to generate a random growing network
• Organization of growing random networks
• Emergence of a Small World from Local Interactions: Modeling Acquaintance Networks
• Hierarchical organization in complex networks
• Breakdown of the Internet under Intentional Attack
• Measures of concurrency in networks and the spread of infectious disease
• Performance of networks of artificial neurons: The role of clustering
• Mixing patterns in networks
• Error and attack tolerance of complex networks
• A simple model of global cascades on random networks
• 5. Sampling and Estimation in Hidden Populations Using Respondent-Driven Sampling
• Statistical mechanics of complex networks
• Evolution of networks
• Respondent-Driven Sampling II: Deriving Valid Population Estimates from Chain-Referral Samples of Hidden Populations
• The Structure and Function of Complex Networks
• Random graphs with arbitrary degree distributions and their applications