论文部分内容阅读
社团结构是网络中相同属性节点的集合,揭示了复杂网络中的隐藏属性和交互规律。识别和分析网络中的社团结构有助于更深入的了解复杂网络的内在规律,探究网络中个体的未来演化动态,预测复杂网络的发展规律,因此,开展对社团结构检测的研究具有重要的理论与实际意义。模块度优化算法和标签传播算法是现有的两种较为典型的社团检测算法。二者在初始化时都是将各个节点视为一个独立的社团,这影响了模块度优化算法第一阶段的性能;另外,由于标签传播算法在计算时选择目标标签的随机性,导致社团检测结果不准确,算法的鲁棒性较差。针对以上两个算法存在的问题,本文结合复杂网络的节点重要性提出了相应的改进算法:(1)基于节点重要性的改进模块度优化社团检测算法:首先,对网络进行预处理,合并度值为1的节点;然后,对网络中节点进行重要性排序,以序列中若干重要节点作为中心进行扩展,形成网络的初始社团结构;最后以初始社团结构作为节点形成新图,以模块度为衡量标准将新图的节点进行相互合并得到最终社团结构。基于4个真实网络以及1个人工合成网络,选取了MDD算法等7种常用节点重要性排序算法对网络节点进行重要性排序,与基本模块度优化算法及其它典型算法相比,结果表明改进模块度优化算法能够更为有效地检测出网络中的社团结构,对于真实网络检测的模块度值和NMI值都优于其它算法。(2)基于模块度和节点重要性的改进标签传播算法:算法初始时不为节点分配标签,而是将网络进行准确和快速的初始划分,对划分在一起的节点分配相同的标签,减少了标签数量;根据节点重要性排序的结果更新标签,避免了不重要节点对标签更新的影响;选择标签时如果有多个待选标签,以待选标签对应节点的重要性为依据进行选择,避免了原算法的随机性。基于4个真实网络和1个人工合成网络的实验结果表明,与原算法及其它检测算法相比,改进算法能够有效改善原算法不稳定和正确率低的问题,能够获得稳定的社团检测结果,且检测结果的模块度值和NMI值都优于其它算法。