Community Detection in Degree-Corrected Block Models
Community Detection in Degree-Corrected Block Models
复制标题
DOI：
10.1214/17-aos1615
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Chao Gao;Zongming Ma;A. Zhang;Harrison H. Zhou
中科院分区：
文献类型：
--
作者：
Chao Gao;Zongming Ma;A. Zhang;Harrison H. Zhou
社区检测是网络数据分析的核心问题。给定一个网络，社区检测的目标是将网络节点划分为少量的簇，这通常有助于揭示有趣的结构。研究度校正块模型(DCBMS)中的社区发现问题。在适当的条件下，我们首先得到了误分类比例损失问题的渐近极小极大风险。以直观和可解释的方式显示，最小最大风险取决于度数校正参数、社区大小以及社区内部和社区之间的平均连接性。此外，我们还提出了一种多项式时间算法来自适应地执行DCBMS中一致甚至渐近最优的社区检测。
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.