论文部分内容阅读
对于任何包含大量个体单元的复杂系统来说,我们都可以将其看作复杂网络来研究,复杂网络具有小世界、无标度和社团结构等诸多特征。社团结构主要刻画了网络中节点之间的相互关系,社团结构具有处于社团内部的节点联系较为紧密,处于社团之间的节点联系较为稀疏的显著特点,深入了解复杂网络中的社团结构有助于发现网络中潜藏着的规律和预测网络的行为。本文依据优化、启发式和相似度等不同的策略对常用社团划分算法进行了分类,并对其中的典型代表算法进行了详细的研究分析。针对相似度算法中存在的问题,本文提出了基于相似度的三元社团合并算法(Ternary Community Merging Algorithm based on Similarity,STCMA)。然后,本文将三元社团的概念应用于传统标签传播算法(Label Propagation Algorithm,LPA),进一步提出了基于三元社团的LPA算法(Label Propagation Algorithm based on Ternary Community,TCLPA)。(1)基于相似度的三元社团合并算法为解决在使用相似度判别哪些节点应该被放入同一个社团时可能出现的冲突问题,该算法构建了三元社团,并将三元社团作为网络中社团合并的基本元素。该算法通过引入三元社团,有效地增强了社团内部节点之间连接的紧密程度,更加清晰的凸显了网络中的社团结构。该算法的时间复杂度为??2O tm n,其中n代表网络中的节点数目,m代表连边数目,t代表节点相似度阈值更新的次数,该算法的提出能够较好的均衡时间复杂度与正确划分率两者之间的关系。(2)基于三元社团的LPA算法针对传统LPA算法中存在的两大不确定问题,一是在对网络中节点的标签信息进行更改时其节点更新顺序的不确定问题;二是在邻居节点集合中具有节点数目最多的标签信息类型不惟一时从中选取标签信息的不确定问题,该算法在三元社团的基础上构建了网络的初始核心社团,然后结合局部最优规则和深度计算规则计算网络中其他节点的标签依赖度,并据此对这些节点的标签信息做相应标记。本文分别采用人工合成网络与真实世界网络对提出的两种算法进行实验验证,通过标准化互信息、正确划分率和模块度等指标对实验结果进行分析,同时将本文提出的两种算法与常用社团划分算法进行了对比。实验结果表明本文提出的两种算法不仅具有较高的划分精度,而且在运行效率方面也有着较好的表现。