Mixed Membership Estimation for Social Networks

Abstract

In economics and social science, network data are regularly observed, and a thorough understanding of the network community structure facilitates the comprehension of economic patterns and activities. Consider an undirected network with $n$ nodes and $K$ communities. We model the network using the Degree-Corrected Mixed-Membership (DCMM) model, where for each node $i$, there exists a membership vector ${\pi }_i=({\pi }_i(1),{\pi }_i(2),\dots ,{\pi }_i(K){)}^{\prime }$, where ${\pi }_i(k)$ is the weight that node $i$ puts in community $k$, $1\le k\le K$. In comparison to the well-known stochastic block model (SBM), the DCMM permits both severe degree heterogeneity and mixed memberships, making it considerably more realistic and general. We present an efficient approach, Mixed-SCORE, for estimating the mixed membership vectors of all nodes and the other DCMM parameters. This approach is inspired by the discovery of a delicate simplex structure in the spectral domain. We derive explicit error rates for the Mixed-SCORE algorithm and demonstrate that it is rate-optimal over a broad parameter space. Our findings provide a novel statistical tool for network community analysis, which can be used to understand network formations, extract nodal features, identify unobserved covariates in dyadic regressions, and estimate peer effects. We applied Mixed-SCORE to a political blog network, two trade networks, a co-authorship network, and a citee network, and obtained interpretable results.

84 pages

References in corpus (8)

• Stochastic blockmodels and community structure in networks
• Finding statistically significant communities in networks
• Community detection in networks: Structural communities versus ground truth
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Consistent Estimation of Mixed Memberships with Successive Projections
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• A Sharp Lower Bound for Mixed-membership Estimation

Cited by in corpus (24)

• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Testing for Global Network Structure Using Small Subgraph Statistics
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Improvements on SCORE, Especially for Weak Signals
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Recent Advances in Text Analysis
• A Sharp Lower Bound for Mixed-membership Estimation
• State Aggregation Learning from Markov Transition Data
• A useful criterion on studying consistent estimation in community detection
• Asymptotic Theory of Eigenvectors for Random Matrices with Diverging Spikes
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• Directed mixed membership stochastic blockmodel
• Directed degree corrected mixed membership model and estimating community memberships in directed networks
• Estimation and Clustering in Popularity Adjusted Stochastic Block Model
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• Overlapping community detection in networks via sparse spectral decomposition
• Mixed-SCORE+ for mixed membership community detection
• Estimating Mixed-Memberships Using the Symmetric Laplacian Inverse Matrix
• An improved spectral clustering method for mixed membership community detection
• Overlapping and nonoverlapping models
• Individual-centered partial information in social networks
• Consistency of regularized spectral clustering in degree-corrected mixed membership model
• The Hierarchy of Block Models