Maps of random walks on complex networks reveal community structure

Martin Rosvall and Carl T. Bergstrom
PNAS January 29, 2008 105 (4) 1118-1123; https://doi.org/10.1073/pnas.0706851105

  1. Edited by Brian Skyrms, University of California, Irvine, CA, and approved December 10, 2007 (received for review July 21, 2007)

Abstract

To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network—including physics, chemistry, molecular biology, and medicine—information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.

Footnotes

  • †To whom correspondence should be addressed. E-mail: rosvall{at}u.washington.edu

  • Author contributions: M.R. and C.T.B. designed research, performed research, and wrote the paper.

  • The authors declare no conflict of interest.

  • This article is a PNAS Direct Submission.

  • This article contains supporting information online at www.pnas.org/cgi/content/full/0706851105/DC1.

  • Freely available online through the PNAS open access option.

References

  1. ↵
    1. Newman MEJ
    (2003) SIAM Review 45:167–256.
    OpenUrlCrossRef
  2. ↵
    1. Newman MEJ,
    2. Barabási AL,
    3. Watts DJ
    (2006) The Structure and Dynamics of Networks (Princeton Univ Press, Princeton, NJ).
  3. ↵
    1. Girvan M,
    2. Newman MEJ
    (2002) Proc Natl Acad Sci USA 99:7821–7826.
    OpenUrlAbstract/FREE Full Text
  4. ↵
    1. Palla G,
    2. Derényi I,
    3. Farkas I,
    4. Vicsek T
    (2005) Nature 435:814–818.
    OpenUrlCrossRefPubMed
  5. ↵
    1. Sales-Pardo M,
    2. Guimerà R,
    3. Moreira AA,
    4. Amaral LAN
    (2007) Proc Natl Acad Sci USA 104:15224.
    OpenUrlAbstract/FREE Full Text
  6. ↵
    1. Guimerà R,
    2. Amaral LAN
    (2005) Nature 433:895–900.
    OpenUrlCrossRefPubMed
  7. ↵
    1. Tufte ER
    (2006) Beautiful Evidence (Graphics, Cheshire, CT).
  8. ↵
    1. Ziv E,
    2. Middendorf M,
    3. Wiggins CH
    (2005) Phys Rev E 71:046117.
    OpenUrlCrossRef
  9. ↵
    1. Donath WE,
    2. Hoffman A
    (1972) IBM Tech Discl Bull 15:938–944.
    OpenUrl
  10. ↵
    1. Enright AJ,
    2. Van Dongen S,
    3. Ouzounis CA
    (2002) Nucleic Acids Res 30:1575–1584.
    OpenUrlAbstract/FREE Full Text
  11. ↵
    1. Newman MEJ,
    2. Girvan M
    (2004) Phys Rev E 69:026113.
    OpenUrlCrossRef
  12. ↵
    1. Eriksen KA,
    2. Simonsen I,
    3. Maslov S,
    4. Sneppen K
    (2003) Phys Rev Lett 90:148701.
    OpenUrlCrossRefPubMed
  13. ↵
    1. Shannon CE,
    2. Weaver W
    (1949) The Mathematical Theory of Communication (Univ of Illinois Press, Champaign, IL).
  14. ↵
    1. Rissanen J
    (1978) Automatica 14:465–471.
    OpenUrlCrossRef
  15. ↵
    1. Grünwald P,
    2. Myung IJ,
    3. Pitt M
    , eds (2005) Advances in Minimum Description Length: Theory and Applications (MIT Press, London).
  16. ↵
    1. Rosvall M,
    2. Bergstrom CT
    (2007) Proc Natl Acad Sci USA 104:7327–7331.
    OpenUrlAbstract/FREE Full Text
  17. ↵
    1. Shannon CE
    (1948) Bell Labs Tech J 27:379–423.
    OpenUrl
  18. ↵
    1. Huffman D
    (1952) Proc Inst Radio Eng 40:1098–1102.
    OpenUrl
  19. ↵
    1. Zipf GK
    (1949) Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology (Addison-Wesley, Cambridge, MA).
  20. ↵
    1. Clauset A,
    2. Newman MEJ,
    3. Moore C
    (2004) Phys Rev E 70:066111.
    OpenUrlCrossRef
  21. ↵
    1. Wakita K,
    2. Tsurumi T
    (2007) arXiv:cs/0702048.
  22. ↵
    1. Brin S,
    2. Page L
    (1998) Comp Networks ISDN Sys 33:107–117.
    OpenUrl
  23. ↵
    1. Newman MEJ
    (2004) Phys Rev E 69:066133.
    OpenUrlCrossRef
  24. ↵
    1. Guimerà R,
    2. Sales-Pardo M,
    3. Amaral LAN
    (2007) Phys Rev E 76:036102.
    OpenUrlCrossRef
  25. ↵
    1. Leicht EA,
    2. Newman MEJ
    (2007) arXiv:0709.4500.
  26. ↵
    1. Arenas A,
    2. Duch J,
    3. Fernández A,
    4. Gómez S
    (2007) New J Phys 9:176.
    OpenUrlCrossRef
  27. ↵
    1. de Solla Price DJ
    (1965) Science 149:510–515.
    OpenUrlFREE Full Text
  28. ↵
    1. Small H
    (1973) J Am Soc Inf Sci 24:265–269.
    OpenUrlCrossRef
  29. ↵
    1. Small H
    (1999) J Am Soc Inf Sci 50:799–813.
    OpenUrlCrossRef
  30. ↵
    1. Moya-Anegón F,
    2. Vargas-Quesada1 B,
    3. Herrero-Solana V,
    4. Chinchilla-Rodríguez Z,
    5. Corera-Álvarez E,
    6. Munoz-Fernández FJ
    (2004) Scientometrics 61:129–145.
    OpenUrlCrossRef
  31. ↵
    1. Shiffrin RM,
    2. Börner K
    (2004) Proc Natl Acad Sci USA 101:5183–5185.
    OpenUrlFREE Full Text
  32. ↵
    1. Institute for Scientific Information
    (2004) Journal Citation Reports (Thompson Scientific, Philadelphia, PA).
View Full Text
Back to top
Article Alerts
Email Article
Citation Tools
Request Permissions
Maps of random walks on complex networks reveal community structure
Martin Rosvall, Carl T. Bergstrom
Proceedings of the National Academy of Sciences Jan 2008, 105 (4) 1118-1123; DOI: 10.1073/pnas.0706851105
del.icio.us logo Digg logo Reddit logo Twitter logo CiteULike logo Facebook logo Google logo Mendeley logo
Proceedings of the National Academy of Sciences: 116 (25)
Current Issue

Submit

Jump to section

You May Also be Interested in

Tidewater glacier in Southeast Greenland, summer of 2018. Image courtesy of Eric Rignot.
Loss of Greenland Ice Sheet mass
Since 1972, ice loss from Greenland has contributed to an estimated 13.7 mm rise in global sea level, with the largest contributions coming from northwest, southeast, and central west Greenland, according to a study.
Image courtesy of Eric Rignot.
The change in annual surface air temperature resulting from historical anthropogenic climate forcing. Image courtesy of Noah S. Diffenbaugh and Marshall Burke.
Economic inequality and global warming
Global warming has likely increased the economic disparity between the top and bottom population deciles across the world, thereby generating greater economic inequality than would have occurred without global warming, according to a study.
Image courtesy of Noah S. Diffenbaugh and Marshall Burke.
Soldier nymphs of Nipponaphis monzeni repairing a gall breach by discharging coagulating body fluid. Image courtesy of Mayako Kutsukake.
Social aphids defend colonies against predators
Some species of aphids use a form of social defense to protect colonies from predators, uncovering potential molecular clues to the evolutionary roots of altruistic social defense, according to a study.
Image courtesy of Mayako Kutsukake.
QnAs with NAS member and materials scientist Stephen Forrest
Featured QnAs
QnAs with NAS member and materials scientist Stephen Forrest
Image courtesy of Michigan Photography, University of Michigan.

More Articles of This Classification

Related Content

Cited by...

Similar Articles