基于概率模型的重叠社区发现算法研究

论文摘要

现实世界的很多复杂系统可以用网络的形式来表达,比如在社会网络和生物网络中,网络中的点表示系统中的实体,网络中的边来表示实体间的关系。随着研究的不断深入,学者们发现实际网络除了具有小世界和幂率分布等统计特性外,还具有社区结构特征。社区内部的节点之间的连接相对紧密,社区之间的连接相对稀疏。寻找复杂网络中社区结构的方法已经成为复杂网络研究的重要内容之一传统的社区发现算法主要是图形分割和层次聚类,层次聚类算法又可以分为两类：凝聚方法和分裂方法。自Newman等人提出用模块度函数来评价社区划分质量后,相继出现了一些基于模块度极值优化的方法。在真实网络中,并不是每个节点都仅属于一个社区,而是存在着重叠社区结构。随后出现了一系列重叠社区划分方法,更加真实地反映网络结构。最近,一些学者利用统计推理的方法来划分重叠社区,其中一个简单的概率算法——SPAEM能很好地发现重叠社区。本文在深入理解SPAEM算法的基础上,通过实验发现该算法存在一些缺陷,比如在大规模网络中效率比较低,随机初始化使得算法容易陷入局部最优解等。首先,对SPAEM算法的时间复杂度进行了详细分析；然后,对算法做了一些改进,降低了算法时间复杂度；此外,为了避免算法陷入局部最优解,本文还提出了种SPAEM算法的初始化方法,使算法可以在更短的时间内获得更好的社区发现结果。基于真实网络和人工网络的实验结果证明了改进算法的有效性。在很多实际网络中,改进算法的社区发现结果要好于其他重叠社区发现算法。在人工网络,尤其是非常稀疏的网络中,改进算法也能得到很好的社区发现结果。

论文目录

• 致谢
• 中文摘要
• ABSTRACT
• 1 引言
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 研究内容及主要工作
• 1.4 论文的组织结构
• 2 社区发现理论基础
• 2.1 网络的基本性质
• 2.1.1 网络的图表示
• 2.1.2 聚类系数
• 2.1.3 平均路径长度与介数
• 2.1.4 度分布
• 2.2 社区发现算法
• 2.2.1 传统图类及聚类方法
• 2.2.2 分裂方法
• 2.2.3 基于模块度优化方法
• 2.2.4 基于统计推理的方法
• 2.2.5 重叠社区发现算法
• 2.3 社区结构评价标准
• 2.4 小结
• 3 SPAEM概率模型
• 3.1 概率混合模型及参数估计
• 3.1.1 概率混合模型
• 3.1.2 EM算法
• 3.2 SPAEM模型
• 3.2.1 算法思想
• 3.2.2 参数估计
• 3.2.3 重叠节点
• 3.2.4 算法分析
• 3.3 小结
• 4 SPAEM算法改进
• 4.1 模型求解优化
• 4.1.1 SPAEM算法时间复杂度分析
• 4.1.2 EM迭代优化
• 4.2 初始值优化的改进SPAEM算法
• 4.2.1 算法思路
• 4.2.2 初始化方法
• 4.3 小结
• 5 实验及结果分析
• 5.1 实验设置
• 5.2 实验评价标准
• 5.2.1 准确度标准
• 5.2.2 时间复杂度标准
• 5.3 基于真实数据的实验
• 5.3.1 Karate数据集
• 5.3.2 Dolphins数据集
• 5.3.3 Netscienee数据集
• 5.3.4 Power数据集
• 5.3.5 protein-protein数据集
• 5.3.6 Blogs数据集
• 5.3.7 word-assoeitaion数据集
• 5.3.8 PGP数据集
• 5.4 基于人工数据的实验
• 5.5 结果分析
• 5.5.1 基于真实数据的准确率分析
• 5.5.2 基于真实数据的效率分析
• 5.5.3 基于人工数据的结果分析
• 5.6 小结
• 6 结论
• 6.1 论文工作总结
• 6.2 未来的研究工作
• 参考文献
• 学位论文数据集