Discrete small world networks

Andrew D Barbour (University of Zurich)
Gesine D Reinert (University of Oxford)

Abstract


Small world models are networks consisting of many local links and fewer long range `shortcuts', used to model networks with a high degree of local clustering but relatively small diameter. Here, we concern ourselves with the distribution of typical inter-point network distances. We establish approximations to the distribution of the graph distance in a discrete ring network with extra random links, and compare the results to those for simpler models, in which the extra links have zero length and the ring is continuous.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1234-1283

Publication Date: December 15, 2006

DOI: 10.1214/EJP.v11-381

References

  1. R. Albert, A.-L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics 74 (2002), 47ñ97. Math. Review 1895096
  2. S. Asmussen, H. Hering. Branching Processes. Birkhauser, Basel (1983). Math. Review 0701538
  3. K.B. Athreya, P.E. Ney. Branching Processes. Springer, New York (1972). Math. Review 0373040
  4. F. Ball, D. Mollison, and G. Scalia-Tomba. Epidemics with two levels of mixing. Ann. Appl. Probab. 7 (1997), 46-89. Math. Review 1428749
  5. A.-L. Barabasi. Linked: the new science of networks. Perseus, Cambridge, Mass. (2002). Math. Review not available.
  6. A.D. Barbour. L. Holst, and S. Janson. Poisson Approximation. Oxford University Press (1992). Math. Review 1163825
  7. A.D. Barbour, G. Reinert. Small Worlds. Random Structures and Algorithms 19 (2001), 54ñ74. Math. Review 1848027. Correction: ibid 25, 115 (2004). Math. Review 184802751
  8. S.N. Dorogovtsev, J.F.F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press (2003). Math. Review 1993912
  9. E.J. Gumbel. Statistics of extremes. Columbia University Press (1958). Math. Review 0096342
  10. T.E. Harris. The Theory of Branching Processes. Dover, New York (1989). Math. Review 1991122
  11. S. Janson. One, two and three times log n/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 (1999), 347ñ361. Math. Review 1723648
  12. M.E.J. Newman, D.J. Watts. Scaling and percolation in the smallworld network model. Phys. Rev. E. 60 (1999), 7332-7344. Math. Review number not available.
  13. M.E.J. Newman, C, Moore, and D.J. Watts. Mean-field solution of the small-world network model. Phys. Rev. Lett. 84 (2000), 3201ñ3204. Math. Review number not available.
  14. D.J. Watts. Small Worlds. Princeton University Press (1999). Math. Review 1716136
  15. D.J. Watts, S.H. Strogatz. Collective dynamics of ìsmall-worldî networks. Nature 393 (1998), 440ñ442. Math. Review number not available.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.