任成磊, 韩定定, 蒲　鹏, 张嘉诚

(华东师范大学信息科学技术学院, 上海 200241)



利用堆数据结构实现邻域重叠社团结构挖掘

任成磊, 韩定定, 蒲鹏, 张嘉诚

(华东师范大学信息科学技术学院, 上海 200241)

摘要:基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性，提出了一种高效、快速、准确的社团划分算法。基于贪婪算法，建立最大模块度矩阵，并采用堆数据结构，划分非邻域重叠社团。通过分析局部网络的连边情况，计算邻域社团的划分密度，以准确挖掘社团间的重叠节点。新算法经过仿真分析和实证研究表明，算法复杂度降到近线性。

关键词：社团挖掘；邻域重叠；模块度；划分密度；时间复杂度

0引言

随着对网络性质的物理意义和数学特性的深入研究，人们发现在社会网、神经网、蛋白质网、万维网、通信网等网络中，普遍存在着一种特性——社团结构[1-4]。网络是由若干个团簇构成的，每个团簇内部的节点之间的连接非常紧密，但是各个团簇之间的连接却相对比较稀疏。这些子团簇就被称为社团，社团结构可以直观形象地揭示一个网络内部是如何自组织的，以及各个团簇之间的关系。因此，复杂网络社团结构的探测研究，对于网络的拓扑结构分析、功能的理解和网络行为动力学预测等有着重要的意义[5-6]。

近几年，复杂网络中社团结构的挖掘得到了各个领域科学家的广泛研究。Kernighan等[7]基于贪婪算法的基本原理，通过优化两个社团之间的连边，准确地将网络划分为两个已知大小的社团。……