基于仿射传播的复杂网络社区发现算法研究

摘要

许多研究表明，复杂网络中普遍存在着社区结构，即社区内部的节点联系紧密，而社区之间的节点联系则相对稀疏。复杂网络内部的社区结构具有十分重要的理论意义和应用价值，可以帮助人们理解复杂网络的功能、发现复杂网络中潜在的规律和预测复杂网络的行为。
　　本研究提出一种基于结构相似度仿射传播的社区发现算法(SS-FAP)。该算法首先选取结构相似度作为节点之间的相似性度量，并采用一种优化的方法来计算相似度矩阵；其次将计算得到的相似度矩阵作为输入，采用快速仿射传播算法进行聚类；最后得到最终的社区结构集合。实验结果表明，无论在模拟网络上还是在真实网络上，SS-FAP都具有很好的社区发现能力，能够发现高质量的社区结构。提出一种基于模块度仿射传播的社区发现算法(MAP)。该算法的主要思想是将模块度函数Q嵌入到AP算法的迭代过程中，基于模块度优化来得到最优的社区发现结果。实验结果表明，与传统的LPA算法、FN算法、BGLL算法以及原始的AP算法对比，MAP算法能够更加有效地发现网络中的社区结构。实现一个社区发现算法原型系统，该原型系统主要实现了SS-FAP算法、MAP算法、LPA算法以及4种社区发现评价标准，分别是规范化互信息、FM指标、准确率与模块度，并且利用力引导布局算法来可视化显示网络。

目录

声明

致谢

1绪论

1.1研究背景与意义(Research Background and Significance)

1.2 研究现状及存在的问题(Research Overview and Existing Problems)

1.3研究内容及组织安排(Research Contents and Organization)

2相关理论基础

2.1引言(Introduction)

2.2复杂网络的表示(Representation of Complex Networks)

2.3社区结构(Community Structure)

2.4仿射传播算法(Affinity Propagation Algorithm)

2.5社区发现的评价方法(The Evaluation Methods of Community Detection)

2.6本章小结(Summary)

3基于结构相似度仿射传播的社区发现算法

3.1引言(Introduction)

3.2 基于结构相似度仿射传播的社区发现算法(Community Detection Algorithm based on Structural Similarity Affinity Propagation)

3.3实验(Experimental Results)

3.4本章小结(Summary)

4基于模块度仿射传播的社区发现算法

4.1引言(Introduction)

4.2基于模块度仿射传播的社区发现算法(Community Detection Algorithm based on Modularity Affinity Propagation)

4.3实验(Experimental Results)

4.4本章小结(Summary)

5社区发现算法原型系统的实现

5.1引言(Introduction)

5.2系统框架(System Framework)

5.3系统设计(System Design)

5.4系统展示(System Display)

5.5本章小结(Summary)

6总结与展望

6.1总结(Conclusion)

6.2展望(Future Work)

参考文献

作者简历

学位论文数据集