大规模在线社交网络中社区结构发现相关技术研究

摘要

随着网络社交的普及，人类社会快速步入在线社交网络时代。在线社交网络普遍具有“社区结构”特性，社区结构的挖掘和分析已成为在线社交网络领域的一个研究热点和重点。
　　社区发现技术的研究已经开展了很多年，并取得了丰硕的成果。然而随着信息技术的进步，当前的社交网络所呈现出的大规模、高复杂性、动态演化的特征，对社区发现方法在处理速度、精确性及动态应对等方面提出了更高的要求：
　　1)快速性是社区发现的基本要求。面对规模持续膨胀的、交互不断加强的、以及群体行为不断变化的在线社交网络，如何利用更加高效的方法和技术来处理大规模在线社交网络数据，是社区发现面临的重要难题。
　　2)准确性是社区发现技术追求的目标。关于社区划分质量的衡量，虽然没有统一的标准，但在同一指标下，各种方法的优劣好坏却一目了然。如何发现社交网络中的自然意义下的真实社区划分，是所有社区发现方法前进的方向和终极目标。
　　3)高可扩展性是社区发现方法的发展方向。传统的社区发现方法缺乏可扩展性，不支持大规模并行处理，不适合处理当前千万级节点规模的在线社交网络。
　　4)社区结构的动态演化为社区发现技术带来新的挑战。在线社交网络的结构动态变化，个体及群体行为复杂多样，这给社区发现带来了新的困难和提出了更高要求。只有准确发现发展过程中的社区结构，才有可能理解和掌握社区演化的内在机理。
　　针对上述问题，本文基于MapReduce的大规模并行处理思想，精选目前优秀的社区结构发现算法infomap进行并行化，并对社区结构发现算法大规模并行化的支撑技术进行了研究，具体研究成果如下：
　　(1)提出了基于MapReduce模型的社区发现算法infomap的并行化算法inforMR，实现了infomap算法的高可扩展性。infomap算法是目前社区发现算法中精度最高的，但该算法需要大量的随机数据访问，所以一般基于内存实现，对于大规模在线社交网络而言，infomap面临计算时间和内存空间开销方面的不足。针对这一问题，inforMR首先基于分治思想，按照节点到达顺序将社交网络进行分割；然后对infomap中基于全局搜索的社区合并策略进行改进，通过局部贪婪搜索方式，减少搜索空间，并利于MapReduce实现；最后通过MapReduce编程，实现了infomap算法的大规模并行化。实验表明，该算法具有较好的可扩展性，在计算速度上具有接近线性的加速比。
　　(2)提出了基于MapReduce的多层次图划分算法DMGP。inforMR可扩展性好，但准确度与原算法比有所降低，主要是因为其采用了简单的网络划分算法，网络划分的质量较差。多层次图划分模型的实现，如Metis，是目前普遍采用的图划分方法，具有较高的划分质量，但已有算法不能满足大规模在线社交网络的分析需要。DMGP基于MapReduce模型对Metis算法进行了并行化，1)在图压缩阶段，基于MapReduce模型实现了重边匹配策略，实现了图规模以近似指数级的速度快速压缩；2)在图压缩阶段，通过大规模并行，提高I/O性能，避免了保存大量中间结果所需的开销；3)在划分的还原迭代阶段，通过大规模并行提高划分质量评估的性能和分区优化调整性能。实验表明，DMGP能对千万节点规模的在线社交网络进行有效划分，且其精度与Metis相差不到10％；基于DMGP的社区发现算法infoMR的精度与informap相当。
　　(3)提出了一个通用的基于MapReduce的社区发现框架MRHCD。传统的社区发现方法大多面临infomap同样的困境。分析总结了infoMR的实践过程后，我们认为可以将该方式推广：大规模在线社交网络中的层次社区结构发现以及非重叠社区结构发现可以通过类似的两阶段过程实现：网络划分阶段和并行社区发现阶段。MRHCD集成了DMGP和HCD。在网络划分阶段，DMGP具有较高的精度，能够胜任大规模在线社交网络的划分任务，且不破坏网络中的社区结构。在并行社区发现阶段，基于Hadoop Streaming的HCD模型在不需要修改社区发现算法业务逻辑的情况，实现了社区发现算法的大规模并行化，而且可以保证较高的社区发现精度。在实验过程中，我们在MRHCD框架部署了三个优秀层次社区发现方法，验证了提出的MRHCD可以快速实现Louvain、OSLOM等算法的大规模并行化，加速了算法的计算过程，并提高了可扩展性，同时还保持了与原算法相当的算法精度。
　　(4)提出了一种多网络协同划分算法CPMN。协同划分是跨网络社区发现的一个支撑技术，目前还缺乏相关研究。许多用户在多个社交网络中注册账号并产生行为活动。为了更加全面地了解社交网络中的社区结构，需要进行跨社交网络的协同分析。多网络比单网络规模更大，且因为分布在不同网络中的同一个体（锚点）而产生了联系。即使采用MRHCD框架，也无法处理有关联关系的跨网络的社区发现。根据锚点的分布对这些网络进行划分，锚点分布一致度较高的分区被认为是相似分区，将这些相似分区置于同一服务器处理，即可实现跨网络的协同分析。CPMN是在DMGP的基础上改进的，增加了锚点分布限制条件。CPMN在图粗化阶段引入优先级机制和纯度的概念保证和记录锚点的一致性，并通过MapReduce模型实现图的快速压缩；在初始划分阶段则通过标签传播模型得到初始划分；在细化阶段通过大规模并行实现分区调整，优化割集和分区均衡度。实验表明，CPMN框架可以有效地处理多个在线社交网络中的协同划分问题，并使得锚点的分布尽可能一致，同时该框架具有较高的处理速度和可扩展性。
　　总的来说，本文针对大规模在线社交网络中的社区发现相关问题展开研究，主要技术思路是通过大数据分析处理工具以及分治策略对已有的优秀算法进行并行化以适用于大规模网络。此外，我们还对跨网络的社区发现的支撑技术–多网络协同划分展开研究。整体上看，本文中提出的方法和框架基本都达到了设计指标，可以有效处理千万节点规模以上的社交网络。

目录

声明

第一章 绪论

1.1 社交网络概述

1.2 社区发现

1.3 社区发现面临的问题、挑战以及本文的主要工作

1.4 论文组织

第二章 基础知识

2.1 在线社交网络的图表示

2.2 社区划分质量评价指标

2.3 基准网络

第三章 基于MapReduce的并行infomap社区挖掘方法

3.1 引言

3.2 相关研究

3.3 infomap算法的MapReduce化

3.4 实验分析

3.5 小结

第四章 基于分布式图划分的并行infomap社区挖掘方法

4.1 引言

4.2 相关研究

4.3 基于MapReduce的多层次图划分框架

4.4 实验与结果分析

4.5 小结

第五章 基于MapReduce的层次社区发现通用框架

5.1 引言

5.2 相关研究

5.3 基于Hadoop Streaming的通用层次社区发现框架

5.4 实验与结果分析

5.5 小结

第六章 多网络协同划分算法研究

6.1 引言

6.2 相关定义及问题描述

6.3 多网络协同划分框架的设计与实现

6.4 实验与结果分析

6.5 小结

第七章 结束语

7.1 论文工作总结

7.2 课题研究展望

致谢

参考文献

作者在学期间取得的学术成果