Random graphs with arbitrary degree distributions and their applications
Bibliographic Data
| ID | 23337142 |
|---|---|
| Authors | M E J Newman (0000-0002-0907-1660, Santa Fe Institute), Steven H Strogatz (0000-0003-2923-3118, Cornell University), Duncan J Watts (0000-0001-5005-4961, Santa Fe Institute) |
| Year | 2001 |
| Volume | 64 |
| Issue | 2 |
| Pages | 026118-026118 |
| Publication date | 2001-07-24 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Physical Review E (JOURNAL) |
| Journal identifiers | ISSN: 1539-3755 • E-ISSN: 1550-2376 |
| Publisher | American Physical Society (APS) (PUBLISHER) |
| DOI | 10.1103/physreve.64.026118 |
| PMID | 11497662 |
| OpenAlex | W2169015768 |
| Language | EN |
| Citations received | 140 |
| References cited | 35 |
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Bipartite graph · Chordal graph · Combinatorics · Complex network · Degree (music) · Degree distribution · Discrete mathematics · Giant component · Graph · Indifference graph · Line graph · Pathwidth · Physics · Random graph · Vertex (graph theory) · Complex Network Analysis Techniques · Graph theory and applications · Mathematics · Opinion Dynamics and Social Influence
Perception and privilege
Preferential attachment hypergraph with high modularity
Measuring directed triadic closure with closure coefficients
Triadic analysis of affiliation networks
Networks, Percolation, and Consumer Demand
Homophily as a Process Generating Social Networks
A social network caught in the Web
Network Structure and the Risk for HIV Transmission Among Rural Drug Users
Evolutionary radiation and the spectrum of consciousness
Building blocks of communication networks in times of crises
Disaster response on September 11, 2001 through the lens of statistical network analysis
Bringing the owners back in
Quién programa las redes sociales en Internet? El caso de Twiter en el movimiento #Yosoy132 México
Getting into Networks and Clusters
Cluster Emergence and Network Evolution
The structure of scientific collaboration networks
Analyzing local and global properties of multigraphs
Are the World’s Languages Consolidating? The Dynamics and Distribution of Language Populations
Structural Cohesion and Embeddedness
Price dynamics, financial fragility and aggregate volatility
Spiral of Silence in the Social Media Era
Social Media Mining
Imputation of Missing Network Data
Exponential Random Graph Models
Social Networks in Byzantine Egypt
Spatial networks
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Epidemic processes in complex networks
Multilayer networks
A simple model of global cascades on random networks
Small Worlds Among Interlocking Directors
Evolution of the social network of scientific collaborations
Clustering and preferential attachment in growing networks
Finding community structure in networks using the eigenvectors of matrices
Assortative Mixing in Networks
Mixing patterns in networks
Catastrophic cascade of failures in interdependent networks
Statistical mechanics of complex networks
Spread of epidemic disease on networks
Multirelational organization of large-scale social networks in an online world
Coauthorship networks and patterns of scientific collaboration
Characterization of complex networks
Why social networks are different from other types of networks
Network ‘Small-World-Ness’
Random graph models of social networks
Community structure in social and biological networks
The Structure and Function of Complex Networks
Transitivity correlation
Academic team formation as evolving hypergraphs
Robustness and modular structure in networks
Convexity in complex networks
The network structure of mathematical knowledge according to the Wikipedia, MathWorld, and DLMF online libraries
An analysis of emotion-exchange motifs in multiplex networks during emergency events
Diversity and Community Can Coexist
How individuals’ opinions influence society’s resistance to epidemics
Network security and contagion
Focus statistics for testing network centrality on uncorrelated random graphs
On the impact of network size and average degree on the robustness of centrality measures
The Friendship Paradox and Systematic Biases in Perceptions and Social Norms
Higher-order interactions shape collective human behaviour
Properties of latent variable network models
Mean-field dynamics of the non-consensus opinion model
Roles of institutions and dynamic capability in the relationship between collaboration and performance in emergency management
Something draws near, I can feel it
Multilayer Networks
When do institutions suddenly collapse? Zones of knowledge and the likelihood of political cascades
Epidemic potential by sexual activity distributions
Disjoint and Overlapping Community Detection in Small-World Networks Leveraging Mean Path Length
City Transmission Networks
Large very dense subgraphs in a stream of edges
An internationalised Europe and regionally focused Americas
Interactions among organizations from science, technology, and industry on the basis of percolation theory
Structure of university licensing networks
Higher-order rich-club phenomenon in collaborative research grant networks
Systemic gendered citation imbalance in computer science
When Disagreement Becomes Uncivil on Social Media
When Opinions Polarize Without Persuasion
Highlighting action and environmental component interactions using a network theory approach
Locating women board members in gendered director networks
A Statistical Model of Bipartite Networks
If the Financial System Is Complex, How Can We Regulate It
The power of local networking
A new look at clustering coefficients with generalization to weighted and multi-faction networks
Unleashing the potential of relational research
Engineering complexity
Unfolding Community Structure in Rainfall Network of Germany Using Complex Network-Based Approach
Theories for Influencer Identification in Complex Networks
Assessing the ecology of cluster-based enterprise trust networks through percolation theory
New Survey Questions and Estimators for Network Clustering with Respondent-driven Sampling Data
Sampling and Estimation in Hidden Populations Using Respondent-Driven Sampling
Macrostructure from Microstructure
The Small World of the American Corporate Elite, 1982-2001
Building them up, breaking them down
The structure of educational research
Basic notions for the analysis of large two-mode networks
Effects of missing data in social networks
Spectral goodness of fit for network models
Modelling the evolution of a bipartite network—Peer referral in interlocking directorates
Exploratory social network analysis of affiliation networks of Indian listed companies
Random alliance networks
Social Network Analysis
Diameter of the World-Wide Web
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
Scientific collaboration networks. I. Network construction and fundamental results
Classes of small-world networks
Graph structure in the Web
Exploring complex networks
The structure of scientific collaboration networks
Collective dynamics of ‘small-world’ networks
Emergence of Scaling in Random Networks
The Power Structure
Some analyses of Erdős collaboration graph
Studying Social Relations Cross-Culturally
Respondent-Driven Sampling
Corporate Elite Networks and Governance Changes in the 1980s
| Unique citing works | 140 |
|---|---|
| Citations per year | 5,6 |
| Citation span | 2001 - 2026 (26) |
| Citation velocity | current |
| Highly cited | Yes |
| Citation types | Neutral: 121 |