Random spreading phenomena in annealed small world networks
Physica A Statistical Mechanics and its ApplicationsPublished 1 August 2002Open access
Jani Lahtinen, János Kertész, Kimmo Kaski
Citations18
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
This work studies simple random walk dynamics in an annealed version of a small world network (SWN) consisting of N nodes by calculating the mean number of distinct sites visited and the return probability as functions of time t, and presents an approximate self-consistent solution to it.
Abstract
We study the simple random walk dynamics on an annealed version of a\nSmall-World Network (SWN) consisting of $N$ nodes. This is done by calculating\nthe mean number of distinct sites visited S(n) and the return probability\n$P_{00}(t)$ as a function of the time $t$. $S(t)$ is a key quantity both from\nthe statistical physics point of view and especially for characterizing the\nefficiency of the network connectedness. Our results for this quantity shows\nfeatures similar to the SWN with quenched disorder, but with a crossover time\nthat goes inversely proportianal to the probability $p$ of making a long range\njump instead of being proportional to $p^{-2}$ as in quenched case. We have\nalso carried out simulations on a modified annealed model where the crossover\ntime goes as $p^{-2}$ due to specific time dependent transition probabilities\nand we present an approximate self-consistent solution to it.\n
Keywords
Computer SciencePhysics 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.
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.
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.
ACM SIGCOMM Computer Communication ReviewOn power-law relationships of the Internet topology
2,599 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
The European Physical Journal BHow popular is your paper? An empirical study of the citation distribution
1,508 Citations1998S. Redner
Cambridge University Press eBooksDiffusion and Reactions in Fractals and Disordered Systems
1,379 Citations2000Daniel ben‐Avraham, Shlomo Havlin
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.
Random Walks And Random Environments
1,092 Citations1995Barry D. Hughes
Lecture notes in physicsLévy Flights and Related Topics in Physics
722 Citations1995Micheal F. Shlesinger, George M. Zaslavsky +1 more
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 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.
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 topicsLévy flights from a continuous-time process
130 Citations2000Igor M. Sokolov
Mixed models, describing normal CTRW's in superlinear operational time and Lévy flights under the operational time of subdiffusive CTRW’s lead to a paradoxical diffusive behavior, similar to the one found in transport on polymer chains.
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,
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsTarget problem on small-world networks
77 Citations2001F. Jasch, A. Blumen
This work focuses on reactions on small-world networks (SWN's), disordered graphs of much recent interest, and finds that the decay of the targets on SWN's is again related to S(n), the mean number of distinct sites visited in n steps.
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.
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 topicsScaling of random spreading in small world networks
48 Citations2001Jani Lahtinen, János Kertész +1 more
The mean number of visited sites and the return probabilities of random walks on Watts-Strogatz-type small world networks were found to obey scaling behavior with intuitively reasoned exponents as long as the probability of having a long range bond was sufficiently low.