Random spread on the family of small-world networks

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPublished 20 March 2001Open access

Sagar A. Pandit, R. E. Amritkar

DOI10.1103/physreve.63.041104

Source URL

Citations75

View PDF

TL;DR

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.

Abstract

We present analytical and numerical results of a random walk on the family of small-world graphs. The average access time shows a crossover from regular to random behavior with increasing distance from the starting point of the random walk. We introduce an independent step approximation, which enables us to obtain analytic results for the average access time. We observe a scaling relation for the average access time in the degree of the nodes. The behavior of the average access time as a function of p shows striking similarity with that of the characteristic length of the graph. This observation may have important applications in routing and switching in networks with a large number of nodes.

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.

The Design and Analysis of Computer Algorithms

9,456 Citations1974Alfred V. Aho, John E. Hopcroft

This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.

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.

View PDF

ACM SIGCOMM Computer Communication ReviewUnix network programming

996 Citations1990W. Richard Stevens, T. Narten

The UNIX Model, a Practical Guide to Communication Protocols, and its Applications: A Network Primer, a Guide to Security and Performance, a guide to Performance, are reviewed.

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.

View PDF

The European Physical Journal BOn the properties of small-world network models

889 Citations2000Alain Barrat, Martin Weigt

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.

View PDF

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,

View PDF

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsCharacterization and control of small-world networks

91 Citations1999Sagar A. Pandit, R. E. Amritkar

The concept of a "faraway" connection in a network is concretized by defining a far edge, which is algorithmic and independent of any external parameters such as topology of the underlying space of the network.

View PDF

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.

View PDF