paper-with-me

홈 › Papers

Consistency of spectral clustering in stochastic block models

2013-12-07 · Jing Lei, Alessandro Rinaldo

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 network can consistently recover hidden communities even when the order of the maximum expected degree is as small as $\log n$, with $n$ the number of nodes. This result applies to some popular polynomial time spectral clustering algorithms and is further extended to degree corrected stochastic block models using a spherical $k$-median spectral clustering method. A key component of our analysis is a combinatorial bound on the spectrum of binary random matrices, which is sharper than the conventional matrix Bernstein inequality and may be of independent interest.

📄 PDF Abstract BibTeX arXiv:1312.2050

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

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…

Similar Papers 제목 키워드 기반

Strong Consistency, Graph Laplacians, and the Stochastic Block Model

2020-04-21 · Shaofeng Deng, Shuyang Ling, Thomas Strohmer

Spectral clustering has become one of the most popular algorithms in data clustering and community detection. We study the performance of classical two-step spectral clustering via the graph Laplacian to learn the stocha…

ClusteringCommunity DetectionStochastic Block Model

On consistency of constrained spectral clustering under representation-aware stochastic block model

2022-03-03 · Shubham Gupta, Ambedkar Dukkipati

Spectral clustering is widely used in practice due to its flexibility, computational efficiency, and well-understood theoretical performance guarantees. Recently, spectral clustering has been studied to find balanced clu…

ClusteringComputational EfficiencyStochastic Block Model

On Consistency of Compressive Spectral Clustering

2017-02-12 · Muni Sreenivas Pydi, Ambedkar Dukkipati

Spectral clustering is one of the most popular methods for community detection in graphs. A key step in spectral clustering algorithms is the eigen decomposition of the $n{\times}n$ graph Laplacian matrix to extract its …

ClusteringCommunity DetectionStochastic Block Model

Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding

2013-10-02 · Vince Lyzinski, Daniel Sussman, Minh Tang, Avanti Athreya 외

Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain…

Clustering

The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels

2015-12-01 · NeurIPS 2015 12 · Purnamrita Sarkar, Deepayan Chakrabarti, Peter J. Bickel

Link prediction and clustering are key problems for network-structureddata. While spectral clustering has strong theoretical guaranteesunder the popular stochastic blockmodel formulation of networks, itcan be expensive f…

ClusteringLink Prediction