Models of the Small World
Journal of Statistical PhysicsPublished 1 November 2000
M. E. J. Newman
Citations714
SJR quartileQ2
SJR score0.67
SNIP1.00
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A review of the six degrees of separation phenomenon, which is believed that almost any pair of people in the world can be connected to one another by a short chain of intermediate acquaintances, of typical length about six.
Abstract
It is believed that almost any pair of people in the world can be connected to one another by a short chain of intermediate acquaintances, of typical length about six. This phenomenon, colloquially referred to as the "six degrees of separation," has been the subject of considerable recent interest within the physics community. This paper provides a short review of the topic.
Keywords
MathematicsPhysics and Astronomy
NatureCollective dynamics of ‘small-world’ networks
43,160 Citations1998Duncan J. Watts, Steven H. Strogatz
Simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder are explored, finding that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs.
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Cambridge University Press eBooksSocial Network Analysis
17,041 Citations1994Stanley Wasserman, Katherine Faust
This paper presents mathematical representation of social networks in the social and behavioral sciences through the lens of dyadic and triadic interaction models, which provide insights into the structure and dynamics of relationships between actors and groups.
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
Monte Carlo Methods in Statistical Physics
3,178 Citations1999M. E. J. Newman, G. T. Barkema
Proceedings of the National Academy of SciencesClasses of small-world networks
3,086 Citations2000Luı́s A. Nunes Amaral, Antonio Scala +2 more
Evidence of the occurrence of three classes of small-world networks, characterized by a vertex connectivity distribution that decays as a power law law, and the nature of such constraints may be the controlling factor for the emergence of different classes of networks are presented.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
Physica A Statistical Mechanics and its ApplicationsMean-field theory for scale-free random networks
2,251 Citations1999Albert-Ĺaszló Barabási, Réka Albert +1 more
A mean-field method is developed to predict the growth dynamics of the individual vertices of the scale-free model, and this is used to calculate analytically the connectivity distribution and the scaling exponents.
NatureNavigation in a small world
1,711 Citations2000Jon Kleinberg
The small-world phenomenon was first investigated as a question in sociology and is a feature of a range of networks arising in nature and technology and is investigated by modelling how individuals can find short chains in a large social network.
Physical Review LettersPunctuated equilibrium and criticality in a simple model of evolution
1,524 Citations1993Per Bak, Kim Sneppen
A simple and robust model of biological evolution of an ecology of interacting species that self-organizes into a critical steady state with intermittent coevolutionary avalanches of all sizes and exhibits ``punctuated equilibrium'' behavior.
The European Physical Journal BHow popular is your paper? An empirical study of the citation distribution
1,508 Citations1998S. Redner
Physics Letters ARenormalization group analysis of the small-world network model
1,439 Citations1999M. E. J. Newman, Duncan J. Watts
It is contended that the small-world network model displays a normal continuous phase transition with a divergent correlation length as the degree of randomness tends to zero, and a real-space renormalization group transformation is proposed and demonstrated that it is exact in the limit of large system size.
Physical Review LettersStructure of Growing Networks with Preferential Linking
1,307 Citations2000S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
The model of growing networks with the preferential attachment of new links is generalized to include initial attractiveness of sites and it is shown that the relation beta(gamma-1) = 1 between the exponents is universal.
Computational and Mathematical Organization TheoryNetwork models of the diffusion of innovations
1,230 Citations1996Thomas W. Valente
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScaling and percolation in the small-world network model
1,213 Citations1999M. E. J. Newman, Duncan J. Watts
There is one nontrivial length-scale in the small-world network model of Watts and Strogatz, analogous to the correlation length in other systems, which is well-defined in the limit of infinite system size and which diverges continuously as the randomness in the network tends to zero, giving a normal critical point in this limit.
Physical Review LettersConnectivity of Growing Random Networks
1,180 Citations2000P. L. Krapivsky, S. Redner +1 more
A solution for the time- and age-dependent connectivity distribution of a growing random network is presented and the power law N(k) approximately k(-nu) is found, where the exponent nu can be tuned to any value in the range 2.
SciencePower-Law Distribution of the World Wide Web
1,018 Citations2000Lada A. Adamic, Bernardo A. Huberman
An improved version of the Erdos-Renyi (ER) theory of random networks is proposed to account for the scaling properties of a number of systems, including the link structure of the World Wide Web.
Proceedings of the Royal Society B Biological SciencesThe small world inside large metabolic networks
986 Citations2001Andreas Wagner, David A. Fell
A graph theoretical analysis of the E. coli metabolic network is found that this network is a small–world graph, a type of graph distinct from both regular and random networks and observed in a variety of seemingly unrelated areas, such as friendship networks in sociology, the structure of electrical power grids, and the nervous system of Caenorhabditis elegans.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsEpidemics and percolation in small-world networks
936 Citations2000Cristopher Moore, M. E. J. Newman
The resulting models display epidemic behavior when the infection or transmission probability rises above the threshold for site or bond percolation on the network, and are given exact solutions for the position of this threshold in a variety of cases.
The European Physical Journal BOn the properties of small-world network models
889 Citations2000Alain Barrat, Martin Weigt
Proceedings of the Royal Society B Biological SciencesThe effects of local spatial structure on epidemiological invasions
800 Citations1999Matt J. Keeling
By modelling the correlations between individuals, this work is able to understand the role of spatial heterogeneity in invasion dynamics without the need for large–scale computer simulations.
Physical Review LettersFast Response and Temporal Coherent Oscillations in Small-World Networks
574 Citations2000Luis F. Lago-Fernández, Ramón Huerta +2 more
Small-world topologies, which fall between random and regular ones, take advantage of the best features of both, giving rise to fast system response with coherent oscillations.
Physical review. B, Condensed matterScaling for first-order phase transitions in thermodynamic and finite systems
480 Citations1982Michael E. Fisher, A. Nihat Berker
Mathematical BiosciencesMeasures of concurrency in networks and the spread of infectious disease
421 Citations1996Mirjam Kretzschmar, Martina Morris
Proceedings of the National Academy of SciencesOn 1/ <i>f</i> noise and other distributions with long tails
420 Citations1982Elliott W. Montroll, Michael F. Shlesinger
A simple amplification model is introduced to characterize the transition from a log-normal distribution to an inverse-power Pareto tail.
Physical Review LettersMean-Field Solution of the Small-World Network Model
410 Citations2000Michelle G. Newman, Cristopher Moore +1 more
A mean-field solution for the average path length and for the distribution of path lengths in the small-world network model is presented, which is exact in the limit of large system size and either a large or small number of shortcuts.
Physical Review LettersSmall-World Networks: Evidence for a Crossover Picture
303 Citations1999Marc Barthélemy, Luı́s A. Nunes Amaral
The hypothesis that the appearance of small-world behavior is not a phase transition but a crossover phenomenon which depends both on the network size and on the degree of disorder is tested.
Journal de Physique IConvergent Multiplicative Processes Repelled from Zero: Power Laws and Truncated Power Laws
250 Citations1997Didier Sornette, Rama Cont
The European Physical Journal BDiffusion, localization and dispersion relations on “small-world” lattices
198 Citations1999R. Monasson
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsExact solution of site and bond percolation on small-world networks
178 Citations2000Cristopher Moore, M. E. J. Newman
An exact solution of the model for both site and bond percolation is given, including the position of thePercolation transition at which epidemic behavior sets in, the values of the critical exponents governing this transition, the mean and variance of the distribution of cluster sizes below the transition, and the size of the giant component (epidemic) above the transition.
American Journal of PhysicsRandom multiplicative processes: An elementary tutorial
160 Citations1990S. Redner
Lecture notes in computer scienceA genetic algorithm discovers particle-based computation in cellular automata
153 Citations1994Rajarshi Das, Melanie Mitchell +1 more
The emergent logic underlying these strategies are analyzed in terms of information processing performed by “particles” in space-time, and the generational progression of the GA evolution of these strategies is described.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSmall worlds: How and why
145 Citations2001Nisha Mathias, Venkatesh Gopal
This work uses simulated annealing to study the properties of a randomly rewired network as the relative tradeoff between wiring and connectivity is varied, and finds an alternate route to small-world behavior through the formation of hubs, small clusters where one vertex is connected to a large number of neighbors.
Mathematical BiosciencesThe spread and persistence of infectious diseases in structured populations
132 Citations1988Lisa Sattenspiel, Carl G. Simon
A stability analysis of the model is presented which shows that there is a unique threshold for disease maintenance, which determines critical subpopulation sizes above which the disease cannot go extinct.
Mathematical BiosciencesA mathematical model for predicting the geographic spread of new infectious agents
127 Citations1988Ira M. Longini
A mathematical model for the temporal and geographic spread of an epidemic in a network of populations is presented and the model is used to predict the spread of Hong Kong influenza in 1968–1969 among 52 of the world's major cities.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpreading and shortest paths in systems with sparse long-range connections
112 Citations1999Cristian F. Moukarzel
From this,
Journal of Mathematical BiologySusceptible-infected-removed epidemic models with dynamic partnerships
101 Citations1995Michael Altmann
The author extends the classical, stochastic, Susceptible-Infected-Removed (SIR) epidemic model to allow for disease transmission through a dynamic network of partnerships and develops a new method of analysis to analyze the model by tracking the configurations of all possible dyads, rather than individuals.
Europhysics Letters (EPL)Small-world networks and the conformation space of a short lattice polymer chain
100 Citations2001Antonio Scala, Luı́s A. Nunes Amaral +1 more
Europhysics Letters (EPL)Exactly solvable small-world network
95 Citations2000S. N. Dorogovt︠s︡ev, J. F. F. Mendes
Physica A Statistical Mechanics and its ApplicationsMean-field-type equations for spread of epidemics: the ‘small world’ model
87 Citations1999A. Kleczkowski, Bryan T. Grenfell
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsRelaxation properties of small-world networks
77 Citations2000Sune Nørhøj Jespersen, Igor M. Sokolov +1 more
This work studies diffusion processes defined on small-world networks by considering explicitly the probability for a random walker to be present at the origin.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsRandom spread on the family of small-world networks
75 Citations2001Sagar A. Pandit, R. E. Amritkar
The behavior of the average access time as a function of p shows striking similarity with that of the characteristic length of the graph, which may have important applications in routing and switching in networks with a large number of nodes.
Europhysics Letters (EPL)First-order transition in small-world networks
53 Citations2000M. Argollo de Menezes, C. F Moukarzel +1 more
The Journal of Chemical PhysicsSmall-world Rouse networks as models of cross-linked polymers
52 Citations2000S. Jespersen, I. M. Sokolov +1 more
It is shown that stretching is related to the probability of a random walker over the network to return to its origin, and this work focuses on the (structurally and thermally averaged) stretching of the SWN.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsExact results and scaling properties of small-world networks
50 Citations2000Rahul Kulkarni, Eivind Almaas +1 more
Using the general form of this distribution function for minimal paths in small-world networks, exact expressions for the average minimal distance &lmacr; and its variance sigma(2) are derived.
arXiv (Cornell University)Multiple Scales in Small-World Graphs
24 Citations1999Rajesh Kasturirangan
It is shown that the fundamental mechanism behind the small-world phenomenon is not disorder/randomness, but the presence of connections of many different length scales, and introduces the concept of multiple scale graphs and states the multiple length scale hypothesis.
arXiv (Cornell University)Evolutionary dynamics in the Bak-Sneppen model on small-world networks
21 Citations1999Rahul Kulkarni, Eivind Almaas +1 more
It is found that for a given network, the site with the minimal connectance shows long periods of stasis interrupted by much smaller periods of activity, while the activity pattern for the maximally connected site appears uniform on the same time scale.
arXiv (Cornell University)Growing network with heritable connectivity of nodes
13 Citations2000S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
The nontrivial version of this model, in which preferential linking is combined with partial inheritance of connectivity (number of incoming links) of individual nodes by new ones, is solved exactly in the limit of a large network size.
arXiv (Cornell University)Comment on ``Small-world networks: Evidence for a crossover picture''
13 Citations1999Alain Barrat