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 (15)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• The diameter of the world wide web
• Comparing community structure identification
• Dynamical and correlation properties of the Internet
• Detecting fuzzy community structures in complex networks with a Potts model
• Spectral Measures of Bipartivity in Complex Networks
• Community Detection as an Inference Problem
• Structural Inference of Hierarchies in Networks
• On network bipartivity

Cited by in corpus (144)

• Community detection in graphs
• Multilayer Networks
• The structure and dynamics of multilayer networks
• Community detection algorithms: a comparative analysis
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Community structure in directed networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The performance of modularity maximization in practical contexts
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Modularity and community detection in bipartite networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Random walks and diffusion on networks
• Clustering and Community Detection in Directed Networks: A Survey
• Generalized Louvain Method for Community Detection in Large Networks
• Phase transition in the detection of modules in sparse networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Bayesian Approach to Network Modularity
• A Classification for Community Discovery Methods in Complex Networks
• The entropy of network ensembles
• Detecting highly overlapping community structure by greedy clique expansion
• Consistency of community detection in networks under degree-corrected stochastic block models
• Pseudo-likelihood methods for community detection in large sparse networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• The entropy of randomized network ensembles
• Assessing the relevance of node features for network structure
• Community detection, link prediction, and layer interdependence in multilayer networks
• Identification of core-periphery structure in networks
• Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction
• Rate-optimal graphon estimation
• Maximum likelihood: extracting unbiased information from complex networks
• Community extraction for social networks
• LinkRank: Finding communities in directed networks
• Large-scale structure of time evolving citation networks
• Overlapping stochastic block models with application to the French political blogosphere
• Coauthorship and Citation Networks for Statisticians
• Entropy of stochastic blockmodel ensembles
• Statistical significance of communities in networks
• Role models for complex networks
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Community Detecting By Signaling on Complex Networks
• A New Comparative Definition of Community and Corresponding Identifying Algorithm
• Entropies of complex networks with hierarchically constrained topologies
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Data-driven Computational Social Science: A Survey
• Exploring the structural regularities in networks
• Protein-Interaction-Networks: More than mere modules
• Scalable Text and Link Analysis with Mixed-Topic Link Models
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Magnetic eigenmaps for community detection in directed networks
• Communities in Networks
• The interplay of microscopic and mesoscopic structure in complex networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Software systems through complex networks science: Review, analysis and applications
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Inversion method for content-based networks
• Stochastic block model and exploratory analysis in signed networks
• Networks in Motion
• Measuring Significance of Community Structure in Complex Networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Nine Quick Tips for Analyzing Network Data
• Leveraging disjoint communities for detecting overlapping community structure
• Overlapping community detection in signed networks
• A generalised significance test for individual communities in networks
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Strategies for online inference of model-based clustering in large and growing networks
• Profiling of a network behind an infectious disease outbreak
• Concentric Characterization and Classification of Complex Network Nodes: Theory and Application to Institutional Collaboration
• Group detection in complex networks: An algorithm and comparison of the state of the art
• Component models for large networks
• Ex-ante measure of patent quality reveals intrinsic fitness for citation-network growth
• Population stratification using a statistical model on hypergraphs
• Random Spatial Network Models with Core-Periphery Structure
• Exact Blind Community Detection from Signals on Multiple Graphs
• Sampling promotes community structure in social and information networks
• Closed benchmarks for network community structure characterization
• Discovering Network Structure Beyond Communities
• Layer reconstruction and missing link prediction of multilayer network with a Maximum A Posteriori estimation
• Community detection by label propagation with compression of flow
• Model selection and clustering in stochastic block models with the exact integrated complete data likelihood
• Automatic Network Fingerprinting through Single-Node Motifs
• Inference for graphs and networks: Extending classical tools to modern data
• Community detection based on first passage probabilities
• Node mixing and group structure of complex software networks
• A Generative Node-attribute Network Model for Detecting Generalized Structure
• Quantum Annealing for Dirichlet Process Mixture Models with Applications to Network Clustering
• Node discovery problem for a social network
• Centrality properties of directed module members in social networks
• Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
• Unfolding network communities by combining defensive and offensive label propagation
• A Method for Group Extraction and Analysis in Multilayer Social Networks
• Local community extraction in directed networks
• Convexity in complex networks
• Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
• Community detection for networks with unipartite and bipartite structure
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Detecting the optimal number of communities in complex networks
• Pairwise Covariates-adjusted Block Model for Community Detection
• Detecting groups of similar components in complex networks
• Reflective visualization and verbalization of unconscious preference
• Generalized network community detection
• Scalable Spectral Algorithms for Community Detection in Directed Networks
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Entrograms and coarse graining of dynamics on complex networks
• Criterions for locally dense subgraphs
• Automatic exploration of structural regularities in networks
• Generative models for local network community detection
• Detecting network communities via greedy expanding based on local superiority index
• Local multiresolution order in community detection
• Overlapping Communities in Social Networks
• Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
• The art of community detection
• Community Detection Based on the $L_{\infty }$ convergence of eigenvectors in DCBM
• Clustering in networks with the collapsed Stochastic Block Model
• New consistent and asymptotically normal estimators for random graph mixture models
• Learning Social Circles in Ego Networks based on Multi-View Social Graphs
• Modular Representation of Layered Neural Networks
• Sandpile cascades on interacting tree-like networks
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• Node discovery in a networked organization
• Stability of Maximum likelihood based clustering methods: exploring the backbone of classifications (Who is keeping you in that community?)
• Metrics for Community Analysis: A Survey
• Community detection and tracking on networks from a data fusion perspective
• On role extraction for digraphs via neighbourhood pattern similarity
• Trophic groups and modules: two levels of group detection in food webs
• Uncovering Longitudinal Healthcare Utilization from Patient-Level Medical Claims Data
• A Generative Model for Exploring Structure Regularities in Attributed Networks
• Spectral community detection in heterogeneous large networks
• Identification of hybrid node and link communities in complex networks
• On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
• Search of Weighted Subgraphs on Complex Networks with Maximum Likelihood Methods
• Analysis of Social Group Dynamics
• Clustering based on Random Graph Model embedding Vertex Features
• Error-Correcting Decoders for Communities in Networks
• Consistency of regularized spectral clustering in degree-corrected mixed membership model
• Community Detection by a Riemannian Projected Proximal Gradient Method
• Overlapping Communities Detection via Measure Space Embedding
• Community Structure and Topical Differentiation in European RTD Collaborations
• Understanding Vulnerability of Communities in Complex Networks
• Multiplex Structures: Patterns of Complexity in Real-World Networks