基于标签传播的社区发现算法研究及其并行化

摘要

随着社交网络的不断发展，社区发现已经成为复杂网络领域的一个重要的研究热点。若干个社区组成了一个完整的网络，在社区的内部，节点之间的连接相对紧密，而社区与社区之间节点间的连接则相对松散。标签传播算法LPA(Label Propagation Algorithm)是社区发现算法中比较优秀的算法。它的线性的时间复杂度是它的一大优势。 虽然LPA有很多的优点，但是缺点也是非常明显的。由于标签的随机选择，LPA不能保证每次结果的一致性;此外，在多次迭代之后，可能会出现大的社区将小社区吞并的现象。结合以上内容，本文在LPA的基础上改进扩展出了两个算法，具体的研究成果如下所示: (1) LPA的优化改进 LPA算法不包含任何参数，主要对标签传播及更新进行优化。在基于概率和相似度的标签传播算法PSLPA(Probability and Similarity based Label Propagation Algorithm)中，结合节点间的概率以及相似度，并在标签传播的过程中使用了自适应标签选择的方式对节点标签进行更新。在基于节点权重和随机游走的标签传播算法WRWLPA(Weight andRandom Walk based Label Propagation Algorithm)中，结合节点权重和随机游走提出了一种新的相似度计算方式，在标签传播过程中利用权重和相似度进行标签的更新。这两个算法在准确性以及稳定性上都有着很优秀的表现。 (2)并行化 对于上述的两个算法均实现了并行化。采用的是Spark平台下的GraphX模块。将算法流程转化为对网络图的迭代计算过程，通过现有的API接口对网络图进行转换操作。对于标签传播过程，实现了自定义的函数，来完成算法的并行化。并行化后的算法在不同规模的数据集上均表现出了高准确性以及高稳定性。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外相关研究与应用现状

1．2．1 传统社区发现算法研究现状

1．2．2 重叠社区发现算法研究现状

1．3 研究内容

1．4 论文内容的组织

第二章 相关理论基础

2．1 相关理论

2．1．1 社交网络与图

2．1．2 社交网络中的社区结构

2．1．3 社交网络中的距离与相似性度量

2．2 标签传播算法

2．2．1 标签传播算法

2．2．2 改进的标签传播算法

2．3 Spark分布式平台

2．3．1 Spark简介

2．3．2 SparkRDD及其设计思想

2．3．3 GraphX简介

2．4 本章小结

第三章 基于概率和相似度的并行标签传播方法

3．1 K-Shell分解方法

3．2 基于概率和相似度的标签传播方法

3．3 基于概率和相似度的并行标签传播方法

3．3．1 图的构造及邻居信息收集

3．3．2 结合位置索引和邻居索引计算节点权重

3．3．3 节点问的传播概率及相似度计算

3．3．4 节点标签初始化

3．3．5 标签传播和标签选择

3．4 PSPLPA的效率分析

3．5 实验设计以及结果分析

3．5．1 实验数据集

3．5．2 评价标准

3．5．3 结果分析

3．6 本章小结

第四章 基于权重和随机游走的并行标签传播方法

4．1 随机游走的概念和相似度计算方式

4．2 基于权重和随机游走的标签传播算法

4．3 基于权重和随机游走的并行标签传播算法

4．4 时间复杂度分析

4．5 实验设计以及结果分析

4．5．1 真实网络数据集

4．5．2 人造网络数据集

4．6 本章小结

第五章 结束语

5．1 总结

5．2 展望

参考文献

作者简介

致谢