# Overlapping community detection in networks via sparse spectral decomposition

@article{Arroyo2020OverlappingCD, title={Overlapping community detection in networks via sparse spectral decomposition}, author={Jes{\'u}s Arroyo and Elizaveta Levina}, journal={ArXiv}, year={2020}, volume={abs/2009.10641} }

We consider the problem of estimating overlapping community memberships in a network, where each node can belong to multiple communities. More than a few communities per node are difficult to both estimate and interpret, so we focus on sparse node membership vectors. Our algorithm is based on sparse principal subspace estimation with iterative thresholding. The method is computationally efficient, with a computational cost equivalent to estimating the leading eigenvectors of the adjacency… Expand

#### Figures and Tables from this paper

#### References

SHOWING 1-10 OF 73 REFERENCES

Detecting Overlapping Communities in Networks Using Spectral Methods

- Mathematics, Computer Science
- SIAM J. Math. Data Sci.
- 2020

An efficient spectral algorithm for estimating the community memberships is developed, which deals with the overlaps by employing the K-medians algorithm rather than the usual K-means for clustering in the spectral domain. Expand

Consistency of spectral clustering in stochastic block models

- Mathematics
- 2015

We analyze the performance of spectral clustering for community extraction in stochastic block models. We show that, under mild conditions, spectral clustering applied to the adjacency matrix of the… Expand

Estimating the number of communities in networks by spectral methods

- Computer Science, Mathematics
- ArXiv
- 2015

This work proposes a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix, which performs well under several models and a wide range of parameters. Expand

Spectral clustering and the high-dimensional stochastic blockmodel

- Mathematics
- 2011

Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social ne tworks, representing people who communicate with each other, are… Expand

Finding overlapping communities in networks by label propagation

- Computer Science, Physics
- ArXiv
- 2009

The main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Expand

Finding community structure in networks using the eigenvectors of matrices.

- Mathematics, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2006

A modularity matrix plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations, and a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong are proposed. Expand

Detecting Overlapping and Correlated Communities without Pure Nodes: Identifiability and Algorithm

- Computer Science
- ICML
- 2019

This work adopts the mixed-membership stochastic blockmodel as the underlying probabilistic model, and gives conditions under which the memberships of a subset of nodes can be uniquely identified. Expand

An efficient and principled method for detecting communities in networks

- Computer Science, Physics
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2011

This work describes a method for finding overlapping communities based on a principled statistical approach using generative network models and shows how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. Expand

Overlapping community detection using Bayesian non-negative matrix factorization.

- Computer Science, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2011

This work presents a probabilistic approach to community detection that utilizes a Bayesian non-negative matrix factorization model to extract overlapping modules from a network. Expand

Estimating the number of communities in a network

- Computer Science, Medicine
- Physical review letters
- 2016

A mathematically principled approach for finding the number of communities in a network by maximizing the integrated likelihood of the observed network structure under an appropriate generative model is described. Expand