Maps of random walks on complex networks reveal community structure

Edited by Brian Skyrms, University of California, Irvine, CA, and approved December 10, 2007
January 29, 2008
105 (4) 1118-1123

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.

Continue Reading

ACKNOWLEDGMENTS.

We are grateful to Jevin West for processing the data used to construct the maps in Figs. 3 and 4 and to Cynthia A. Brewer, www.ColorBrewer.org, for providing the color schemes we have used in Figs. 1–4. This work was supported by the National Institute of General Medical Sciences Models of Infectious Disease Agent Study Program Cooperative Agreement 5U01GM07649.

Supporting Information

Adobe PDF - 06851SuppAppendix.pdf
Adobe PDF - 06851SuppAppendix.pdf

References

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

Information & Authors

Information

Published in

The cover image for PNAS Vol.105; No.4
Proceedings of the National Academy of Sciences
Vol. 105 | No. 4
January 29, 2008
PubMed: 18216267

Classifications

Submission history

Received: July 21, 2007
Published online: January 29, 2008
Published in issue: January 29, 2008

Keywords

  1. clustering
  2. compression
  3. information theory
  4. map of science
  5. bibiometrics

Acknowledgments

We are grateful to Jevin West for processing the data used to construct the maps in Figs. 3 and 4 and to Cynthia A. Brewer, www.ColorBrewer.org, for providing the color schemes we have used in Figs. 1–4. This work was supported by the National Institute of General Medical Sciences Models of Infectious Disease Agent Study Program Cooperative Agreement 5U01GM07649.

Notes

This article is a PNAS Direct Submission.
This article contains supporting information online at www.pnas.org/cgi/content/full/0706851105/DC1.

Authors

Affiliations

Martin Rosvall [email protected]
Department of Biology, University of Washington, Seattle, WA 98195-1800; and
Carl T. Bergstrom
Department of Biology, University of Washington, Seattle, WA 98195-1800; and
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501

Notes

To whom correspondence should be addressed. E-mail: [email protected]
Author contributions: M.R. and C.T.B. designed research, performed research, and wrote the paper.

Competing Interests

The authors declare no conflict of interest.

Metrics & Citations

Metrics

Note: The article usage is presented with a three- to four-day delay and will update daily once available. Due to ths delay, usage data will not appear immediately following publication. Citation information is sourced from Crossref Cited-by service.


Citation statements

Altmetrics

Citations

Export the article citation data by selecting a format from the list below and clicking Export.

Cited by

    Loading...

    View Options

    View options

    PDF format

    Download this article as a PDF file

    DOWNLOAD PDF

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Personal login Institutional Login

    Recommend to a librarian

    Recommend PNAS to a Librarian

    Purchase options

    Purchase this article to access the full text.

    Single Article Purchase

    Maps of random walks on complex networks reveal community structure
    Proceedings of the National Academy of Sciences
    • Vol. 105
    • No. 4
    • pp. 1099-1386

    Figures

    Tables

    Media

    Share

    Share

    Share article link

    Share on social media