Maps of random walks on complex networks reveal community structure
Edited by Brian Skyrms, University of California, Irvine, CA, and approved December 10, 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.
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
- Download
- 841.22 KB
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
Classifications
Copyright
© 2008 by The National Academy of Sciences of the USA. Freely available online through the PNAS open access option.
Submission history
Received: July 21, 2007
Published online: January 29, 2008
Published in issue: January 29, 2008
Keywords
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
Competing Interests
The authors declare no conflict of interest.
Metrics & Citations
Metrics
Citation statements
Altmetrics
Citations
Cite this article
Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. U.S.A.
105 (4) 1118-1123,
https://doi.org/10.1073/pnas.0706851105
(2008).
Copied!
Copying failed.
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 PDFLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.