论文部分内容阅读
现实世界中许多系统都可以用复杂网络表示,对复杂网络的结构特征和内在嵌入机理的研究已成为人们正确认识复杂网络,并促进复杂网络理论发展与应用的重要途径。随着复杂网络的不断深入研究,人们发现了社团结构是复杂网络中的一个重要特征,有助于了解整个网络结构和功能。随着关注网络社团结构问题的不断增加,划分网络社团结构的算法层出不穷,其实用性和应用得到了更多的关注。本文针对复杂网络的社团发现算法改进及应用展开研究,主要工作包括:（1）为消除Louvain算法过程中模块度震荡和社团划分震荡现象,给出了一种改进的模块度增益计算方法,并基于此提出一种基于修剪策略的改进Louvain算法（a graph clustering algorithm based on pruning in complex networks,PRULOU）。算法包括四个主要过程:模块度增益(（35）Qnew)计算、节点移动、修剪和网络聚合。通过判断当前节点与邻域所在的社团标号是否一致,进而修剪网络中的节点,这明显提高了有效节点占节点序列的比例。在8个真实网络上,将所提出的算法与Louvain、快速算法、统计监测等7个经典算法进行实验比较,结果表明PRULOU算法在模块度、时间等方面均表现出优越性。（2）针对（35）Qnew仅可根据节点与社团之间的局限度量进行划分而导致PRULOU算法粗划分的问题,提出了基于模块度和相似性度量的修剪算法（A algorithm for pruning based on modularity and similarity measures,PRUJSM）。该算法给出了一种计算节点间相似性的度量指标JSM,并结合模块度的增益对其相似性进行度量,从而使节点在划分过程中进行更有效的移动。通过与一些经典算法在8个真实网络上的实验比较分析,结果表明PRUJMS表现优越,在模块性、时间等方面表现良好。（3）设计实现了一个面向社团发现算法的比较分析系统——Network Repository平台,包括网络数据集成、社团发现算法集成、评价指标集成三个功能模块。目前,平台集成了Karate、Dolphin、Football、Yeast网络等9个数据集。对这些网络数据进行预处理,获得网络规模、节点数、边数、聚集系数等数据统计信息。社团发现算法模块将5种经典社团发现算法（谱聚类、改进的谱聚类、快速算法、局部限制、统计监测方法）进行集成可视化,并以柱状图（histogram）和点状图（linechart）的形式给出了各算法在NMI、ARI、AC等指标的比较结果。