Estimating Mixed Memberships With Sharp Eigenvector Deviations
From MaRDI portal
Publication:5881973
Abstract: We consider the problem of estimating community memberships of nodes in a network, where every node is associated with a vector determining its degree of membership in each community. Existing provably consistent algorithms often require strong assumptions about the population, are computationally expensive, and only provide an overall error bound for the whole community membership matrix. This paper provides uniform rates of convergence for the inferred community membership vector of each node in a network generated from the Mixed Membership Stochastic Blockmodel (MMSB); to our knowledge, this is the first work to establish per-node rates for overlapping community detection in networks. We achieve this by establishing sharp row-wise eigenvector deviation bounds for MMSB. Based on the simplex structure inherent in the eigen-decomposition of the population matrix, we build on established corner-finding algorithms from the optimization community to infer the community membership vectors. Our results hold over a broad parameter regime where the average degree only grows poly-logarithmically with the number of nodes. Using experiments with simulated and real datasets, we show that our method achieves better error with lower variability over competing methods, and processes real world networks of up to 100,000 nodes within tens of seconds.
Recommendations
- A tensor approach to learning mixed membership community models
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- Overlapping community detection in networks via sparse spectral decomposition
- Mixed membership stochastic blockmodels
- Detecting overlapping communities in networks using spectral methods
Cites work
- A limit theorem for scaled eigenvectors of random dot product graphs
- A tensor approach to learning mixed membership community models
- A useful variant of the Davis-Kahan theorem for statisticians
- Community discovery using nonnegative matrix factorization
- Computing a nonnegative matrix factorization -- provably
- Consistency of spectral clustering in stochastic block models
- Efficient discovery of overlapping communities in massive networks
- Entrywise eigenvector analysis of random matrices with low expected rank
- Exact Recovery in the Stochastic Block Model
- Improved Graph Clustering
- Mixed membership stochastic blockmodels
- Multidimensional binary search trees used for associative searching
- Numerical recipes. The art of scientific computing.
- Signal-plus-noise matrix models: eigenvector deviations and fluctuations
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Unperturbed: spectral analysis beyond Davis-Kahan
Cited in
(11)- Finding mixed memberships in categorical data
- Survival Mixed Membership Blockmodel
- A tensor approach to learning mixed membership community models
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- Latent Space Modeling of Hypergraph Data
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Assigning topics to documents by successive projections
- An \({\ell_p}\) theory of PCA and spectral clustering
This page was built for publication: Estimating Mixed Memberships With Sharp Eigenvector Deviations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5881973)
