2006 MixtureModelsAndNetworksAnalysis

• (Newman & Leicht, 2006) ⇒ Mark E. J. Newman, Elizabeth A. Leicht. (2006). “Mixture Models and Exploratory Data Analysis in Networks.” In: Proceedings of the Natl. Acad. Sci. USA

Subject Headings: Mixture Models, Network Analysis, Exploratory Data Analysis.

Quotes

Abstract

• 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 which 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 examples demonstrating how the method can be used to shed light on the properties of real-world networks, including social and information networks.

References

• [1] M. E. J. Newman, A.-L. Barab´asi, and D. J. Watts, The Structure and Dynamics of Networks. Princeton University Press, Princeton (2006).
• [2] R. Albert and A.-L. Barab´asi, Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002).
• [3] M. E. J. Newman, The structure and function of complex networks. SIAM Review 45, 167–256 (2003).

[4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Complex networks: Structure and dynamics. Physics Reports 424, 175–308 (2006). [5] Stanley Wasserman and K. Faust, Social Network Analysis. Cambridge University Press, Cambridge (1994). [6] J. Scott, Social Network Analysis: A Handbook. Sage, London, 2nd edition (2000). [7] R. Albert, H. Jeong, and A.-L. Barab´asi, Diameter of the world-wide web. Nature 401, 130–131 (1999). [8] M. Faloutsos, P. Faloutsos, and Christos Faloutsos, On powerlaw relationships of the internet topology. Computer Communications Review 29, 251–262 (1999).

• [9] J. M. Kleinberg, S. R. Kumar, Prabhakar Raghavan, S. Rajagopalan, and A. Tomkins, The Web as a graph: Measurements, models and methods. In T. Asano, H. Imai, D. T. Lee, S.-I. Nakano, and T. Tokuyama (eds.), Proceedings of the 5th Annual International Conference on Combinatorics and Computing, number 1627 in Lecture Notes in Computer Science, pp. 1–18, Springer, Berlin (1999).

[10] D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). [11] M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proceedings of Natl. Acad. Sci. USA 99, 7821–7826 (2002). [12] L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, Comparing community structure identification. J. Stat. Mech. p. P09008 (2005). [13] R. Pastor-Satorras, A. V´azquez, and A. Vespignani, Dynamical and correlation properties of the Internet. Phys. Rev. Lett. 87, 258701 (2001). [14] M. E. J. Newman, Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002). [15] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Network motifs: Simple building blocks of complex networks. Science 298, 824– 827 (2002). [16] P. Holme, F. Liljeros, C. R. Edling, and B. J. Kim, Network bipartivity. Phys. Rev. E 68, 056107 (2003). [17] M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006). [18] E. Estrada and J. A. Rodr´ıguez-Vel´azquez, Spectral measures of bipartivity in complex networks. Phys. Rev. E 72, 046105 (2005). [19] F. Lorrain and H. C. White, Structural equivalence of individuals in social networks. Journal of Mathematical Sociology 1, 49–80 (1971). [20] We could alternatively base our calculation on the patterns of ingoing rather than outgoing links and for some networks this may be a useful approach. The mathematical developments are entirely analogous to the case presented here. [21] H. C. White, S. A. Boorman, and R. L. Breiger, Social structure from multiple networks: I. Blockmodels of roles and positions. Am. J. Sociol. 81, 730–779 (1976). [22] J. H. Jones and M. S. Handcock, An assessment of preferential attachment as a mechanism for human sexual network formation. Proceedings of R. Soc. London B 270, 1123– 1128 (2003). [23] A. Clauset, M. E. J. Newman, and C. Moore, Structural inference of hierarchies in networks. In: Proceedings of the 23rd International Conference on Machine Learning, Association of Computing Machinery, New York (2006). [24] M. B. Hastings, Community detection as an inference problem. Preprint cond-mat/0604429 (2006). [25] Arthur P. Dempster, N.M. Laird, and D. B. Rubin, Maximum likelihood from incomplete data via the em algorithm. J. R. Statist. Soc. B 39, 185–197 (1977). [26] G. J. McLachlan and T. Krishnan, The EM Algorithm and Extensions. Wiley-Interscience, New York (1996). [27] W. W. Zachary, An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33, 452–473 (1977). [28] J. Reichardt and S. Bornholdt, Detecting fuzzy community structures in complex networks with a Potts model. Phys. Rev. Lett. 93, 218701 (2004). [29] G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005). [30] J. Baumes, M. Goldberg, and M. Magdon-Ismail, E - cient identification of overlapping communities. In: Proceedings of the IEEE International Conference on Intelligence and Security Informatics, Institute of Electrical and Electronics Engineers, New York (2005). [31] D. M. Chickering and David Heckerman, E cient approximations for the marginal likelihood of Bayesian networks with hidden variables. Machine Learning 29, 181–212 (1997). [32] G. Schwarz, Estimating the dimension of a model. Annals of Statistics 6, 461–464 (1978). [33] Hitotogu Akaike, A new look at the statistical identification model. IEEE Trans. Auto. Control 19, 716–723 (1974).

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2006 MixtureModelsAndNetworksAnalysis	Elizabeth A. Leicht M. E. J. Newman			Mixture Models and Exploratory Data Analysis in Networks			http://arxiv.org/PS cache/physics/pdf/0611/0611158v2.pdf