非重叠社区发现中近邻传播算法的研究与应用

摘要

复杂社会网络可以抽象为由大量节点和节点之间的联系组成的拓扑结构，其在众多领域中广泛存在。聚类分析作为研究复杂社会网络的重要手段之一，目的在于发现其内部的社区结构，体现其内在属性，更好地对现实生活进行指导。本文主要针对近邻传播算法的执行速率较慢、无监督的缺点，给出其改进算法，并将近邻传播算法运用在增量社区发现中。
　　首先，给出基于近邻传播的快速半监督社区发现算法（FSAP算法）。算法在研究近邻传播算法(AP算法)的基础上，根据因子图模型中信息在节点间的传递规则，通过将相似度值为0的节点对直接划分到不同的簇中而提高时间效率，成为快速近邻传播算法（FAP算法）。同时，结合部分Must-link和Cannot-link的成对约束信息，对相似度矩阵进行调整，在新的相似度矩阵上运行FAP算法。相比原始AP算法和其他算法，FSAP算法不仅具有良好的时间效率，而且可以有效利用先验知识去指导聚类过程，进而提高社区发现的准确率。
　　其次，给出基于近邻传播的增量社区发现算法（IAP算法）。算法在FAP算法的基础上，根据网络动态变化的特点，将增量分为增加边、删除边、增加节点、删除节点四种类型，且给出对应的处理方法。由于算法对网络变化进行局部更新，一段时间之后可能造成算法结果相比于真实的社区结构存在失真，给出最小模块度进行检测。在动态社区发现中，相比静态AP算法对全局网络结构的更新，IAP算法不仅能够有效地降低时间复杂度，且能够保证聚类精度。
　　最后，设计并实现了非重叠社区发现算法的原型系统。该系统可以实现数据录入、算法选择、结果显示、系统设置等功能，能够直观地体现社区发现的结果，在社区发现的研究中发挥了良好的作用。