A spectral method for community detection in moderately-sparse degree-corrected stochastic block models

2015-06-29 · Lennart Gulikers, Marc Lelarge, Laurent Massoulié

We consider community detection in Degree-Corrected Stochastic Block Models (DC-SBM). We propose a spectral clustering algorithm based on a suitably normalized adjacency matrix. We show that this algorithm consistently recovers the block-membership of all but a vanishing fraction of nodes, in the regime where the lowest degree is of order log$(n)$ or higher. Recovery succeeds even for very heterogeneous degree-distributions. The used algorithm does not rely on parameters as input. In particular, it does not need to know the number of communities.

📄 PDF Abstract BibTeX arXiv:1506.08621

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringCommunity Detection

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs

2019-01-25 · NeurIPS 2019 12 · Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay

Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the Bethe-Hessian matrix $H_r = (r^2-1)I_n +…

Clustering Community Detection Stochastic Block Model

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)

2025-11-26 · Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen arxiv

A fundamental theoretical question in network analysis is to determine under which conditions community recovery is possible in polynomial time in the Stochastic Block Model (SBM). When the number $K$ of communities rema…

A unified framework for spectral clustering in sparse graphs

2020-03-20 · Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay

This article considers spectral community detection in the regime of sparse networks with heterogeneous degree distributions, for which we devise an algorithm to efficiently retrieve communities. Specifically, we demonst…

Clustering Community Detection Form

Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian

2020-06-03 · NeurIPS 2020 12 · Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay

This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is prop…

Community Detection Stochastic Block Model

Analysis of spectral clustering algorithms for community detection: the general bipartite setting

2018-03-12 · Zhixin Zhou, Arash A. Amini

We consider spectral clustering algorithms for community detection under a general bipartite stochastic block model (SBM). A modern spectral clustering algorithm consists of three steps: (1) regularization of an appropri…