Covariate Regularized Community Detection in Sparse Graphs
Covariate Regularized Community Detection in Sparse Graphs
复制标题
DOI：
10.1080/01621459.2019.1706541
复制
发表时间：
2016-07
影响因子：
3.7
通讯作者：
Bowei Yan;Purnamrita Sarkar
中科院分区：
文献类型：
--
作者：
Bowei Yan;Purnamrita Sarkar
摘要在本文中，我们研究了存在节点协变量的网络中的社区检测问题。在许多情况下，协变量和网络单独只能给出集群结构的部分视图。我们需要通过考虑两者来共同推断完整的集群结构。在统计学中，一个新兴的工作机构一直专注于结合来自网络边缘和节点协变量的信息来推断社区成员资格。然而，到目前为止，理论上的保证已经建立在稠密区域，在那里网络可以在广泛的参数区域下导致完美的聚类，因此协变量的作用通常并不清楚。在这篇文章中，我们考察了稀疏网络与有限维亚高斯混合作为协变量在适度的分离条件下。在此设置中，每个单独的源只能正确地聚集一部分不会消失的节点。我们提出了一个简单的优化框架，当两个源携带了关于簇成员身份的部分信息时，该框架可以提高聚类精度，因此它们本身的性能很差。我们的优化问题可以用可伸缩的凸优化算法来解决。通过大量的模拟和真实数据算例，我们证明了该方法优于现有的其他方法。这篇文章的补充材料可以在网上找到。
Abstract In this article, we investigate community detection in networks in the presence of node covariates. In many instances, covariates and networks individually only give a partial view of the cluster structure. One needs to jointly infer the full cluster structure by considering both. In statistics, an emerging body of work has been focused on combining information from both the edges in the network and the node covariates to infer community memberships. However, so far the theoretical guarantees have been established in the dense regime, where the network can lead to perfect clustering under a broad parameter regime, and hence the role of covariates is often not clear. In this article, we examine sparse networks in conjunction with finite dimensional sub-Gaussian mixtures as covariates under moderate separation conditions. In this setting each individual source can only cluster a nonvanishing fraction of nodes correctly. We propose a simple optimization framework which improves clustering accuracy when the two sources carry partial information about the cluster memberships, and hence perform poorly on their own. Our optimization problem can be solved by scalable convex optimization algorithms. With a variety of simulated and real data examples, we show that the proposed method outperforms other existing methodology. Supplementary materials for this article are available online.