摘要
我们提出了一种名为Ego-Splitting的新框架，用于检测复杂网络中的聚类结构。该框架利用称为“星型子图”（ego-nets）的局部结构——即每个节点邻域所诱导出的子图——来解耦重叠的聚类。Ego-Splitting是一种高度可扩展且灵活的框架，具备可证明的理论保证，能够将复杂的重叠聚类问题转化为更简单、更易于处理的非重叠（划分）问题。该方法可处理包含数十亿条边的图结构，在社区发现任务中显著优于以往基于星型子图分析的解决方案。更具体而言，我们的框架包含两个步骤：局部星型子图分析阶段与全局图划分阶段。在局部阶段，首先使用划分算法对节点的星型子图进行分割，得到初步的局部聚类结果；随后，利用这些聚类信息将每个节点拆分为若干“人格节点”（persona nodes），以表征该节点在其所属社区中的具体实例。在全局阶段，对新构建的图进行划分，从而获得原始图的重叠聚类结构。