标签传播算法在重叠社区发现中的改进

摘要

现实生活中到处都存在着复杂网络结构，随着信息技术的发展，复杂网络也越来越广泛被关注和研究，社区发现不仅可以帮助人们更加具体的了解复杂网络的功能和特性，还能更加深入的帮助人们了解社会网络存在的社会问题，因此社区发现具有越来越重要的意义。在真实网络中，重叠社区发现也越来越普遍，与此同时，研究者们提出了大量的重叠社区发现算法，包括CPM算法、LFM和GCE算法、COPRA算法等，与其他重叠社区发现算法相比，标签传播算法具有简洁高效的优势。
　　本文在原有COPRA算法的基础上，对标签初始化、标签传播和标签选择三个方面进行改进，提出了一种新的基于标签传播思想的重叠社区发现算法。本文算法主要做出的改进有：提出度数阈值d0的概念，引入CPM完全子图的思想，提出标签综合影响度概念，使用标签异步传播思想。通过这几个方面的改进，旨在解决算法的随机性，提高结果的准确性和算法的稳定性。
　　本文最后通过大量的实验来研究分析LFR基准数据集中混合系数μ、COPRA算法中参数v以及改进的COPRA算法中参数d0对CPM算法、COPRA算法以及改进的COPRA算法时间复杂度和结果准确性的影响，结果证明，无论是稀疏网络还是稠密网络，本文算法都能发现更高质量的社区结构。最后在真实网络数据集中实现改进后的COPRA算法，最后证明该算法挖掘的重叠社区具有更高的模块度，能更好的反映社区关系，能够更加有效的发现重叠社区结构。

目录

1 绪 论

1.1社区发现背景和意义

1.2社区发现算法国内外研究现状

1.3本文的研究内容

1.4本文的组织结构

1.5本章总结

2 基于标签传播的重叠社区发现算法

2.1社区发现及相关理论研究

2.2社区发现算法介绍

2.3非重叠社区发现的标签传播算法

2.4重叠社区发现的标签传播算法

2.5算法分析及改进思路

2.6本章总结

3 标签传播算法的改进

3.1标签初始化阶段

3.2标签传播阶段

3.3标签选择阶段

3.4本章总结

4 实验及分析

4.1实验平台和数据集

4.2实验分析

4.3本章总结

5 总结与展望

5.1论文总结

5.2研究展望

致谢

参考文献

附录

A. 作者在攻读学位期间发表的论文目录：