Mixture models and exploratory analysis in networks

By Mark Newman, Elizabeth A. Leicht. Proceedings of the National Academy of Sciences of the United States of America, 2006

568 citations recorded by the source corpus.

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.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/40264b9ecbc944accf11d9eb94644564a3b3ceb3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

A classification for community discovery methods in complex networks (2011, methodology): “The generation and test is very similar to the technique implemented in the Expectation Maximization [7] presented in the following section, but in this case is applied on edges instead of applying it on nodes.”
Random walks and diffusion on networks (2016, background): “also be fruitful to exploit similar ideas to examine other types of network properties (e.g., \role similarity" [349, 416], \rich clubs" [417, 418], and approximately multipartite structure [419]). RWs have also been used for some studies of community structure in temporal and multilayer n”
Assessing the relevance of node features for network structure (2008, methodology): “nodes, and a variety of methods have been proposed relying on i) structural properties of the network (betweenness centrality [13], modularity [14], spectral decomposition [15], cliques [16] and hierarchical structure [17]), ii) statistical methods [18] or iii) on processes defined on the network [9”
Scalable Inference of Overlapping Communities (2012, methodology): “These methods include algorithmic approaches [7, 8] and probabilistic models [2, 3, 9, 10].”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “ al. [82]; the two-step random walk model is able to capture important connectivity patterns by exploiting the existence of co-citation and co-reference relationships. The method of Newman and Leicht [94] based on mixture models can detect diverse types of clusters, including assortative11 and dissa”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [86, 140, 144, 94, 133].”
Statistical properties of community structure in large social and information networks (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [85, 137, 141, 93, 130].”
Hierarchical block structures and high-resolution model selection in large networks (2013, background): “This approach oﬀers several advantages over a dominating fraction of existing methods, since it is more ﬁrmly grounded on well-known principles and methods of statistical analysis, which allows the incorporation of the statistical evidence present in the data in a formally correct manner.”
A nonparametric view of network models and Newman–Girvan and other modularities (2009, unknown): “The mixture model of Newman and Leicht (15) where, given communities 1, is not of this type, since it is not invariant under permutations.”
Multilayer networks (2013, background): “One can also generate models of interconnected networks using notions such as block models [112,136] and mixture models [223,247].”
Unsupervised Machine Learning for Networking: Techniques, Applications and Research Challenges (2017, background): “mixture models produces remarkable results in deciphering the structure and topology of the vertices connected through a multi-dimensional network [83].”
Community detection in graphs (2009, methodology): “The community assignments are recovered through an expectation-maximization procedure that closely follows that by Newman and Leicht.”