基于最大生成树的重叠社区发现算法

摘要

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。针对局部扩展算法(local fitness method,LFM)随机选取种子节点造成的社区结果鲁棒性较低等问题,提出了一种基于最大生成树的重叠社区发现算法:提出一种新颖的边权重定义,将无权的网络转换为带权重的网络,而且该权重真实反映了网络真实结构;提出一种节点影响力计算方法,反映节点在整个网络结构中的重要程度;提出了一种新的生成候选种子集的方法,并借助最大生成树使得到的候选种子节点在网络中更具有代表性;对初始社区划分结果进行优化,避免社区之间重叠度过多。经仿真实验发现,该算法与经典的重叠社区发现算法相比,无论在真实网络还是LFR人工网络上,均有良好的表现。