Mixture models and exploratory analysis in networks

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

8 pages, 4 figures, two new examples in this version plus minor corrections

References in corpus (4)

• Uncovering the overlapping community structure of complex networks in nature and society
• Comparing community structure identification
• Structural Inference of Hierarchies in Networks
• On network bipartivity

Cited by in corpus (15)

• Community structure in directed networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Modularity and community detection in bipartite networks
• A Bayesian Approach to Network Modularity
• Maximum likelihood: extracting unbiased information from complex networks
• Large-scale structure of time evolving citation networks
• Role models for complex networks
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Component models for large networks
• Centrality properties of directed module members in social networks
• Detecting groups of similar components in complex networks
• The art of community detection
• Search of Weighted Subgraphs on Complex Networks with Maximum Likelihood Methods
• Clustering based on Random Graph Model embedding Vertex Features