Probabilistic Community Detection With Unknown Number of Communities
Probabilistic Community Detection With Unknown Number of Communities
复制标题
DOI：
10.1080/01621459.2018.1458618
复制
发表时间：
2016-02
影响因子：
3.7
通讯作者：
J. Geng;A. Bhattacharya;D. Pati
中科院分区：
文献类型：
--
作者：
J. Geng;A. Bhattacharya;D. Pati
摘要网络分析中的一个基本问题是将节点聚类成共享相似连接模式的组。现有的社区检测算法假设已知聚类个数，或使用各种选择标准对其进行先验估计，然后估计社区结构。忽视第一阶段的不确定性可能会导致错误的聚类，特别是当社区结构模糊的时候。相反，我们提出了一个连贯的概率框架，用于同时估计社区数量和社区结构，将最近发展的贝叶斯非参数技术应用于网络模型。提出了一种高效的马尔可夫链蒙特卡罗(MCMC)算法，该算法不需要对聚类个数进行可逆跳跃。在各种合成数据示例和基准真实数据集中，该方法被证明优于最近开发的社区检测算法。在所有构型的空间上使用适当的度量，即使在簇数未知的情况下，我们也得到非渐近的贝叶斯风险界。在此过程中，我们发展了Bernoulli随机变量的非线性函数的集中性质，这可能在相关模型的分析中具有独立的兴趣。这篇文章的补充材料可以在网上找到。
ABSTRACT A fundamental problem in network analysis is clustering the nodes into groups which share a similar connectivity pattern. Existing algorithms for community detection assume the knowledge of the number of clusters or estimate it a priori using various selection criteria and subsequently estimate the community structure. Ignoring the uncertainty in the first stage may lead to erroneous clustering, particularly when the community structure is vague. We instead propose a coherent probabilistic framework for simultaneous estimation of the number of communities and the community structure, adapting recently developed Bayesian nonparametric techniques to network models. An efficient Markov chain Monte Carlo (MCMC) algorithm is proposed which obviates the need to perform reversible jump MCMC on the number of clusters. The methodology is shown to outperform recently developed community detection algorithms in a variety of synthetic data examples and in benchmark real-datasets. Using an appropriate metric on the space of all configurations, we develop nonasymptotic Bayes risk bounds even when the number of clusters is unknown. Enroute, we develop concentration properties of nonlinear functions of Bernoulli random variables, which may be of independent interest in analysis of related models. Supplementary materials for this article are available online.