Community Detection in Degree-Corrected Block Models
Community detection is a central problem of network data analysis. Given a network, the goal of community detection is to partition the network nodes into a small number of clusters, which could often help reveal interesting structures. The present paper studies community detection in Degree-Corrected Block Models (DCBMs). We first derive asymptotic minimax risks of the problem for a misclassification proportion loss under appropriate conditions. The minimax risks are shown to depend on degree-correction parameters, community sizes, and average within and between community connectivities in an intuitive and interpretable way. In addition, we propose a polynomial time algorithm to adaptively perform consistent and even asymptotically optimal community detection in DCBMs.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
A spectral method for community detection in moderately-sparse degree-corrected stochastic block models
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 r…
ClusteringCommunity DetectionAn improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…
ClusteringCommunity DetectionStochastic Block ModelNon-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$ vertices partitioned int…
ClusteringCommunity DetectionStochastic Block ModelSpectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
Spectral clustering is a popular method for community detection in network graphs: starting from a matrix representation of the graph, the nodes are clustered on a low dimensional projection obtained from a truncated spe…
ClusteringCommunity DetectionModel SelectionMatrix Factorization Framework for Community Detection under the Degree-Corrected Block Model
Community detection is a fundamental task in data analysis, and block models provide an approach for identifying a wide variety of community structures while offering high interpretability. The degree-corrected block mod…
Community Detection