谱聚类集成算法SCEA：高效发现网络重叠社区

"本文提出了一种名为谱聚类集成算法(SCEA)的方法，用于解决大规模网络中的重叠社区发现问题。SCEA通过结合高效的近似谱聚类(KASP)算法、个体聚类选择机制以及层次软聚类来挖掘高质量的社区结构。实验结果表明，SCEA在发现具有高规范化互信息(NMI)的网络重叠社区方面优于其他代表性算法(CPM, Link, COPRA, SSDE)，并且表现出良好的鲁棒性。" 网络社区发现是社交网络分析中的一个重要任务，旨在识别出网络中节点之间的紧密连接组，这些组被称为社区。在许多实际网络中，节点可能属于多个社区，因此重叠社区发现成为了必要的研究方向。传统的非重叠社区发现方法通常将节点分配到单一社区，而重叠社区发现允许节点在多个社区中存在，这更符合现实世界网络的复杂特性。 谱聚类是一种基于图谱理论的聚类方法，它利用图的拉普拉斯矩阵进行节点的聚类。然而，对于大规模网络，直接应用谱聚类算法会导致计算复杂度和内存需求过高，无法有效处理。为了克服这个问题，KASP（近似谱聚类）算法被引入，它提供了一种高效的方法来近似地执行谱聚类，降低了计算成本。 SCEA算法首先利用KASP生成多个不同的个体聚类结果，形成一个聚类集合。接下来，通过个体聚类选择机制，选取最具代表性的聚类，这一过程有助于减少冗余和提高聚类质量。然后，根据优选的个体聚类构建簇相似图，这一步骤考虑了不同聚类之间的关系，进一步整合信息。最后，通过层次软聚类对节点进行软划分，即每个节点可以同时属于多个社区，这样就得到了网络节点的重叠社区结构。 实验部分对比了SCEA与其他知名算法，如CPM、Link、COPRA和SSDE。规范化互信息(NMI)是一种衡量聚类效果的指标，数值越高表示聚类结果与真实社区结构的匹配度越高。SCEA在NMI上的表现优于其他算法，表明其能发现更接近真实社区结构的重叠社区。此外，SCEA的鲁棒性也得到了验证，意味着即使在网络数据有噪声或不完全时，算法仍能保持稳定性能。 SCEA算法通过集成学习策略成功地解决了大规模网络中的重叠社区发现挑战，提供了更准确和鲁棒的社区结构。这种方法对于理解网络中的群组行为、发现关键节点以及预测网络动态等方面都有重要的应用价值。