超大规模社交网络中基于结构与主题的社团挖掘

摘要

社团挖掘作为复杂网络分析中的一个重要方法，近年来越来越多的研究者将其应用到社交网络分析、万维网服务、网络可视化等具体问题中。目前许多社团挖掘算法复杂度高，难以处理大规模网络，本文利用Graphlab平台分布式实现社团挖掘算法以适用于大规模网络分析。
　　本文的主要工作包括如下三个方面：
　　(1)提出了基于初始社团和可信度的改进标签传播(LPA)算法。传统的标签传播算法在Graphlab平台上存在不收敛和划分不稳定等问题。为了解决这些问题，本文从如下两个方面对LPA算法进行改进：首先选择网络部分节点作为中心节点，将中心节点及其一阶邻居初始化为同一社团，从而大幅降低了标签传播算法的初始社团数目；然后为网络中每条边定义一个可信度，可信度越高表明邻居节点的标签越可信，在标签传播过程中根据可信度改进随机选择策略。在仿真网络和真实网络上，对改进LPA算法进行了测试，实验表明改进LPA算法的划分结果更加稳定和准确。
　　(2)在BIGCLAM算法基础上提出了结合网络拓扑结构和用户主题信息的社团生成模型。web2.0技术催生了大量用户生成内容的网络(如Facebook、Twitter、GooglePlus)，用户在这些网络上留下了大量主题信息，本文将这些信息引入到社团挖掘中。在社团生成模型中，假设社团生成了网络连边和节点主题，进而建立网络的似然函数，利用邻接矩阵和节点主题极大化似然函数，最后得到节点所属的社团。在主题社交网络上对社团生成模型进行测试，实验结果表明引入主题信息对社团划分性能有所提升。
　　(3)在由4台普通PC组成的Graphlab集群上实现本文改进的算法，并对比分析了算法在Graphlab集群上的性能。实验结果表明算法在Graphlab集群上取得了较高的加速比。
　　本文的社团生成模型输入参数为网络的社团数目，而社团数目通常是未知的，虽然可以通过不断迭代求得网络最有可能的社团数目，但计算开销很大。因此将社团生成模型改造为无参数算法是下一步需要研究的工作。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 本文主要研究内容

1.4 本文结构安排

第二章 社团挖掘基础知识及Graphlab分布式平台

2.1 社团挖掘基础知识

2.2 基于图谱分析的分布式平台Graphlab

2.3 本章总结

第三章 基于结构的非重叠社团挖掘

3.1 并行化实现标签传播算法

3.2 基于初始社团和可信度的改进LPA算法

3.3 实验结果

3.4 本章总结

第四章 结合主题的重叠社团挖掘

4.1 社团生成网络连边和节点主题

4.2 社团生成模型

4.3 模型复杂度分析

4.4 实验结果

4.5 本章总结

第五章 社团挖掘算法的分布式并行化

5.1 改进LPA算法Graphlab分布式并行化

5.2 社团生成模型Graphlab分布式并行化

5.3 实验结果

5.4 本章总结

第六章 总结与展望

6.1 全文总结

6.2 进一步研究工作

致谢

参考文献

攻读硕士期间取得的成果