Spark在社交网络数据处理中的应用研究

李彤

（四川大学计算机学院，成都610065）

1 问题的提出

随着社交网络工具的流行，例如我们熟悉的微博、知乎、微信和推特等，用户在使用这些工具的过程中会产生大量的行为日志，这些日志记录着用户与用户之间的关系，通过挖掘用户之间的关系得出的结论可以应用于很多的领域。但是，科研人员虽然可以获得这些海量的信息，但最重要的是需要对这些海量数据处理和分析。例如，当我们在单机环境中处理这些数据时，首先受到限制的是存储空间，其次是计算能力。因此，需要使用支持水平扩展的分布式计算框架来处理该类问题。

目前处理社交网络关系通常需要分析出入度、连通性、聚合系数等。出入度需要统计每个顶点的出度和入度信息；连通性是图的基本属性，对于连通图中的任意两个顶点，都有一条路径通向彼此；聚合系数指的是对每个点的三角计数，Watts和Strogatz定义了一个新的指标，称为局部聚类系数，它是一个顶点的真实三角计数的个数与这个顶点所有邻接点可能构成的三角计数的比值。在无向图中，若有k个邻接点和t个三角计数的顶点，其局部聚类系数C为:

首先我们先对Spark分布式计算框架进行介绍，Spark是一个分布式的，弹性的计算框架。我们主要是用的是GraphX来完成社交网络的分析，图1展示了Spark存储图数据的原理图：

图1 Spark存储图数据的原理图

Spark将网络信息存储成了顶点表和边表，顶点表中记录了每个顶点的唯一顶点ID以及顶点属性，边表中记录了每条边的起始和截止顶点，以及每条边的属性。这种存储方式将图按照顶点进行切割，解决了海量社交网络数据的存储问题，网络按照顶点分隔之后，分割成的顶点表和边表同样可以分布式存储，随着数据的增长，通过扩充网络节点个数就可加快网络计算的速度。

2 算法实现

算法（1）构建社交网络

输入：输入每个顶点的信息，以及顶点之间的信息传播信息

输出：构建的社交网络

算法（2）构建有序的连通分量

输入：构建的社交网络

输出：该网络中有序的连通分量

算法（3）计算网络的平均聚合系数

输入：构建的社交网络

输出：该网络的平均聚合系数

算法（4）计算网络中任意两个节点的最短路径的迭代算法

输入：构建的社交网络

输出：网络中任意两个节点的最短路径迭代过程：

（1）确认每个节点需要存储的数据

（2）编写函数1,每个节点根据当前记录的数据，将节点存储的数据发给邻居节点

（3）编写函数2，每个节点汇总来自不同的相邻节点的数据，更新存储到每个节点自身的数据

函数1:将信息发送给邻居节点

函数2：汇总邻居节点数据

3 统计结果展示

（1）图的基本信息展示:

可以看到，通过对vertices变量和topic Graph变量操作，可以快速的对网络中的顶点个数和边的个数进行统计。因为顶点数据和边的数据是分开存储的，并且相似的数据类型会存储在一起，若将顶点数据和边的数据存储在一起，就很难达到较快与较灵活的统计速度。

（2）查看连通分量并查看最大的8个连通分量的信息：

图中结果展示，通过sorted Connected Components对算法1构建的图进行计算，可以获得所有的连通分量，连通分量的个数，以及所有连通分量中所存在的点的个数，并且可以统计得到网络中最大的n个连通分量。

（3）获取社交网络中所有顶点的聚合系数的平均值：

首先我们计算图中每个点的聚合系数总和，然后除以网络中顶点的个数，就可以快速的获得整个网络中的平均聚合系数。

（4）计算社交网络中两个节点的最短距离：

我们通过Pregel函数迭代计算出了每个节点的最短路径，并且统计了网络中节点之间最短跳数的分布，可以快速并且十分简洁地求出网络中最短路径的统计信息，了解网络的属性。基于最短路径信息，也可以进一步对图进行小世界网络特性分析。

4 结语

本文首先基于Spark对社交网络进行构建，可以获得网络中的总节点数和边的个数。接下来，基于分布式操作算子对连通分量进行计算，并且给出有序的连通分量，在此基础上对每个节点的三角计数进行统计，然后分析了整个网络的聚合系数以及最短路径分布。本文编写了高效的Spark代码，对实际分析中常用的统计处理信息进行了计算，具有一定的实际意义。

参考文献：

[1]RezvaniM,LiangW,XuW,etal.Identifying Top-k,Structural Hole Spanners in Large-Scale Social Networks[C].ACM International on Conference on Information and Knowledge Management.ACM,2015:263-272.

[2]XuW,LiangW,Lin X,etal.Finding Top-k,Influential Users in Social Networks Under the Structural Diversity Model[J].Information Sciencesan International Journal,2016,355（C）:110-126.

[3]XuW,RezvaniM,LiangW,etal.Efficient Algorithms for the Identification of Top-k Structural Hole Spanners in Large Social Networks[J].IEEE Transactions on Knowledge&Data Engineering,2017,PP（99）:1-1.

[4]Zhang Y,BaiY,Chen L,etal.Influence Maximization in Messenger-Based Social Networks[C].Global Communications Conference.IEEE,2017:1-6.

[5]DiestelR.Graph theory[M].Springer-Verlag,2000.

[6]Watts,Duncan J,Strogatz,etal.Collective Dynamics of'S mall World'Networks[M].The Structure and Dynamics of Networks.2006:301-303.

[7]ZahariaM.An Architecture for Fastand General Data Processing on Large Clusters[M].Association for Computing Machinery and Morgan&Claypool,2016.