基于节点重要性和模块度优化的社团划分算法

张梦园,李玲娟

(南京邮电大学 计算机学院,江苏 南京 210023)

0 引 言

对复杂网络的深入研究发现,现实世界中许多系统都能抽象为网络,如人与人之间的社交网络、自然界的食物链网络、蛋白质相互作用网络等。这些网络由具有一定组织性和极大随机性的节点构成[1]。根据网络节点之间的连边是否存在权值,复杂网络可以分为无权网络和加权网络,加权网络相比无权网络能够反映更加丰富的信息,同时赋予复杂网络更加明确的物理意义。

社团是复杂网络的一个重要特征,社团内各个节点间连接紧密,而社团之间只有一些稀疏的连接[2]。发现复杂网络中的社团结构能为进一步理解网络所代表的真实世界系统的结构和功能提供捷径。经典的社团划分算法有基于模块度优化的、基于标签传播的、基于局部扩展的、基于深度学习的等等[3-5]。针对加权网络的社团划分算法还相对较少,通常考虑引入边的权值来对已有的经典的无权网络划分算法进行改进。典型的基于模块度优化的加权复杂网络的社团划分算法有WGN[6]、WFN[7-8]、CNM[9]、BGLL等。

其中的BGLL[10]算法分为两个阶段,第一阶段不断将节点移入(即并入)使模块度增益最大的社团,直至节点的移动不会再导致模块度增加;第二阶段将得到的社团作为新的节点对网络进行重构,在重构的网络上重复第一阶段。BGLL算法在第二阶段对网络重构,极大地缩小了网络规模,算法的迭代会越来越快,因此具有很好的时间效率,但由于第一阶段迭代遍历节点是无序的,没有考虑节点自身在网络中的地位,因此可能会使最终划分结果的准确度不佳,仍有改进的空间。……