X-RIME：基于 Hadoop 的大规模社会网络分析

              声明：下面论文由《免费论文教育网》  http://www.PaperEdu.cn  用 户转载自互联网，版权归原作者所有，本文档仅供参考，严禁抄袭！                  《免费论文教育网》          http://www.paper.edu.cn - 1 - 中国科技论文在线 X-RIME：基于 Hadoop 的大规模社会网络分析# 杨寅* 基金项目：国家 973 项目（ 2009CB320504）；国家自然科学基金创新研究组（ 60821001）；高等学校博士 学科点专项科研基金（ 20090005120012）；国家重点科学与技术专项项目：下一代宽带无线移动通信网络 （2010ZX03004-001-01） 作者简介：北京邮电大学网络与交换技术国家重点实验室研究生，主要研究方向是分布式与并行计算 . E-mail: bobten2008@gmail.com （北京邮电大学网络与交换技术国家重点实验室，北京 100082） 摘要：随着 SNS（Social Networking Sites, 社交网站）如 Renren、Facebook 等的快速发展， SNA(Social Network Analysis，社会网络分析)逐渐成为研究的重点。 现代 SN（Social Network， 社会网络）往往都是几百万甚至上千万的超大规模数据集，因此如何处理大规模的社会网络 数据集成为传统的社会网络分析算法具面临的一个较为严峻的挑战。本文将介绍 X-RIME： 基于 Hadoop 的大规模社会网络分析工具，能够对大规模的数据集进行社会网络分析，具有 良好的扩展性和通用性。本文还简单分析了适合用 MapReduce 编程模型进行分布式并行化 的算法应该具有的特征，最后在仿真实验中举例说明了 X-RIME 的社会网络分析能力。 关键词： 社会网络分析； X-RIME；HADOOP；云计算 中图分类号：TP39 X-RIME: HADOOP-BASED LARGE-SCALE SOCIAL NETWORK ANALYSIS Yang Yin (State Key Laboratory of Networking & Switching Technology, Beijing University of Posts & Telecommunications, Beijing, 100082) Abstract: With the fast development of Social Networking Sites (SNS) such as Renren, Facebook, etc., Social Network Analysis (SNA) is becoming a hot research area. However, considering a typical SNS consists of millions to tens of millions of ultra-large-scale data sets, how to deal with such large-scale Social Network (SN) data sets becomes a great challenge for existing SNA tools. Towards this problem, this paper proposes X-RIME: a Hadoop-based analysis tool for large-scale social network. We show that X-RIME can efficiently deal with large-scale data sets, with great expandability and universality. We also briefly analyze the necessary features for an algorithm to be implemented with MapReduce programming model, in a distributed and concurrent way. Finally, we demonstrate the SNA abilities of X-RIME with extensive experiment results. Key words: Social Network Analysis; X-RIME; HADOOP; Cloud Computing 0 引言 随着近几十年互联网的飞速发展， 世界范围内的互联网用户数都在迅速增长并与之同时 涌现出了一大批社交网站如 Renren、Facebook 等。随着这些网络用户数量的迅速增加，海 量的用户数据被不断地制造出来。如何从这些海量的用户数据中获取更深层次的有用信息， 从而进一步挖掘商业价值、 理解商业行为以及发现新的业务增长点成为一个重要的研究方向 以及挑战。 社会网络分析是分析社会性数据的重要技术手段，它强调分析社会个体之间的关系 [1]， 它的基础模型是图论的图模型，在这个模型里，社会网络中的个体被视为图里的结点 v ，结 点的集合为V ；个体之间的关联被视为图里面的边 e ，边的集合是 },|),({ VvVuvueE ∈∈= ，因此整个模型就可以看作是 ),( EVG = 。通过这种映射，我 http://www.paper.edu.cn - 2 - 中国科技论文在线 们可以将现实社会中的个体关系网转化为用结点和边表示的图模型， 然后利用一系列的社会 网络分析算法和工具对其进行深入分析和挖掘。 同传统的围绕能动者属性进行的统计性社会 分析不同，社会网络分析认为能动者之间的关系和联系要比能动者的属性更为重要。这种视 角使得它非常适合解释很多真实世界中的现象， 因此在数据挖掘和商业智能领域得到了广泛 的应用。典型应用有异常客户识别，客户多重身份识别，客户价值分析，客户流失分析，客 户社群发现等等。经过长时间的研究积累，大量用于社会网络分析的算法被提出来，典型的 有 K-核算法，社区发现算法， PageRank 算法等；大量的社会网络分析工具也被开发出来， 典型的有 GRADAP，STRUCTURE 和 PAJEK 等。 图 1 典型社会网络 Fig.1 A Typical Social Network 互联网规模的快速扩大导致了用户数据规模迅速增加， 从而给社会网络分析算法和工具 带来了新的要求和挑战，即大规模数据集的处理和分析能力。传统的社会网络分析算法和工 具往往都是单机形式的， 在面对大规模数据集的时候往往会出现存储和处理能力不足等方面 问题，再加上原始输入数据和社会网络的内部表示都属于无结构或者半结构化数据，传统关 系数据库并不擅长处理此类数据， 使得利用传统的社会网络分析算法和工具对大规模数据集 进行处理变得更加困难。基于此，我们开发了 X-RIME[2]。X-RIME 是一个开源的社会网络 分析工具，它提供了一套基于 Hadoop 云计算环境的大规模社会网络 /复杂网络分析工具包， 在 Map/Reduce 的框架上对十几种社会网络分析算法进行了并行化与分布式化，从而实现了 对互联网级大规模社会网络 /复杂网络的分析。 本文主要介绍以下方面的内容：第一部分介绍 X-RIME 的系统框架，包括 X-RIME 的 系统设计，数据模型以及处理模型。第二部分我们举例说明了 X-RIME 算法库并分析了适合 用 MapReduce 实现的算法所应具有的主要特征。第三部分是相关的仿真实验。最后是工作 总结与展望。 1 系统框架 X-RIME 基于 Hadoop，Hadoop 是 Appache 开源分布式运算工具和分布式文件系统的集 合。Hadoop 主要包括三个部分， 分别为： Hadoop 分布式文件系统（HDFS, Hadoop Distributed File System）[3]，MapReduce[4]以及 Hbase[5]。如图 2 所示为 X-RIME 的系统架构，其设计 思想是：首先在 HADOOP 的 HDFS 存储系统之上构建一套适合用于大规模社会网络分析的 数据模型，基于该数据模型利用 MapReduce 实现一系列用于社会网络分析的分布式并行算 法，最后构建出 X-RIME 处理模型，即 X-RIME 工具链。 http://www.paper.edu.cn - 3 - 中国科技论文在线 图 2 X-RIME 系统架构 Fig.2 X-RIME System Structure 1.1 数据模型 社会网络的本质模型是图模型， X-RIME 的主要工作是基于 Hadoop 进行大规模社会网 络分析，因此 X-RIME 的底层数据模型必须满足该要求，即 X-RIME 的数据模型是支持大 规模社会网络分析的图模型，基于此我们设计了 X-RIME 数据模型（ X-RIME Data Model） 如图 3 所示。 图 3 X-RIME 数据模型图 Fig.3 X-RIME Data Model X-RIME 数据模型主要有以下几部分构成： z GraphAlgorithm：代表 X-RIME 中的算法 z GraphAlgorithmContext：X-RIME 算法的执行上下文，包含算法执行时需要的各种参数 z Graph：代表一个 X-RIME 框架下的图实例 z Element：X-RIME 中元素表示的基本单位 z Vertex：代表 X-RIME 中的结点类型 z Labels：用来承载附加的标签信息 z AbstractEdge：代表 X-RIME 中的边类型 z WeightOfEdge: 用来表示边的权值信息 X-RIME 的数据模型适合做大规模社会网络分析，主要是由于具备以下三点关键特征： z 以 HADOOP HDFS 云存储平台为基础 http://www.paper.edu.cn - 4 - 中国科技论文在线 X-RIME 数据模型中定义的所有数据类型都是基于 HADOOP HDFS，从而实现海量数据 的高效存储。 z 完备的图模型定义 X-RIME 的数据模型是我们在充分考虑了社会网络分析的基础模型图模型之后定义的， 具有很强的完备性，足够支撑社会网络分析。 z 较强的灵活性 X-RIME 的数据模型在设计的时候充分考虑了以后的扩展需求，因此具备较强的可扩展性和 灵活性。 1.2 处理模型 基于 X-RIME 的数据模型我们开发了 X-RIME 算法库，包含十几种 Hadoop 下的社会网 络分析算法。在此之上我们构建了 X-RIME 的处理模型即 X-RIME 工具链（ X-RIME Tool Chain）用来驱动 X-RIME 进行社会网络分析。 如图 4 所示，X-RIME 工具链主要包含 4 个 步骤：待分析原始数据的获取、待分析原始数据的预处理，待分析数据的社会网络分析，结 果数据的后续处理。 图 4 X-RIME 工具链 Fig.4 X-RIME Tool Chain 为了对诸如论坛、社交网站之类的社会网络进行数据分析，我们必须首先获取这些网络 的原始数据。项目中我们基于 WebHarvest [7] 开发了 X-RIME Web 数据抓取系统，用来抓 取需要分析的目标网站数据。 由于 X-RIME 处理的数据具有特定的格式， 因此我们需要将得到的待分析原始数据进行 预处理，将其转化为 X-RIME 可以处理的数据格式。 数据全部经过预处理之后，就是对数据进行具体分析和处理，这一步的关键是我们开发 的 X-RIME 算法库（ X-RIME Algorithm Library）。 经过 X-RIME 算法库的处理，我们得到了一系列中间结果，但是这些中间结果是 HADOOP 下的二进制文件，易读性和易处理性很差，因此需要使用 X-RIME Post-processing Tool 将其转换为易读的和易处理的文本形式。 2 X-RIME 算法库 X-RIME 算法库是 X-RIME 的核心部分， 决定了 X-RIME 的社会网络分析能力的大小与 强度。为了支撑 X-RIME 的社会网络分析能力，我们基于 HADOOP 开发了十几种大规模分 布式并行社会网络分析算法。 这些算法都有一个共同的特点，即：都是基于 Hadoop 的大规模分布式并行算法。并不 是所有算法都适合用 MapReduce 来实现，通过分析和总结我们发现适合用 MapReduce 实现 的算法应该在数据上和计算上具有较强的可划分性。MapReduce 编程模型的主要特点是对 http://www.paper.edu.cn - 5 - 中国科技论文在线 数据基于 对进行划分从而得到不同的数据块，然后对不同的数据块进行并行 计算同时得到新的数据块，最后对得到的新数据块进行合并。这就首先要求数据块在数据上 和计算上具备较强的可划分性， 其本质就是划分得到的数据块之间在并行计算时具有较少的 关联性甚至不具备关联性。具备该条件的算法往往比较适合用 MapReduce 来实现。下面将 介绍 X-RIME 中的广度优先搜索（ BFS）算法，说明 BFS 算法是如何符合该特点的。 图 5 BFS MapReduce 化示意图 Fig.5 Diagram of BFS MapReduce Procedure 传统的 BFS 算法基于队列对图中的结点进行遍历； MapReduce 下的 BFS 算法是在传统 BFS 算法思想的基础上进行改进从而实现分布式与并行化。 如图 5 所示， 我们定义 )(idist 表 示结点i 距离初始结点的距离大小； )(istage 表示结点 i 所处的阶段，这样 1)()( += idististage 。按照传统的方法，我们是先访问点 A，然后将其邻居结点 B，C（第 二阶段结点）分别加入队列，接着从队列中先后取出 B 和 C 并访问他们。那么对这个算法 进行 MapReduce 化的关键在于将“从队列中先后取出 B 和 C 并访问其邻居结点 ”变为“同时取 出 B 和 C 并访问其邻居结点 ”。这样处于同一阶段的各个结点都能够并行工作。 Edge Mpaper Re-emit Reducer Iterator () Node Type Destination Visited Re-emit Vertex Discard Yes Visit This Vertex For every edge, visit and emit edge All Nodes Visited End Yes No 图 6 BFS MapReduce 流程图 Fig.6 BFS MapReduce Flow Chart http://www.paper.edu.cn - 6 - 中国科技论文在线 图 7 BFS Mapper 和 Reducer 伪码 Fig.7 The Pseudo Code of BFS Mapper and Reducer 通过上述分析我们知道，处于同一阶段的结点由于距离初始结点距离相同，因此具有相 同的计算优先级，所以他们之间在计算上是可以划分的。根据新的划分思想，我们设计出了 MapReduce 下每个结点的运行流程图如图 6 所示，用伪码描述如图 7 所示。 BFS Mapper 的 工作只是将收到的键值对再次抛出去；具有相同键值即结点 ID 的 Node 都会在一个 Reducer 中被处理，于是 Reduce 会收集到一个代表该结点的 Node 以及若干个代表其他结点对该结 点进行访问的边信息。如果该结点已经被访问过则丢弃这些边信息，否则先访问该结点，访 问中要向其邻居结点抛出边访问信息。最后就是将结点信息再次抛出。基于 HADOOP 的 BFS 算法具有较高的执行效率，如果用 depth 表示目标图的深度，由于每一层都能够并行执 行，所以其时间复杂度为 )(depthO 。 X-RIME 算法库比较丰富，目前主要包含如下算法： „ vertex degree statistics „ weakly connected components (WCC) „ strongly connected components (SCC) „ bi-connected components (BCC) „ ego-centric network density „ bread first search / single source shortest path (BFS/SSSP) „ K-core „ maximal cliques „ pagerank „ hyperlink-induced topic search (HITS) „ minimal spanning tree (MST) „ grid variant of Fruchterman-Reingold network layout algorithm „ triangle-based community discovery algorithm „ Recommendation Algorithm http://www.paper.edu.cn - 7 - 中国科技论文在线 3 X-RIME 应用举例 我们选取水木社区进行测试。水木社区是我国目前最大的 BBS 之一。利用 X-RIME 中 的数据抓取系统，我们于 2009 年 6 月 25 日至 28 日抓取了水木社区的全部版面信息，并进 行了预处理。预处理后得到的信息数据主要有：用户属性信息，每个版的用户关系（ A 发帖 子，B 回复 A 的帖子，则 A 和 B 之间存在关系）。我们将从客户价值发现以及客户社群发 现两个方面来举例说明 X-RIME 的社会网络分析能力。 3.1 客户价值发现 随着互联网快速发展，互联网企业都拥有了大量的客户，并且还在不断增加。这些客户 自身的价值是存在差异的， 因此从大量用户中寻找有价值的活跃用户和核心用户对互联网企 业具有很大的意义。 用户在用户群中的地位高低可以通过用户关系网来反映。 一个活跃用户或者核心用户在 用户关系网中往往存在某些较高的指标值，利用 PageRank 就可以发现这一点。PageRank 就 是这样一种指标，它是一种常用的网也排名算法。我们可以将用户视为 PageRank 中的网页， 而将用户之间的关系视为网络之间的链接关系，通过计算得到的用户 rank 值就可以判断用 户的活跃程度和核心程度，从而判断用户价值的高低。 为了更加充分地说明 X-RIME 的社会网络分析能力，我们用传统的基于统计学的方法和 X-RIME 的 PageRank 工具对水木 Military_View 版用户关系数据进行对比分析。 3.1.1 传统的基于统计学的方法 如图 8 所示，利用传统的统计分析方法，我们统计了 Military_View 版用户关系数据中 所有用户的出度，可以发现 “youngdragon”以及“yiangs”两个用户的用户度数并不是很高，没 有突出的特点，基于此来看，这两个用户算不上活跃用户以及核心用户。 图 8 军事观察版出度分布图 Fig.8 Out-degree Distribution of Military_View Board 3.1.2 X-RIME PageRank 算法 如图 9 所以， 通过利用 X-RIME 的 PageRank 分析工具，我们计算了所有用户的 PageRank 值，可以发现 “youngdragon”和“yiangs”两个的 PageRank 值是比较高的（前 20），说明这两 个用户在 Military_View 版的活跃度和核心度是挺高的。因此，利用 X-RIME 我们可以发现 普通基于统计学方法无法发现的深层信息。 图 9 军事观察版 PageRank 值分布图 Fig.9 PageRank Value Distribution of Military_View Board http://www.paper.edu.cn - 8 - 中国科技论文在线 3.2 客户社群发现 4.1 主要考虑了单个客户的价值，一个社交网络中往往还存在社群性结构。在一个社交 网络中，一个活跃的社群结构往往具有非常重要的价值。例如，一则消息如果发布给一个活 跃的社群，那么这则消息就更容易被扩散传播给其他用户。 K-核代表的是用户群中凝聚力相对较强的结构。利用 K-核算法我们可以寻找社会网络 中活跃的社群结构。 如图 10 所示，我们利用 X-RIME 的 K-核算法工具我们分别对水木清华的 Circuit 版和 Career_Post 版进行计算，发现 Circuit 版即使到了 16 核，也有着较为密集的用户，可以反映 出 Circuit 版具有凝聚力较强的群体结构； 相比之下 Career_Post 版刚到 7-核用户数就非常低， 反映出该版群体结构凝聚力不强。 图 10 Circuit 版的 16-核以及 Career_Post 版的 7-核 Fig.10 16-core of Circuit Board and 7-core of Career_Post Board 4 总结 随着互联网的快速发展，社会网络及社会网络分析相关理论逐渐得到完善。传统的基于 统计学的分析方法往往只是粗浅地进行分析， 而一般的社会网络分析工具遇到大规模的社会 网络数据集也无能为力。 X-RIME 是开源的社会网络分析工具包，它基于 HADOOP，在 HADOOP HDFS 与 Map/Reduce 基础上提供了互联网级 社会网络分析能力。通过本文的介绍可以看出 X-RIME 具有传统基于统计学的方法以及普通社会网络分析工具不具备的优势和能力， 具有较强的可 扩展性与通用性。我们还分析了适合用 MapReduce 实现的算法所应具有的主要特征。 下一步的主要工作有：对已有的算法工具库进行改进，以进一步提高其效率；进一步研 究 X-RIME 可以应用实际应用的场景。 [参考文献] (References) [1] Brunelli, M, Fedrizzi, M. A Fuzzy Approach to Social Network Analysis. Social Network Analysis and Mining, 2009. ASONAM '09. International Conference on Advances in. [2] X-RIME home page: Available from: http://xrime.sourceforge.net/ [3] D Borthakur. The Hadoop Distributed File System: Architecture and Design. Hadoop Project Website, 2007 - hadoop.apache.org. [4] J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Proceedings of OSDI’04: 6th Symposium on Operating System Design and Implemention, San Francisco, CA, Dec. 2004. [5] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, etc. Bigtable: A distributed storage system for structured data. Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI’06) (2006). [6] The Apache Software Foundation. Hadoop 0.20.2 API. Hadoop Project Website, 2007 - hadoop.apache.org. [7] WebHarvest home page. Available from: http://web-harvest.sourceforge.net/index.php [8] Vladimir Batagelj and Andrej Mrvar. Pajek Program for Analysis and Visualization of Large Networks Reference Manual List of commands with short explanation version 1.24. Available from: http://vlado.fmf.uni-lj.si/pub/networks/pajek/ [9] John Scott. Social Network Analysisz: A Handbook, 2nd edition, Sage Publications, Inc. 2000 http://www.paper.edu.cn - 9 - 中国科技论文在线 [10] Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web [11] Kleinberg J. Authoritative sources in a hyperlinked environment. In: Tarjan RE, Baecker T, eds. Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. New Orleans: ACM Press, 1997. 668~677. [12] RG Gallager, PA Humblet, PM Spira. A Distributed Algorithm for Minimum-Weight Spanning Trees. ACM Transactions on Programming Languages and Systems (TOPLAS) archive Volume 5, Issue 1 (January 1983) [13] Radicchi F, Castellano C, Cecconi F, Loreto V and Parisi D. Defining and identifying communities in networks. Proc. Natl Acad. Sci. USA