An information-theoretic framework for resolving community structure in complex networks

Edited by Brian Skyrms, University of California, Irvine, CA, and approved March 12, 2007
May 1, 2007
104 (18) 7327-7331

Abstract

To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks.

Continue Reading

Acknowledgments

We thank Ben Althouse for generating the network used in Fig. 3 and Mark Newman for constructive comments on the manuscript. This work was supported by National Institute of General Medical Sciences Models of Infectious Disease Agent Study Program Cooperative Agreement 5U01GM07649.

References

1
LC Freeman Am J Sociol 98, 152–166 (1992).
2
K Eriksen, I Simonsen, S Maslov, K Sneppen Phys Rev Lett 90, 148701 (2003).
3
LH Hartwell, JJ Hopfield, S Leibler, AW Murray Nature 402, C47–C52 (1999).
4
EA Variano, JH McCoy, H Lipson Phys Rev Lett 92, 188701 (2004).
5
M Girvan, MEJ Newman Proc Natl Acad Sci USA 99, 7821–7826 (2002).
6
G Palla, I Derényi, I Farkas, T Vicsek Nature 435, 814–818 (2005).
7
R Guimerà, LAN Amaral Nature 433, 895–900 (2005).
8
P Holme, M Huss, H Jeong Bioinformatics 19, 532–538 (2003).
9
MEJ Newman Eur Phys J B 38, 321–330 (2004).
10
L Danon, A Díaz-Guilera, J Duch, A Arenas J Stat Mech, pp. P09008 (2005).
11
CE Shannon, W Weaver The Mathematical Theory of Communication (Univ of Illinois Press, Champaign, 1949).
12
J Rissanen Automatica 14, 465–471 (1978).
13
E Ziv, M Middendorf, CH Wiggins Phys Rev E 71, 046117 (2005).
14
D Lusseau, K Schneider, OJ Boisseau, P Haase, E Slooten, SM Dawson Behav Ecol Sociobiol 54, 396–405 (2003).
15
MEJ Newman, M Girvan Phys Rev E 69, 026113 (2004).
16
MEJ Newman Phys Rev E 69, 066133 (2004).
17
MEJ Newman Proc Natl Acad Sci USA 103, 8577–8582 (2006).
18
J Reichardt, S Bornholdt Phys Rev E 74, 016110 (2006).
19
S Fortunato, M Barthélemy Proc Natl Acad Sci USA 104, 36–41 (2007).
20
R Guimerà, LAN Amaral J Stat Mech, pp. P02001 (2005).
21
A Barron, J Rissanen, B Yu IEEE Trans Inf Theory 44, 2743–2760 (1998).
22
, eds P Grünwald, IJ Myung, M Pitt (MIT Press, Cambridge, MA Advances in Minimum Description Length: Theory and Applications, Chap 1 and 2. (2005).
23
R Guimerà, M Sales-Pardo, LAN Amaral Phys Rev E 70, 025101. (2004).
24
J Reichardt, S Bornholdt Physica D 224, 20–26 (2006).
25
N Kashtan, U Alon Proc Natl Acad Sci USA 102, 13773–13778 (2005).
26
S Wasserman, K Faust Social Network Analysis: Methods and Applications (Cambridge Univ Press, Cambridge, UK, 1994).
27
F Radicchi, C Castellano, F Cecconi, V Loreto, D Parisi Proc Natl Acad Sci USA 101, 2658–2663 (2004).
28
MEJ Newman, EA Leicht, arXiv:physics/0611158.
29
WW Zachary J Anthropol Res 33, 452–473 (1977).
30
A Clauset, MEJ Newman, C Moore Phys Rev E 70, 066111 (2004).
31
MEJ Newman Phys Rev E 74, 036104 (2006).
32
Journal Citation Reports (Thompson Scientific, Philadelphia, 2004).

Information & Authors

Information

Published in

Go to Proceedings of the National Academy of Sciences
Proceedings of the National Academy of Sciences
Vol. 104 | No. 18
May 1, 2007
PubMed: 17452639

Classifications

Submission history

Received: December 13, 2006
Published online: May 1, 2007
Published in issue: May 1, 2007

Keywords

  1. clustering
  2. compression
  3. information theory

Acknowledgments

We thank Ben Althouse for generating the network used in Fig. 3 and Mark Newman for constructive comments on the manuscript. This work was supported by National Institute of General Medical Sciences Models of Infectious Disease Agent Study Program Cooperative Agreement 5U01GM07649.

Notes

This article is a PNAS Direct Submission.

Authors

Affiliations

Martin Rosvall [email protected]
Department of Biology, University of Washington, Seattle, WA 98195-1800
Carl T. Bergstrom
Department of Biology, University of Washington, Seattle, WA 98195-1800

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

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

Cited by

    Loading...

    View Options

    View options

    PDF format

    Download this article as a PDF file

    DOWNLOAD PDF

    Get Access

    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

    An information-theoretic framework for resolving community structure in complex networks
    Proceedings of the National Academy of Sciences
    • Vol. 104
    • No. 18
    • pp. 7309-7729

    Media

    Figures

    Tables

    Other

    Share

    Share

    Share article link

    Share on social media