×

Mixture models and exploratory analysis in networks. (English) Zbl 1155.91026

Summary: Networks are widely used in the biological, physical, and social sciences as a concise mathematical representation of the topology of systems of interacting components. Understanding the structure of these networks is one of the outstanding challenges in the study of complex systems. Here we describe a general technique for detecting structural features in large-scale network data that works by dividing the nodes of a network into classes such that the members of each class have similar patterns of connection to other nodes. Using the machinery of probabilistic mixture models and the expectation-maximization algorithm, we show that it is possible to detect, without prior knowledge of what we are looking for, a very broad range of types of structure in networks. We give a number of examples demonstrating how the method can be used to shed light on the properties of real-world networks, including social and information networks.

MSC:

91D30 Social networks; opinion dynamics
91C20 Clustering in the social and behavioral sciences
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Reviews of Modern Physics 74 pp 47– (2002) · Zbl 1205.82086
[2] SIAM REV 45 pp 167– (2003) · Zbl 1029.68010
[3] PHYS REPORTS 424 pp 175– (2006) · Zbl 1371.82002
[4] Nature; Physical Science (London) 401 pp 130– (1999)
[5] COMPUT COMM REV 29 pp 251– (1999)
[6] Watts, Nature; Physical Science (London) 393 (6684) pp 440– (1998) · Zbl 1368.05139
[7] Girvan, PNAS 99 (12) pp 7821– (2002) · Zbl 1032.91716
[8] Pastor-Satorras, Physical Review Letters 87 (25) pp 258701– (2001)
[9] Newman, Physical Review Letters 89 (20) pp 208701– (2002)
[10] Milo, Science 298 (5594) pp 824– (2002)
[11] AM J SOCIOL 81 pp 730– (1976)
[12] Jones, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 270 (1520) pp 1123– (2003)
[13] J R STATIST SOC B 39 pp 185– (1977)
[14] ANN STAT 11 pp 93– (1983)
[15] 33 pp 452– (1977)
[16] Reichardt, Physical Review Letters 93 (21) pp 218701– (2004)
[17] Palla, Nature; Physical Science (London) 435 (7043) pp 814– (2005)
[18] AM J SOCIOL 107 pp 679– (2001)
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.