2002 CommunityStructureInSocBioNetworks: Difference between revisions

Latest revision as of 07:26, 22 August 2024

(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

@@ Line 16: / Line 16: @@
 ===Introduction===
-Many systems take the form of [[Graph|networks]], [[Set|sets]] of [[Graph Node|nodes or vertice]]s joined together in [[Tuple|pairs]] by [[Graph Link|links or edges]] (1). Examples include [[social networks]] (2–4) such as [[acquaintance network]]s (5) and [[collaboration network]]s (6), [[technological network]]s such as [[the Internet]] (7), [[the Worldwide Web]] (8, 9), and [[power grid]]s (4, 5), and [[biological network]]s such as [[neural network]]s (4), [[food web]]s (10), and [[metabolic network]]s (11, 12). Recent research on networks among mathematicians and [[physicist]]s has focused on a number of distinctive statistical properties that most networks seem to share. One such property is the “[[small world effect]],” which is the name given to the finding that the average distance between vertices in a network is short (13, 14), usually scaling logarithmically with the total number n of [[vertice]]s. Another is the [[right-skewed degree distributions]] that many [[networks]] possess (8, 9, 15–17). The [[Graph Node Degree|Node degree of a vertex]] in a [[network]] is the [[number]] of other [[vertice]]s to which it is [[connected]], and one finds that there are typically many vertices in a network with low degree and a small number with high degree, the precise distribution often following a [[power-law]] or [[exponential form]] (1, 5, 15).
+Many systems take the form of [[Graph|networks]], [[Set|sets]] of [[Graph Node|nodes or vertice]]s joined together in [[Tuple|pairs]] by [[Graph Link|links or edges]] (1). Examples include [[social networks]] (2–4) such as [[acquaintance network]]s (5) and [[collaboration network]]s (6), [[technological network]]s such as [[the Internet]] (7), [[the Worldwide Web]] (8, 9), and [[power grid]]s (4, 5), and [[biological network]]s such as [[neural network]]s (4), [[food web]]s (10), and [[metabolic network]]s (11, 12). Recent research on networks among mathematicians and [[physicist]]s has focused on a number of distinctive statistical properties that most networks seem to share. One such property is the “[[small world effect]],” which is the name given to the finding that the average distance between vertices in a network is short (13, 14), usually scaling logarithmically with the total number n of [[vertice]]s. Another is the [[right-skewed degree distribution]]s that many [[networks]] possess (8, 9, 15–17). The [[Graph Node Degree|Node degree of a vertex]] in a [[network]] is the [[number]] of other [[vertice]]s to which it is [[connected]], and one finds that there are typically many vertices in a network with low degree and a small number with high degree, the precise distribution often following a [[power-law]] or [[exponential form]] (1, 5, 15).
 A third property that many networks have in common is [[Network Transitivity|clustering, or network transitivity,]] which is the [[property]] that [[two]] [[vertice]]s that are both [[neighbors]] of the same third [[vertex]] have a [[heightened]] [[probability]] of also being neighbors of one another. In the language of social networks, two of your [[friend]]s will have a greater probability of knowing one another than will two people chosen at random from the population, on account of their common acquaintance with you. This effect is quantified by the [[clustering coefficient]] C (4, 18), defined by
@@ Line 24: / Line 24: @@
 This number is precisely the probability that two of one's [[friend]]s are [[friend]]s themselves. It is 1 on a [[fully connected graph]] (everyone knows everyone else) and has typical values in the range of 0.1 to 0.5 in many [[real-world network]]s.
-In [[2002_CommunityStructureInSocBioNetworks|this article]], [[we]] consider another property, which, as we will show, appears to be common to many networks, the property of [[Community Structure|community structure]]. (This property is also sometimes called [[clustering]], but we refrain from this usage to avoid confusion with the other meaning of the word [[clustering]] introduced in the preceding paragraph.) Consider for a moment the case of [[Social Networks|social networks]] — [[Network|networks]] of [[Friendship|friendships]] or other [[Acquaintance|acquaintance]]s between [[Person|individuals]]. It is a matter of common experience that such networks seem to have [[communities]] in them: [[subsets]] of [[Network Vertex|vertice]]s within which [[vertex–vertex connections]] are [[Dense Graph|dense]], but between which connections are less dense. A figurative sketch of a network with such a community structure is shown in Fig. Fig.1.1. (Certainly it is possible that the communities themselves also join together to form metacommunities, and that those metacommunities are themselves joined together, and so on in a hierarchical fashion. This idea is discussed further in the next section.) The ability to detect community structure in a network could clearly have [[practical application]]s. Communities in a social network might represent real social groupings, perhaps by interest or background; communities in a citation network (19) might represent related papers on a single topic; communities in a metabolic network might represent cycles and other functional groupings; communities on the web might represent pages on related topics. Being able to identify these communities could help us to understand and exploit these networks more effectively.
+In [[2002_CommunityStructureInSocBioNetworks|this article]], [[we]] consider another property, which, as we will show, appears to be common to many networks, the property of [[Community Structure|community structure]]. (This property is also sometimes called [[clustering]], but we refrain from this usage to avoid confusion with the other meaning of the word [[clustering]] introduced in the preceding paragraph.) Consider for a moment the case of [[Social Networks|social networks]] — [[Network|networks]] of [[Friendship|friendships]] or other [[Acquaintance|acquaintance]]s between [[Person|individuals]]. It is a matter of common experience that such networks seem to have [[communities]] in them: [[subsets]] of [[Network Vertex|vertice]]s within which [[vertex–vertex connection]]s are [[Dense Graph|dense]], but between which connections are less dense. A figurative sketch of a network with such a community structure is shown in Fig. Fig.1.1. (Certainly it is possible that the communities themselves also join together to form metacommunities, and that those metacommunities are themselves joined together, and so on in a hierarchical fashion. This idea is discussed further in the next section.) The ability to detect community structure in a network could clearly have [[practical application]]s. Communities in a social network might represent real social groupings, perhaps by interest or background; communities in a citation network (19) might represent related papers on a single topic; communities in a metabolic network might represent cycles and other functional groupings; communities on the web might represent pages on related topics. Being able to identify these communities could help us to understand and exploit these networks more effectively.
 }}
 == 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.