基于线图与标签传播的重叠社区发现算法研究

摘要

随着社会关系网络等复杂网络的快速发展，复杂网络中的社区发现已经成为了一个研究热点。作为其中的一个分支，重叠社区发现更接近真实的网络结构，因而具有重要的研究和实践意义。目前，基于节点的标签传播算法具有简单和快速发现社区的优点，因而在重叠社区发现研究领域里被广泛应用。但是该类算法的随机性较强，有时甚至会把所有的节点划分到一个社区。因此，为了发现复杂网络中的重叠社区并提高基于标签传播算法的鲁棒性，考虑到以边为研究对象相对于传统的基于节点的划分具有独特的优势，即可以自然地获得重叠社区，本文以边为研究对象，提出了一种基于线图与标签传播的重叠社区发现算法。此外，为了快速发现较大规模网络中的重叠社区，本文在前面提出的算法基础上做了改进，提出一种基于线图的重叠社区的合并与优化算法。本文的主要研究工作如下:
　　(1)由于标签传播算法的随机更新顺序以及更新标签的随机选取，导致其随机性较强，因此，为了提高重叠社区发现中基于标签传播方法的鲁棒性和准确性，本文以边为研究对象，提出了一种定向标签传播算法，即基于线图与标签传播的重叠社区发现算法(LLPA)。LLPA提出种子边的概念，并根据其他边与种子边之间的相似度，来定向地传播标签，从而提高算法的鲁棒性。同时，为了提高算法的准确性，LLPA算法从提高模块度的角度对重叠社区进行了合并与优化。在LFR基准网络和真实网络数据集上的实验结果表明，LLPA算法在重叠社区发现上比已有的基于标签传播思想的算法有更高的鲁棒性和准确性。
　　(2)考虑到从提高模块度的角度来优化基于线图得到的重叠社区时，大量的计算量使其无法适用于较大规模的网络，本文又提出了一种合并与优化基于线图的重叠社区算法，MOOCLG算法。为了适用于较大规模网络，MOOCLG算法通过设置两个阈值，使其只利用节点的重叠社区信息和重叠节点信息来合并高重叠社区及过滤掉不合适的重叠节点，从而提高算法的准确性并大大减少时间复杂度。通过在较大规模的LFR基准网络和真实网络上的实验表明，MOOCLG算法比通过模块度来优化重叠社区的算法的运行速度明显加快，而且准确性也高。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1 基于边划分的重叠社区发现算法国内外研究现状

1．2．2 基于标签传播的重叠社区发现算法国内外研究现状

1．3 本文的主要工作及内容安排

第2章 复杂网络社区发现的相关基础

2．1 复杂网络社区结构相关定义

2．2 社区结构评价标准

2．2．1 模块度

2．2．2 归一化互信息

2．3 复杂网络线图的相关定义及其与原始图的相互转换

2．3．1 线图定义

2．3．2 线图与原始图之间的相互转换

2．4 本章小结

第3章 基于线图与标签传播的重叠社区发现算法

3．1 基于线图与标签传播的重叠社区发现算法

3．1．1 算法流程

3．1．2 种子边

3．1．3 标签传播

3．1．4 优化重叠社区

3．1．5 算法时间复杂度分析

3．2 实验与分析

3．2．1 LFR基准网络上的实验

3．2．2 真实网络上的实验

3．3 本章小结

第4章 基于线图的重叠社区的合并与优化算法

4．1 基于线图的重叠社区的合并与优化算法

4．1．1 算法流程

4．1．2 高度重叠社区的合并

4．1．3 过滤操作

4．1．4 算法时间复杂度分析

4．2 实验与分析

4．2．1 LFR基准网络上的实验

4．2．2 真实网络上的实验

4．3 本章小结

第5章 结论与展望

5．1 工作总结

5．2 未来展望

致谢

参考文献

附录