基于边界节点与标签传播的社区发现算法

摘要

目前，为了使人们能够更加准确、快速地从错综复杂的网络中挖掘出有用的信息，研究者们提出社区发现的概念。社区发现能够将复杂网络结构简单化，方便研究者对复杂网络进行深层解析以及探索其中元素之间的特征关系。因此，如何对社区结构进行合理有效地发现是近年来的研究热点。标签传播算法（LPA）是一种经典的社区发现算法，其基本思想是首先给图中节点赋予不同标签，然后经过节点标签传播迭代更新，最后将被同一标签覆盖的节点划分到一个社区。该算法因具有较高的时间效率而受到研究者们的广泛关注。但是在LPA算法执行过程中存在很多随机操作，从而影响到最终算法社区发现结果的稳定性。
　　为了有效提升标签传播算法的稳定性，本文提出了一种基于边界节点与标签传播的社区发现算法（Community Detection Algorithm based on boundary node and Label Propagation），简称LBN算法。LBN算法主要围绕以下2个关键技术进行研究：
　　（1）LBN算法在初始阶段改变了LPA算法随机对网络图中的所有节点都赋予标签的思想，而是首先挖掘出核心节点，然后对核心节点赋予标签，再通过核心节点标签传递迭代，挖掘网络图中的边界节点。此步骤有效减少LPA算法中标签更新迭代的次数，提高迭代过程的时间效率，还能够获取初始划分社区个数。
　　（2）通过核心节点对边界节点赋予权值，并选择权值大的核心节点标签，覆盖到边界节点上。当所有节点都拥有稳定的标签时，从而实现社区划分。此步骤消除了LPA算法中过多标签更新随机选择，从而提升了算法社区发现稳定性。
　　本文选取美国政治书籍网络和英国大学生社团网络2个经典测试数据集，分别测试LBN算法与LPA算法在两数据集上的社区发现结果以及算法运行时间。最后对比两算法的测试结果，表明LBN算法在保持原有LPA算法的时间效率的同时，社区发现结果具有更高的稳定性。

目录

声明

第1章 绪论

1.1 研究意义

1.2 研究现状与发展趋势

1.3 研究内容及研究目标

1.4 本论文组织结构

第2章 相关技术分析

2.1 基本概念

2.2 重叠社区发现算法

2.3 动态社区发现算法

2.4 静态非重叠社区发现算法

2.5 基于标签传播的社区发现算法

2.6 基于标签传播算法的改进算法

2.7 本章小结

第3章 基于边界节点与标签传播的社区发现算法

3.1 基本概念

3.2 LBN算法

3.3 算法创新点

3.4 本章小结

第4章 实验与结果分析

4.1 实验环境

4.2 数据集选用

4.3 实验结果

4.4 结果分析

4.5 本章小结

第5章 总结和展望

5.1 总结

5.2 展望

参考文献

致谢