×

Community structure in social and biological networks. (English) Zbl 1032.91716

Summary: 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.

MSC:

91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Strogatz, Nature; Physical Science (London) 410 (6825) pp 268– (2001) · Zbl 1370.90052
[2] Watts, Nature; Physical Science (London) 393 (6684) pp 440– (1998) · Zbl 1368.05139
[3] PNAS 97 (21) pp 11149– (2000)
[4] Newman, PNAS 98 (2) pp 404– (2001)
[5] COMPUT COMMUN REV 29 pp 251– (1999)
[6] COMPUT NETWORKS 33 pp 309– (2000)
[7] Williams, Nature; Physical Science (London) 404 (6774) pp 180– (2000)
[8] Jeong, Nature; Physical Science (London) 407 (6804) pp 651– (2000)
[9] Fell, Nature biotechnology 18 (11) pp 1121– (2000)
[10] 1 pp 1– (1978)
[11] 2 pp 60– (1967)
[12] Barabasi, Science 286 (5439) pp 509– (1999) · Zbl 1226.05223
[13] Krapivsky, Physical Review Letters 85 (21) pp 4629– (2000)
[14] Dorogovtsev, Physical Review Letters 85 (21) pp 4633– (2000)
[15] PHYS REV E 64 pp 026118– (2001)
[16] EUR. PHYS. J. B 4 pp 131– (1998)
[17] FUNDAMENTA MATHEMATICAE 10 pp 96– (1927)
[18] Sociological Methodology 31 pp 305– (2001)
[19] Psychometrika 18 pp 39– (1953) · Zbl 0053.27606
[20] Sociometry 40 pp 35– (1977)
[21] PHYS REV E 64 pp 016131– (2001)
[22] 33 pp 452– (1977)
[23] Ecological Monographs 59 pp 329– (1989)
[24] Oikos 87 pp 327– (1999)
[25] 139 pp 1208– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.