论文标题
在加权图中可证明的重叠社区检测
Provable Overlapping Community Detection in Weighted Graphs
论文作者
论文摘要
社区检测是一个广泛研究的无监督学习问题，该任务是根据观察到的成对实体相互作用将类似实体组合在一起。这个问题在社交网络分析和计算生物学等不同领域中具有应用。在社区没有重叠的假设下，有大量文献研究这个问题。当允许社区重叠时，通常会做出纯粹的节点假设，即每个社区都有一个属于该社区的节点。但是，在实践中，这个假设可能并不总是满足。在本文中，我们提供了一种可证明的方法，可以在加权图中检测重叠的社区而不明确地做出纯节点假设。此外，与大多数现有算法相反，我们的方法基于凸优化，为此，许多有用的理论属性已经知道。我们证明了我们在人工和现实世界数据集上的算法成功。
Community detection is a widely-studied unsupervised learning problem in which the task is to group similar entities together based on observed pairwise entity interactions. This problem has applications in diverse domains such as social network analysis and computational biology. There is a significant amount of literature studying this problem under the assumption that the communities do not overlap. When the communities are allowed to overlap, often a pure nodes assumption is made, i.e. each community has a node that belongs exclusively to that community. This assumption, however, may not always be satisfied in practice. In this paper, we provide a provable method to detect overlapping communities in weighted graphs without explicitly making the pure nodes assumption. Moreover, contrary to most existing algorithms, our approach is based on convex optimization, for which many useful theoretical properties are already known. We demonstrate the success of our algorithm on artificial and real-world datasets.
