李彤

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

1 問題的提出

隨著社交網(wǎng)絡(luò)工具的流行，例如我們熟悉的微博、知乎、微信和推特等，用戶在使用這些工具的過程中會(huì)產(chǎn)生大量的行為日志，這些日志記錄著用戶與用戶之間的關(guān)系，通過挖掘用戶之間的關(guān)系得出的結(jié)論可以應(yīng)用于很多的領(lǐng)域。但是，科研人員雖然可以獲得這些海量的信息，但最重要的是需要對(duì)這些海量數(shù)據(jù)處理和分析。例如，當(dāng)我們?cè)趩螜C(jī)環(huán)境中處理這些數(shù)據(jù)時(shí)，首先受到限制的是存儲(chǔ)空間，其次是計(jì)算能力。因此，需要使用支持水平擴(kuò)展的分布式計(jì)算框架來處理該類問題。

目前處理社交網(wǎng)絡(luò)關(guān)系通常需要分析出入度、連通性、聚合系數(shù)等。出入度需要統(tǒng)計(jì)每個(gè)頂點(diǎn)的出度和入度信息；連通性是圖的基本屬性，對(duì)于連通圖中的任意兩個(gè)頂點(diǎn)，都有一條路徑通向彼此；聚合系數(shù)指的是對(duì)每個(gè)點(diǎn)的三角計(jì)數(shù)，Watts和Strogatz定義了一個(gè)新的指標(biāo)，稱為局部聚類系數(shù)，它是一個(gè)頂點(diǎn)的真實(shí)三角計(jì)數(shù)的個(gè)數(shù)與這個(gè)頂點(diǎn)所有鄰接點(diǎn)可能構(gòu)成的三角計(jì)數(shù)的比值。在無向圖中，若有k個(gè)鄰接點(diǎn)和t個(gè)三角計(jì)數(shù)的頂點(diǎn)，其局部聚類系數(shù)C為:

首先我們先對(duì)Spark分布式計(jì)算框架進(jìn)行介紹，Spark是一個(gè)分布式的，彈性的計(jì)算框架。我們主要是用的是GraphX來完成社交網(wǎng)絡(luò)的分析，圖1展示了Spark存儲(chǔ)圖數(shù)據(jù)的原理圖：

圖1 Spark存儲(chǔ)圖數(shù)據(jù)的原理圖

Spark將網(wǎng)絡(luò)信息存儲(chǔ)成了頂點(diǎn)表和邊表，頂點(diǎn)表中記錄了每個(gè)頂點(diǎn)的唯一頂點(diǎn)ID以及頂點(diǎn)屬性，邊表中記錄了每條邊的起始和截止頂點(diǎn)，以及每條邊的屬性。這種存儲(chǔ)方式將圖按照頂點(diǎn)進(jìn)行切割，解決了海量社交網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ)問題，網(wǎng)絡(luò)按照頂點(diǎn)分隔之后，分割成的頂點(diǎn)表和邊表同樣可以分布式存儲(chǔ)，隨著數(shù)據(jù)的增長，通過擴(kuò)充網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)就可加快網(wǎng)絡(luò)計(jì)算的速度。

2 算法實(shí)現(xiàn)

算法（1）構(gòu)建社交網(wǎng)絡(luò)

輸入：輸入每個(gè)頂點(diǎn)的信息，以及頂點(diǎn)之間的信息傳播信息

輸出：構(gòu)建的社交網(wǎng)絡(luò)

算法（2）構(gòu)建有序的連通分量

輸入：構(gòu)建的社交網(wǎng)絡(luò)

輸出：該網(wǎng)絡(luò)中有序的連通分量

算法（3）計(jì)算網(wǎng)絡(luò)的平均聚合系數(shù)

輸入：構(gòu)建的社交網(wǎng)絡(luò)

輸出：該網(wǎng)絡(luò)的平均聚合系數(shù)

算法（4）計(jì)算網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)的最短路徑的迭代算法

輸入：構(gòu)建的社交網(wǎng)絡(luò)

輸出：網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)的最短路徑迭代過程：

（1）確認(rèn)每個(gè)節(jié)點(diǎn)需要存儲(chǔ)的數(shù)據(jù)

（2）編寫函數(shù)1,每個(gè)節(jié)點(diǎn)根據(jù)當(dāng)前記錄的數(shù)據(jù)，將節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)發(fā)給鄰居節(jié)點(diǎn)

（3）編寫函數(shù)2，每個(gè)節(jié)點(diǎn)匯總來自不同的相鄰節(jié)點(diǎn)的數(shù)據(jù)，更新存儲(chǔ)到每個(gè)節(jié)點(diǎn)自身的數(shù)據(jù)

函數(shù)1:將信息發(fā)送給鄰居節(jié)點(diǎn)

函數(shù)2：匯總鄰居節(jié)點(diǎn)數(shù)據(jù)

3 統(tǒng)計(jì)結(jié)果展示

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

可以看到，通過對(duì)vertices變量和topic Graph變量操作，可以快速的對(duì)網(wǎng)絡(luò)中的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)進(jìn)行統(tǒng)計(jì)。因?yàn)轫旤c(diǎn)數(shù)據(jù)和邊的數(shù)據(jù)是分開存儲(chǔ)的，并且相似的數(shù)據(jù)類型會(huì)存儲(chǔ)在一起，若將頂點(diǎn)數(shù)據(jù)和邊的數(shù)據(jù)存儲(chǔ)在一起，就很難達(dá)到較快與較靈活的統(tǒng)計(jì)速度。

（2）查看連通分量并查看最大的8個(gè)連通分量的信息：

圖中結(jié)果展示，通過sorted Connected Components對(duì)算法1構(gòu)建的圖進(jìn)行計(jì)算，可以獲得所有的連通分量，連通分量的個(gè)數(shù)，以及所有連通分量中所存在的點(diǎn)的個(gè)數(shù)，并且可以統(tǒng)計(jì)得到網(wǎng)絡(luò)中最大的n個(gè)連通分量。

（3）獲取社交網(wǎng)絡(luò)中所有頂點(diǎn)的聚合系數(shù)的平均值：

首先我們計(jì)算圖中每個(gè)點(diǎn)的聚合系數(shù)總和，然后除以網(wǎng)絡(luò)中頂點(diǎn)的個(gè)數(shù)，就可以快速的獲得整個(gè)網(wǎng)絡(luò)中的平均聚合系數(shù)。

（4）計(jì)算社交網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的最短距離：

我們通過Pregel函數(shù)迭代計(jì)算出了每個(gè)節(jié)點(diǎn)的最短路徑，并且統(tǒng)計(jì)了網(wǎng)絡(luò)中節(jié)點(diǎn)之間最短跳數(shù)的分布，可以快速并且十分簡潔地求出網(wǎng)絡(luò)中最短路徑的統(tǒng)計(jì)信息，了解網(wǎng)絡(luò)的屬性?；谧疃搪窂叫畔?，也可以進(jìn)一步對(duì)圖進(jìn)行小世界網(wǎng)絡(luò)特性分析。

4 結(jié)語

本文首先基于Spark對(duì)社交網(wǎng)絡(luò)進(jìn)行構(gòu)建，可以獲得網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)和邊的個(gè)數(shù)。接下來，基于分布式操作算子對(duì)連通分量進(jìn)行計(jì)算，并且給出有序的連通分量，在此基礎(chǔ)上對(duì)每個(gè)節(jié)點(diǎn)的三角計(jì)數(shù)進(jìn)行統(tǒng)計(jì)，然后分析了整個(gè)網(wǎng)絡(luò)的聚合系數(shù)以及最短路徑分布。本文編寫了高效的Spark代碼，對(duì)實(shí)際分析中常用的統(tǒng)計(jì)處理信息進(jìn)行了計(jì)算，具有一定的實(shí)際意義。

參考文獻(xiàn)：

[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.