2002 CommunityStructureInSocBioNetworks

(Girvan & Newman, 2002) ⇒ Michelle Girvan, and M. E. J. Newman. (2002). “Community Structure in Social and Biological Networks.” In: Proceedings of the National Academy of Sciences of the USA, 99(12). doi:10.1073/pnas.122653799
Subject Headings: Community Structure.

Notes

Cited By

~2,725 http://scholar.google.com/scholar?q=%22Community+structure+in+social+and+biological+networks%22+2002

Quotes

Abstract

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known — a collaboration network and a food web — and find that it detects significant and informative community divisions in both cases.

References

1. Strogatz S H. Nature (London) 2001;410:268–276. [PubMed]
2. Wasserman S, Faust K. Social Network Analysis. Cambridge, U.K.: Cambridge Univ. Press; 1994.
3. Scott J. Social Network Analysis: A Handbook. 2nd Ed. London: Sage; 2000.
4. Watts D J, Strogatz S H. Nature (London) 1998;393:440–442. [PubMed]
5. Amaral L A N, Scala A, Barthélémy M, Stanley H E. Proc Natl Acad Sci USA. 2000;97:11149–11152. [PMC free article] [PubMed]
6. Newman M E J. Proc Natl Acad Sci USA. 2001;98:404–409. [PMC free article] [PubMed]
7. Faloutsos M, Faloutsos P, Faloutsos C. Comput Commun Rev. 1999;29:251–262.
8. Albert R, Jeong H, Barabási A-L. Nature (London) 1999;401:130–131.
9. Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J. Comput Networks. 2000;33:309–320.
10. Williams R J, Martinez N D. Nature (London) 2000;404:180–183. [PubMed]
11. Jeong H, Tombor B, Albert R, Oltvai Z N, Barabási A-L. Nature (London) 2000;407:651–654. [PubMed]
12. Fell D A, Wagner A. Nat Biotechnol. 2000;18:1121–1122. [PubMed]
13. Pool I de S, Kochen M. Social Networks. 1978;1:1–48.
14. Milgram S. Psychol Today. 1967;2:60–67.
15. Barabási A-L, Albert R. Science. 1999;286:509–512. [PubMed]
16. Krapivsky P L, Redner S, Leyvraz F. Phys Rev Lett. 2000;85:4629–4632. [PubMed]
17. Dorogovtsev S N, Mendes J F F, Samukhin A N. Phys Rev Lett. 2000;85:4633–4636. [PubMed]
18. Newman M E J, Strogatz S H, Watts D J. Phys Rev E. 2001;64:026118.
19. Redner S. Eur Phys J B. 1998;4:131–134.
20. Menger K. Fundamenta Mathematicae. 1927;10:96–115.
21. White D R, Harary F. Sociol Methodol. 2001;31:305–359.
22. Ahuja R K, Magnanti T L, Orlin J B. Network Flows: Theory, Algorithms, and Applications. Upper Saddle River, NJ: Prentice–Hall; 1993.
23. Katz L. Psychometrika. 1953;18:39–43.
24. Freeman L. Sociometry. 1977;40:35–41.
25. Newman M E J. Phys Rev E. 2001;64:016131.
26. Zachary W W. J Anthropol Res. 1977;33:452–473.
27. Baird D, Ulanowicz R E. Ecol Monogr. 1989;59:329–364.
28. Yodzis P, Winemiller K O. Oikos. 1999;87:327–340.
29. Martinez N D. Am Nat. 1992;139:1208–1218.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2002 CommunityStructureInSocBioNetworks	M. E. J. Newman Michelle Girvan			Community Structure in Social and Biological Networks		Proceedings of the National Academy of Sciences of the USA	http://arxiv.org/PS cache/cond-mat/pdf/0112/0112110v1.pdf	10.1073/pnas.122653799		2002