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.