基于Hadoop的面向web规模图数据的社区发现算法的研究与实现

摘要

来自于真实世界许多不同区域或者覆盖范围的数据集可以表示成社交网络的形式，而且这种表示形式是非常的自然、简洁、有意义。为什么这么说呢？因为这种形式反映巧妙的表达了一种社会化的关系网络。Internet的兴起，尤其是Web2.0应用的强势崛起极大地拓展了真实世界中的社交关系网络。社交网络应用的流行积累越来越多的关系网络数据（也就是图数据），对社交网络数据的分析可以发现这个社交网络的组织模式以及该网络背后隐藏的一些属性。 社区发现和分析是一种重要的通过把大规模网络分割成小的子网络（也就是社区）从而分析复杂的大规模网络来达到理解真实世界网络关系的技术手段，已经在很多的领域中得到了应用。比如，基于兴趣爱好的主题推荐、生物信息学领域中基因调控网络分析、基于浏览习惯的新闻、商品推荐以及根据流行病的传播网络，通过对网络的分析找出网络中传染病的关键社区以及传播源的关键结点等。尤其是最近几年，社交网络应用的强势崛起积累的大量的相关的在各个领域中的数据，这些数据规模都很大，需要通过社区发现等相关的技术来进行分析才能得到利用，从而为经济和社会来服务。因此，对于社区发现这个主题的研究具有重要的理论意义和应用价值。 近些年来，许多针对具有数百万条边的图数据的算法先后不断被提出来。这类算法由于面对的是仅仅只有数百万条边的图数据，因此它们的一个共同的特点就是都是在单节点在内存中来对图数据进行运行和分析的。然而，随着大数据时代的来临，随着图数据的增长，大量的图数据得到积累保存，形成了超大规模的具有数十亿条边的图数据。针对这种超大规模的图数据，使用前面提到的在单节点在内存中运行的算法来进行分析是不可能达到目标的。好在随着分布计算技术的兴起，直至今天分布式计算技术已经非常的成熟，出现了以Hadoop为代表的开源的分布式计算平台。像Hadoop这种成熟的分布式计算平台的出现给这个大数据时代的针对海量数据的分析提供了可能性。我们的方法就是在Hadoop平台上利用分布式的算法来处理具有数十亿条边的图数据。 在这篇论文中，展示了如何在有数十亿条边的这种超大规模的图数据中发现社区的。我们的方法基于一种集成学习的社区发现方案。这种方案提供了一种从由较低质量分割组成的集合中识别出高质量的分区的方法。提出了一种针对社区发现算法进行预处理的方法。通过这种预处理的方法可以显著地降低要处理的问题的规模。降低了要处理的问题的规模以后，传统的非分布式的社区发现算法就可以进行应用了。在分布式计算框架Apache Hadoop上面实现了一个弱化的但却是可高度扩展的的标签传播算法。通过对在Apache Hadoop集群上实现的社区发现算法在多达33亿条边的图数据集上的评估，发现该评估展现了在社区质量以及可扩展性方面取得了非常不错的结果。对于一个比较小的只有2.6亿条边的图数据集，结果显示我们的预处理方法同样可以提高基于模块化优化的社区发现算法的结果。在社区发现的研究过程中诞生了非常多的经典的集中式的社区发现算法，在这篇论文中我也选取了非常经典的GN算法来进行实现和分析。

目录

声明

摘要

第1章绪论

1．1社区发现的研究内容

1．2研究背景及意义

1．2．1研究背景

1．2．2研究意义

1．3国内外研究现状

1．4本文的主要工作及本文贡献

1．5本文的组织结构

1．6本章小结

2．1符号定义

2．2基本概念定义

2．2．1社区的定义

2．2．2图论中的若干基本概念

2．2．3模块度的定义

2．3 Hadoop平台简介

2．3．1 HDFS简介

2．3．2 MapReduce简介

2．3．3 Hadoop国内外应用现状

2．4本章小结

第3章GN算法的原理与实现

3．1 GN算法中相关定义

3．2 GN算法设计的总体框架

3．3 GN算法中边介数的计算

3．3．1边介数计算方法的原理

3．3．2边介数计算的两种情况

3．4 GN算法的实现

3．5 GN算法的改进

3．5．1改进的GN算法的框架

3．5．2改进的GN算法的测试

3．6本章小结

4．1引言

4．2相关定义

4．3一种分布式的社区发现算法的原理

4．3．1集成学习的框架

4．3．2算法的原理

4．3．3生成图分割集合的基础算法

4．4．1分布式社区发现算法的框架

4．4．2分布式核心组的检测

4．5本章小结

5．1引言

5．2实验数据

5．3实验环境及工具

5．4实验及结果分析

5．5本章小结

第6章总结与展望

6．1内容总结

6．2未来展望

参考文献

致谢