[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Calculating statistics of complex networks through random walks with an application to the on-line social network Bebo

  • Topical issue on The Physics Approach to Risk: Agent-Based Models and Networks
  • Published:
The European Physical Journal B Aims and scope Submit manuscript

Abstract

We develop a methodology with which to calculate typical network statistics by sampling a network through a random walk. By examining the statistics of degree and return times of walks which return to the same vertex, we can estimate characteristics of the giant component such as average clustering coefficient, degree distribution, degree correlations and network size. We confirm the validity of the methods using a variety of available network network data sets and then apply these methods to data collected by performing a random walk on the large on-line social networking website, Bebo. We find good agreement between our results and the results of previous studies of on-line social networks in which data collection was performed by a BFS (“snow-ball”) sampling algorithm. In particular, we find that the degree distribution exhibits a multi-scaling power-law tail and the network exhibits clustering and positive degree correlations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Kumar, J. Novak, A. Tomkins, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining (2006), pp. 611–617

  2. J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (2008), pp. 462–470

  3. F. Fu, L. Liu, L. Wang, Physica A 387, 675 (2008)

    Article  ADS  Google Scholar 

  4. Y.Y. Ahn, S. Han, H. Kwak, S. Moon, H. Jeong, Proceedings of the 16th international conference on World Wide Web (2007), pp. 835–844

  5. A. Mislove, H.S. Koppula, K.P. Gummadi, P. Druschel, B. Bhattacharjee, Proceedings of the first workshop on Online social networks (2008), pp. 25–30

  6. S.H. Lee, P.J. Kim, H. Jeong, Phys. Rev. E 73, 016102 (2006)

    Article  ADS  Google Scholar 

  7. M.R. Henzinger, A. Heydon, M. Mitzenmacher, M. Najork, Proceedings of the 9th international Conference on World Wide Web (2000), pp. 295–308

  8. P. Pons, M. Latapy, Lect. Notes Comput. Sci. 3733/2005, 284 (2005)

    Article  Google Scholar 

  9. R. Lambiotte, J.C. Delvenne, M. Barahona (2009), e-print arXiv:0812.1770

  10. J.D. Noh, H. Rieger, Phys. Rev. Lett. 92, 118701 (2004)

    Article  ADS  Google Scholar 

  11. D.J. Watts, S.H. Strogatz, Nature (London) 393, 440 (1998)

    Article  ADS  Google Scholar 

  12. M.E.J. Newman, J. Park, Phys. Rev. E 68, 036122 (2003)

    Article  ADS  Google Scholar 

  13. G. Caldarelli, Scale-Free Networks, complex webs in nature and technology, Oxford University Press (2007), p. 27

  14. M.E.J. Newman, Proc. Natl. Acad. Scie. USA 98, 404 (2001)

    Article  MATH  ADS  Google Scholar 

  15. A.L. Barabási, R. Albert, Science 286, 509 (1999)

    Article  MathSciNet  Google Scholar 

  16. H. Jeong, S.P. Mason, A.L. Barabási, Z.N. Oltvai, Nature 411, 41 (2001)

    Article  ADS  Google Scholar 

  17. R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, A. Arenas, Phys. Rev. E 68, 065103 (2003)

    Article  ADS  Google Scholar 

  18. R. Albert, H. Jeong, A.L. Barabási, Nature (London) 401, 130 (1999)

    Article  ADS  Google Scholar 

  19. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Computer Networks 33, 309 (2000)

    Article  Google Scholar 

  20. H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A.L. Barabási, Nature 407, 651 (2000)

    Article  ADS  Google Scholar 

  21. G. Caneva, M. Cutini, A. Pacini, M. Vinci, Plant Biosystems 136, 291 (2002)

    Google Scholar 

  22. A.L. Barabási, R. Albert, Science 286, 509 (1999)

    Article  MathSciNet  Google Scholar 

  23. A.L. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, T. Vicsek, Physica A 311, 590 (2002)

    Article  MATH  MathSciNet  ADS  Google Scholar 

  24. J.P. Onnela, J. Saramaki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, A.L. Barabási, Proc. Natl. Acad. Sci. 104, 7332 (2007)

    Article  ADS  Google Scholar 

  25. E. Ravasz, A.L. Barabási, Phys. Rev. E 67, 026112 (2003)

    Article  ADS  Google Scholar 

  26. International Herald Tribune, AOL to buy social networking site Bebo (March 13, 2008)

  27. http://www.livejournal.com/

  28. http://www.myspace.com/

  29. http://www.bebo.com/

Download references

Author information

Authors and Affiliations

  1. School of Physics, Trinity College Dublin, Dublin, Ireland

    S. J. Hardiman, P. Richmond & S. Hutzler

Authors
  1. S. J. Hardiman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Richmond
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Hutzler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. J. Hardiman.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hardiman, S., Richmond, P. & Hutzler, S. Calculating statistics of complex networks through random walks with an application to the on-line social network Bebo. Eur. Phys. J. B 71, 611–622 (2009). https://doi.org/10.1140/epjb/e2009-00292-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1140/epjb/e2009-00292-2

PACS

Search

Navigation