Evolving networks with distance preferences
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPublished 24 September 2002Open access
Jürgen Jost, M. P. Joy
Citations86
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
Simulation results for network parameters like the first eigenvalue of the graph Laplacian, clustering coefficients, average distances, and degree distributions for different distance preferences and compare them with the parameter values for random and scale-free networks find that for the shortest distance rule, a power-law degree distribution is obtained.
Abstract
We study evolving networks where new nodes when attached to the network form links with other nodes of preferred distances. A particular case is where always the shortest distances are selected ("make friends with the friends of your present friends"). We present simulation results for network parameters like the first eigenvalue of the graph Laplacian (synchronizability), clustering coefficients, average distances, and degree distributions for different distance preferences and compare them with the parameter values for random and scale-free networks. We find that for the shortest distance rule we obtain a power-law degree distribution as in scale-free networks, while the other parameters are significantly different, especially the clustering coefficient.
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.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
NatureExploring complex networks
8,339 Citations2001Steven H. Strogatz
This work aims to understand how an enormous network of interacting dynamical systems — be they neurons, power stations or lasers — will behave collectively, given their individual dynamics and coupling architecture.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsRandom graphs with arbitrary degree distributions and their applications
3,644 Citations2001M. E. J. Newman, Steven H. Strogatz +1 more
It is demonstrated 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.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsClustering and preferential attachment in growing networks
2,047 Citations2001M. E. J. Newman
It is shown that the probability of a pair of scientists collaborating increases with the number of other collaborators they have in common, and that the probabilities of a particular scientist acquiring new collaborators increases withThe number of his or her past collaborators.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsGrowing scale-free networks with tunable clustering
1,097 Citations2002Petter Holme, Beom Jun Kim
The standard scale-free network model is extended to include a "triad formation step" and the clustering coefficient is shown to be tunable simply by changing a control parameter---the average number of triad formation trials per time step.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsOrganization of growing random networks
894 Citations2001P. L. Krapivsky, S. Redner
The organizational development of growing random networks is investigated, and the combined age and degree distribution of nodes shows that old nodes typically have a large degree.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsStructure of growing social networks
500 Citations2001Emily Jin, Michelle Girvan +1 more
Using computer simulations, it is found that models that incorporate all of these features reproduce many of the features of real social networks, including high levels of clustering or network transitivity and strong community structure in which individuals have more links to others within their community than to individuals from other communities.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectra of “real-world” graphs: Beyond the semicircle law
481 Citations2001Illés J. Farkas, Imre Derényi +2 more
Methods to determine the eigenvalues of networks comparable in size to real systems are developed, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsHighly clustered scale-free networks
391 Citations2002Konstantin Klemm, Vı́ctor M. Eguı́luz
The model shows stylized features of real-world networks: power-law distribution of degree, linear preferential attachment of new links, and a negative correlation between the age of a node and its link attachment rate.
Proceedings of the National Academy of SciencesCurvature of co-links uncovers hidden thematic layers in the World Wide Web
353 Citations2002Jean‐Pierre Eckmann, Elisha Moses
It is demonstrated here how thematic relationships can be located precisely by looking only at the graph of hyperlinks, gleaning content and context from the Web without having to read what is in the pages.
Physical Review LettersEmergence of a Small World from Local Interactions: Modeling Acquaintance Networks
312 Citations2002Jörn Davidsen, Holger Ebel +1 more
Here, it is demonstrated that this assumption is sufficient to reproduce major nontrivial features of social networks: short path length, high clustering, and scale-free or exponential link distributions.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSize-dependent degree distribution of a scale-free growing network
304 Citations2001S. N. Dorogovt︠s︡ev, J. F. F. Mendes +1 more
The simplest model of scale-free growing networks is proposed and it is demonstrated that a trace of initial conditions - a hump near cutoff of the degree distribution at k(cut) approximately t(beta)--may be found for any network size.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectral properties and synchronization in coupled map lattices
273 Citations2001Jürgen Jost, M. P. Joy
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectra and eigenvectors of scale-free networks
241 Citations2001K.-I. Goh, B. Kahng +1 more
The spectral density shows an exponential decay around the center, followed by power-law long tails at both spectrum edges, and the mass gap scales as N(-0.68) and the component of the normalized eigenfunction at the hub is of order unity.
Physics Letters AStability of synchronized chaos in coupled dynamical systems
145 Citations2002Govindan Rangarajan, Mingzhou Ding