基于进化算法和节点局部信息的复杂网络社区检测

摘要

复杂网络的社区检测问题是指利用网络中节点之间相互连接的拓扑结构关系，找出图形中内部连接相对紧密、外部连接相对稀疏的社区结构。针对这些社区结构的研究，有助于我们更好的探测到复杂网络的拓扑结构层次图，从而挖掘网络中个体元素的特性和有用信息。随着计算机科学技术的不断发展，复杂网络的应用模型不断渗透到科学研究和数据信息挖掘的各个方面，相应的研究算法如层次聚类的算法、谱聚类的算法和基于进化的目标优化的算法等相继被提出。然而，目前存在的这些算法存在着准确率较低、收敛速度较慢等的问题。同时，随着信息时代的到来，复杂网络的规模也在不断增长，现有的算法已经很难高效的检测到大规模中存在的社区结构。因此，本文根据上述问题，分别设计了以下三种社区检测的算法，主要工作如下：
　　(1)提出了一种基于近邻传播的进化多目标优化算法来解决社区检测问题。将经典快速的数据聚类的方法，即近邻传播算法和基于多目标优化的进化算法相结合，在利用数据聚类算法有效快速地获得网络预划分结果的同时，利用多目标进化算法的全局寻优性，最终使得社区检测的结果达到更好的划分精度，同时得到较好的收敛速度。
　　(2)提出了一种基于局部核节点和社区融合策略改进的标签传播算法以解决大规模复杂网络的社区检测。标签传播算法是一种半监督学习的算法，针对大规模网络的社区检测具有很低的时间复杂度，仅为O(m)。然而LPA算法的聚类结果具有较大的随机性，根据每次在节点上标签传播的顺序不同，得到的社区结构差异很大。因此本算法在标签传播算法的基础上设计加入了一种基于局部核节点和社区融合的策略，利用核节点与其邻居节点之间相似度关系，先形成局部小社区，然后通过核节点与核节点之间的关系对这些小社区进行有选择的合并，然后在此基础上再对所有节点按照标签传播的思想赋予标签。该算法在继承了标签传播算法时间复杂度较低的优点同时，进一步提高了算法的检测精度。在大规模真实网络的实验结果上表明了该算法要优于标签传播算法。
　　(3)提出了一种基于节点隶属度和子社区融合的大规模社区检测方法。该方法首先根据提出的局部邻居节点间隶属度函数，将亲密度较高的节点对融合，实现对网络进行预处理，提高现有算法精度的同时可以快速挖掘局部潜在的完全子图结构。其次，根据提出的局部节点与相邻社区间的隶属度函数，对得到的网络进行修正，并且通过调解节点与相邻社区隶属度函数的参数，可以在精确检测到非重叠社区的同时涉及到重叠社区的检测。同时由于本算法采用了标签传播的算法框架，具有较低的时间复杂度，可适用于较大规模网络的社区检测问题。在人工网络和现实网络上的实验结果表明，本算法结果相比于现有经典算法更准确有效。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景和意义

1.2现有社区检测的相关方法研究

1.3 现有复杂网络社区检测主要研究方向

1.4 论文结构安排

第二章 基于近邻传播的进化多目标优化社区检测方法

2.1 算法设计动机

2.2 AP算法基本原理

2.3 基于近邻传播的进化多目标优化社区检测方法设计

2.4 仿真实验及结果分析

2.5 本章小结

第三章 基于局部核节点和社区融合策略的标签传播算法

3.1标签传播算法介绍

3.2 基于局部核节点和社区融合策略的标签传播算法

3.3 实验结果及分析

3.4 本章小结

第四章 基于节点隶属度和子社区融合的大规模社区检测方法

4.1 算法设计相关背景及动机

4.2 基于节点隶属度和子社区融合的大规模社区检测方法

4.3 算法时间复杂度分析

4.4 实验结果及分析

4.5总结

第五章 结论和展望

5.1 本文工作总结

5.2 未来工作的展望

致谢

参考文献

作者简介