基于Spark图计算的社会网络分析系统

社会网络分析系统"/>

基于Spark图计算的社会网络分析系统

资源下载地址：
资源下载地址：

1系统相关技术

1.1通用并行框架 Spark

Spark 是由加州大学伯克利分校 AMP 实验室所开源的类 Hadoop MapReduce 的通用并行框架，Spark 拥有 Hadoop MapReduce 所具有的优点；但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中，从而不再需要读写 HDFS， 因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的MapReduce 的算法。

Spark 是一种与 Hadoop 相似的开源集群计算环境，但是两者之间还存在一些不同之处，这些有用的不同之处使 Spark 在某些工作负载方面表现得更加优越，换句话说，Spark 启用了内存分布数据集，除了能够提供交互式查询外，它还可以优化迭代工作负载。

Spark 是在 Scala 语言中实现的，它将 Scala 用作其应用程序框架。与Hadoop 不同，Spark 和 Scala 能够紧密集成，其中的 Scala 可以像操作本地集合对象一样轻松地操作分布式数据集。

尽管创建 Spark 是为了支持分布式数据集上的迭代作业，但是实际上它是对 Hadoop 的补充，可以在 Hadoop 文件系统中并行运行，通过名为 Mesos 的第三方集群框架可以支持此行为。

RDD（Resilient Distributed Datasets），弹性分布式数据集，是分布式内存的一个抽象概念，RDD 提供了一种高度受限的共享内存模型，即 RDD 是只读的记录分区的集合，只能通过对其他 RDD 执行确定的转换操作（如 map、join 和 group by）而创建，然而这些限制使得实现容错的开销很低。对开发者而言，RDD 可以看作是 Spark 的一个对象，它本身运行于内存中，如读文件是一个 RDD，对文件计算是一个 RDD，结果集也是一个 RDD ，不同的分片、数据之间的依赖、key-value 类型的 map 数据都可以看做 RDD。

1.2图计算框架 GraphX

Spark GraphX 是一个分布式图处理框架，Spark GraphX 基于 Spark 平台提供对图计算和图挖掘简洁易用的而丰富多彩的接口，极大的方便了大家对分布式图处理的需求。

众所周知，社交网络中人与人之间有很多关系链，例如 Twitter、Facebook、微博和微信等，这些都是大数据产生的地方都需要图计算，现在的图处理基本都是分布式的图处理，而并非单机处理。Spark GraphX 由于底层是基于 Spark 来处理的，所以天然就是一个分布式的图处理系统。

图的分布式或者并行处理其实是把图拆分成很多的子图，然后分别对这些子图进行计算，计算的时候可以分别迭代进行分阶段的计算，即对图进行并行计算。

1.3动态图形组件 GraphStream

GraphStream 是一个 Java 类库，用于管理动态图形。它由一个面向对象的 API 组成，能够以简便、快速的方式在一张图形中添加边缘和节点，并让它们进行演变[15]。

1.4函数式编程语言 Scala

Scala 是一门多范式的编程语言，一种类似 java 的编程语言，设计初衷是实现可伸缩的语言，并集成命令式编程、面向对象编程和函数式编程的各种特性。Scala 有几项关键特性表明了它的面向对象的本质。例如，Scala 中的每个值都是一个对象，包括基本数据类型（即布尔值、数字等）在内，连函数也是对象。另外，类可以被子类化，而且 Scala 还提供了基于 mixin 的组合（mixin-based com position）。

与只支持单继承的语言相比，Scala 具有更广泛意义上的类重用。Scala 允许定义新类的时候重用“一个类中新增的成员定义（即相较于其父类的差异之处）”， Scala 称之为 mixin 类组合。

Scala 还包含了若干函数式语言的关键概念，包括高阶函数（Higher-Order Function）、局部套用（Currying）、嵌套函数（Nested Function）、序列解读（Se quence Comprehensions）等等。

Scala 是静态类型的，这就允许它提供泛型类、内部类、甚至多态方法（Po lymorphic Method）。另外值得一提的是，Scala 被特意设计成能够与 Java 和.NE T 互操作。Scala 当前版本还不能在.NET 上运行，但按照计划将来可以在.NET 上运行。

Scala 可以与 Java 互操作。它用 scalac 这个编译器把源文件编译成 Java 的 cl ass 文件（即在 JVM 上运行的字节码）。你可以从 Scala 中调用所有的 Java 类库， 也同样可以从 Java 应用程序中调用 Scala 的代码。用 David Rupp 的话来说，它也可以访问现存的数之不尽的 Java 类库，这让 Java 类库迁移到 Scala 变得更加容易。

2系统功能性需求分析

前两章中，介绍了系统的背景，并介绍了开发中使用的关键技术。本章将描述系统的需求，基于这些需求，系统设计和实现才得以开展。

2.1系统功能模块

系统功能模块如图 3- 1 所示，整个系统分为三大功能块，分别是：图构建模块，可视化模块和顶点分析模块。在顶点分析模块中，用户可以进行顶点重要程度分析、顶点分组（聚类）、顶点邻居计算、顶点到顶点路径计算等多角度的分析。

2.2系统用例描述

图构建的用例描述如下表所示：

表 3-1 构建图用例描述

图计算对象可视化的用例描述如下表所示：

表 3-2 图计算对象可视化用例描述

图的可视化对象局部标记的用例描述如下表所示：

表 3-3 图的可视化对象局部标记用例描述

表 3-4 顶点重要程度分析用例描述

顶点分组的用例描述如下表所示：

表 3-5 顶点分组用例描述

表 3-6 顶点 n 层邻居计算用例描述

表 3-7 顶点到顶点路径计算用例描述

2.3本章小结

本章主要是系统的需求分析，通过系统功能总图和用例描述相结合的形式， 介绍项目的图构建模块、可视化模块、顶点分析模块的功能需求。

3系统概要设计

论文在第二章中介绍了系统的架构设计，在第三章中详细介绍了系统的功能需求，本章将介绍系统关键的类结构和主要的功能函数。

3.1系统架构

首先，由于现实的数据往往不是直接以图形式呈现的，需要进行数据的清洗、提取，并转换为能为 GraphX 图计算引擎操作的数据，因此有必要在大规模图数据挖掘平台中包含非图数据的计算处理能力；其次，一个平台能够完成对图数据和非图数据的挖掘任务，有助于节约集群资源，简化平台管理；最后，采用两种并行计算框架分别完成图数据计算和非图数据计算需要开发人员了解两种程序的设计模式，影响系统的二次开发能力。 因此，本文提出采用 Spark 并行计算框架作为系统的非图数据处理引擎，采用 Spark 的图计算接口 GraphX 作为系统的图数据计算引擎，解决上述问题。系统的架构如图 4-1 所示：

图 3-1 系统架构图

本文系统整体架构包含：提供数据导入、预处理的 Spark 平台层，提供图计算接口的图计算引擎层，提供个性化图数据分析能力的算子层，提供分析结果图形化展示的可视化层。

系统的一个重要可拓展性在于用户可以根据自己的新需求往算子层添加自定义的算子来满足自己的分析需求。

3.2类设计

整个系统的分析和演示分别基于图计算对象 Graph 和可视化图对象GraphStream 两个类，Graph 类由图计算框架 GraphX 提供，类 GraphStream 是动态图形组件 GraphStream 自带的可视化图对象类。

本文在第三方框架的基础上，合理应用各种设计模式[16]来设计系统，减轻各子系统之间的耦合，便于系统未来的扩展和维护。

3.2.1算子子系统

对于算子层，本文使用“外观模式”进行设计，将算子层和图构建层、可视化层相分离，如图 4-2 所示。本文为算子子系统开发一个外观 Analysis 类，对外提供一个简单的接口，减轻各层之间的耦合。Analysis 中的 analysis 方法可以对不同的算子进行组合，来满足特定的分析要求。

图 3-3 可视化对象构建子系统

3.2.2可视化对象构建

对一张图进行可视化时往往需要对它的各种属性标签（顶点名称、顶点 ID、边的名称等）进行组合显示，本文使用“建造者模式”将可视化图对象 GraphStream 的构建和表示分离，使得同样的构建步骤可以创建不同的表示，如图 4-3。类Director 作为子系统对外的交互接口， 用户只需指定具体的建造器， 如CD_GSBuilder 就可以得到相应的可视化对象，而具体的建造过程和细节无需知道。

图 3-3 可视化对象构建子系统

5 系统测试

本章对系统进行功能性测试，先对基础的图构建功能给出测试，再对四个主要分析模块的分析结果在控制台进行输出，并给出可视化的展示。

5.1测试数据

本文采用的测试数据集是“智器云”（一款大数据可视化分析软件，http://w ww.zqykj/）提供的社会关系网络样例数据。测试数据集包含顶点 69 个，边 84 条。

5.2测试环境

系统测试是在个人笔记本电脑上进行的，系统的测试环境情况如表 5-1 所示。

表格 5-1 系统测试环境说明

参数	配置描述
CPU	2.2 GHz Intel Core i7，4 cores
L2 Cache (per Core)	256 KB
L3 Cache	6 MB
Memory	16 GB 1600 MHz DDR3
硬盘	220 GB
操作系统	OS X EI Captitan Version 10.11.3
集成开发环境	IntelliJ IDEA 15
Spark	Stand-alone Model

5.3 图构建和可视化测试

图 5-1 对图构建的可视化结果进行了展示，图中绿色圆点对应人物的实体， 人物旁边的文字标注对应人物的姓名，如 Wang Jie、Wang Feng，紫红色线段用于连接两个人物，表示两个人物有一定强度的联系。

图 5-1 带有人物姓名的图构建可视化结果

系统可以根据需要对顶点或边的属性进行定制化的显示，图 6-2，6-3 中不仅显示了人物的姓名，还分别显示了人物的 ID 和人物的关系。人物的关系有cousin（表亲关系）、partner（合作关系）、schoolmate（同学）等等。

图 5-2 带有人物姓名和 ID的图构建可视化结果

图 5-3 带有人物姓名和关系的图构建可视化结果

5.4分析模块测试

5.4.1顶点重要程度分析

本小节对顶点重要程度分析模块进行了测试，控制台输出结果如图6-4 所示。在每个人的姓名后跟“：”标注了他们的 PageRank 值，颜色越深、越接近红色，该顶点在图中的重要程度越高，反之颜色越浅、越接近于绿色，其重要程度越低。从图 6-5 中可以看出，“Ding Yifan”这个点的重要程度，明显高于其他点。

图 5-4 顶点 PageRank 值输出结果

图 5-5 顶点重要程度可视化结果

5.4.2顶点分组

图 5-6 显示了顶点分组测试的控制台输出结果，输出结果为两栏，左边一栏为顶点的 ID，右边一栏为使用标签传播算法分组后顶点的标签。

图 5-6 顶点分组控制台输出结果

图 5-7 为顶点分组测试的可视化测试结果，其中相同颜色的顶点表示在同一个分组。

图5 -7 顶点分组可视化结果

5.4.3顶点邻居计算

本文计算了人物 Liu Zhengying 的 2 层邻居组（2 层邻居组：节点的邻居和节点的邻居的邻居），如图 6-8 所示，被计算节点用蓝色圆圈标记，结算结果用加深的绿色标记显示。

图 5-8 节点邻居计算可视化结果

5.4.4顶点到顶点的简单路径

本小节对“顶点到顶点的简单路径”模块的功能进行了测试，图 6-9 显示了ID 为 78000000000008000 的点和 ID 为 96000000000009876 的点之间的所有简单路径，一共是 5 条。

图 5-9 两点间简单路径的输出结果

可视化测试结果如图 5-10 所示，其中用深绿色标记的点是所有简单路径上涉及的点。

图 5-10 简单路径可视化结果

资源下载地址：
资源下载地址：