基于在線社交網(wǎng)絡(luò)的JPS跳躍并行頂點(diǎn)采樣方法

趙倩文

(浙江理工大學(xué)信息學(xué)院，浙江 杭州 310018)

0 引 言

在線社交網(wǎng)絡(luò)(Online Social Networks， OSNs)從早期的概念化階段慢慢地發(fā)展到交友和娛樂，整個(gè)發(fā)展過(guò)程中最重要的是將人們線下生活移至線上并且拉近了人們的距離,這使得虛擬的社交網(wǎng)絡(luò)與現(xiàn)實(shí)的社交出現(xiàn)了很多的交集，成為一個(gè)社交的工具。

隨著近幾年OSNs的飛速發(fā)展，其受到全球各年齡階層人們的歡迎。社交網(wǎng)絡(luò)用戶總數(shù)已達(dá)到三十多億，占全球總?cè)丝诘乃某?，?shù)量極其龐大且持續(xù)地增長(zhǎng)。OSNs的迅速發(fā)展也吸引了大量的研究人員去探究其背后的大數(shù)據(jù)隱藏的信息，研究課題也是多種多樣[1]。

因?yàn)镺SNs的數(shù)據(jù)龐大[2]，想要完整地分析需消耗大量的時(shí)間，同時(shí)有些數(shù)據(jù)集比較稀疏，尚且不能完整地處理[3]。研究人員在分析這些數(shù)據(jù)時(shí)遇到的挑戰(zhàn)之一就是如何采集具有代表性的樣本數(shù)據(jù)。所以需要設(shè)計(jì)一個(gè)有效的采樣方法，采集一個(gè)屬性接近原始數(shù)據(jù)集的小型代表性無(wú)偏見的樣本,以供研究人員分析[4]。

研究OSNs的數(shù)據(jù)集時(shí)，將其看作一個(gè)擁有頂點(diǎn)和連接邊的圖來(lái)分析。將用戶看作頂點(diǎn)，把用戶之間的關(guān)系當(dāng)作連接邊，建模成一個(gè)社交圖[5]。目前為止已經(jīng)出現(xiàn)了多種頂點(diǎn)采樣方法，可以用于OSNs數(shù)據(jù)樣本的采集。寬度優(yōu)先采樣(Breadth-First Search， BFS)是一種比較常用的采樣方法，但BFS的采樣偏向于高度頂點(diǎn)，隨機(jī)游走(Random Walk， RW)[11-12]不適用于斷開的圖并且偏向于高度頂點(diǎn)，蒙特卡羅隨機(jī)游走(Metropolis-Hasting Random Walk， MHRW)和無(wú)偏延遲采樣(Unbiased Delay， UD[4])方法依然不適合采樣斷開連接或松散連接的圖[5]，信天翁(Albatross Sampling， AS)采樣花費(fèi)成本很大[14]。

1 蒙特卡羅隨機(jī)游走

早期的很多文獻(xiàn)都涉及在線社交網(wǎng)絡(luò)的樣本采集方法的研究[6]，也提出了很多有用的采樣方法，但現(xiàn)有采樣方法各有利弊。其中寬度優(yōu)先采樣是比較常用的，但是采樣獲取的樣本偏向于高度頂點(diǎn)，并不能代表原始數(shù)據(jù)集[7]；而RW、MHRW、UD方法將節(jié)點(diǎn)選擇問(wèn)題公式化[8],卻不適應(yīng)于低連通社交圖的采樣。

MHRW采樣方法就是基于RW方法提出的，一定程度上消除了樣本頂點(diǎn)的偏差。當(dāng)社交網(wǎng)絡(luò)頂點(diǎn)連接良好時(shí)，MHRW方法可以很好地獲得社交圖的無(wú)偏樣本。實(shí)現(xiàn)原理是根據(jù)給定的任意一個(gè)概率分布，構(gòu)造一個(gè)以該分布為靜態(tài)分布的馬爾科夫鏈[3]，然后執(zhí)行該馬爾科夫鏈，達(dá)到收斂之后開始采樣。MHRW方法與RW方法相同的是,下一樣本頂點(diǎn)依然從當(dāng)前頂點(diǎn)的鄰居頂點(diǎn)中選擇，不同的是,選擇下一樣本頂點(diǎn)時(shí)不是等概率的。MHRW采樣過(guò)程中從v到w的轉(zhuǎn)移概率表示為：

(1)

其中,v和w表示頂點(diǎn)，P表示從v轉(zhuǎn)移到w的概率，kv和kw分別是頂點(diǎn)v和w的度數(shù)。從轉(zhuǎn)移概率可以看出,MHRW采樣過(guò)程中每個(gè)頂點(diǎn)的選擇更傾向于低度頂點(diǎn)，這樣就可能使低度頂點(diǎn)的自循環(huán)升高，陷入局部連通良好的區(qū)域，導(dǎo)致低度頂點(diǎn)過(guò)入樣[13]。另一個(gè)不足之處在于該方法依然不能適用于低連通社交圖的采樣，因?yàn)镸HRW方法獲得的頂點(diǎn)僅在某一個(gè)連通子圖中。

2 跳躍無(wú)偏并行頂點(diǎn)采樣方法

2.1 采樣方法基本思想

本文將在線社交網(wǎng)絡(luò)建模為一個(gè)由用戶頂點(diǎn)集合V和用戶之間連接邊集合E構(gòu)成的社交圖，表示為G=(V,E)，其中E集合的每條邊都是未加權(quán)的[9]。而在線社交圖分為無(wú)向圖和有向圖，對(duì)于無(wú)向圖頂點(diǎn)的度數(shù)是連接的鄰居頂點(diǎn)數(shù)，但是在采樣有向圖時(shí)需要給頂點(diǎn)的每條邊添加一個(gè)標(biāo)志著進(jìn)出方向的屬性將其轉(zhuǎn)化為無(wú)向圖再進(jìn)行采樣，針對(duì)指向頂點(diǎn)的邊設(shè)為入度，指出的邊設(shè)為出度。

下面基于MHRW采樣方法，針對(duì)其較高的自循環(huán)率和不能適用低連通強(qiáng)度社交圖的缺陷做出改進(jìn)。首先提出一個(gè)雙保險(xiǎn)的跳躍策略以便提高采樣時(shí)對(duì)全局頂點(diǎn)的公平性，且對(duì)于不同連通強(qiáng)度的社交圖都是可以避免困于局部連接良好的區(qū)域，同時(shí)降低了頂點(diǎn)的自循環(huán)概率；其次添加一個(gè)頂點(diǎn)緩存區(qū)，采樣過(guò)程中以一定概率在此處隨機(jī)選擇與當(dāng)前頂點(diǎn)度數(shù)相同的頂點(diǎn)作為下一頂點(diǎn)，可以降低全局跳躍的成本；最后多路并行采樣加快了樣本采集的效率，盡可能在最短時(shí)間采集一定數(shù)量的頂點(diǎn)。

頂點(diǎn)緩存區(qū)D是一個(gè)初始為空的區(qū)域，隨著采樣的進(jìn)行把采集到的頂點(diǎn)的所有鄰居頂點(diǎn)按照頂點(diǎn)度數(shù)排序后添加進(jìn)去，形成一個(gè)獨(dú)立的區(qū)域。并行意味著采樣不是一條主線進(jìn)行到底的，而是多路并行采樣互不干擾。

跳躍無(wú)偏并行頂點(diǎn)(Jump unbiased Parallel vertex Sampling， JPS)采樣方法引入了2個(gè)跳躍參數(shù)α與β，其中α控制著采樣過(guò)程中從頂點(diǎn)緩存區(qū)內(nèi)隨機(jī)選取與當(dāng)前頂點(diǎn)相同度數(shù)的下一頂點(diǎn)的概率，而β控制著采樣過(guò)程中從全局頂點(diǎn)V中隨機(jī)選取下一頂點(diǎn)的概率。

由于D中頂點(diǎn)是隨著采樣的進(jìn)行逐漸添加的，可知采樣的前期D并沒有足夠的頂點(diǎn)數(shù)量，要保持一個(gè)較大的β值提高算法在初期的全局搜索能力,以致加快了算法的后期收斂速度[15]，從而采集到全局中其他頂點(diǎn)且能盡快增加頂點(diǎn)緩存區(qū)頂點(diǎn)數(shù)量，而在采樣中后期D中頂點(diǎn)足夠支撐采樣的跳轉(zhuǎn)時(shí)可以設(shè)置較小的β值降低跳轉(zhuǎn)成本，因此可得：

(2)

其中,s表示采樣過(guò)程中采集的頂點(diǎn)數(shù)，S表示需要的樣本總數(shù)量。設(shè)置2個(gè)不同區(qū)域跳躍參數(shù)α與β的優(yōu)點(diǎn)在于降低了受困于局部連接良好的區(qū)域的可能性，以便采集到性能更接近原始連通圖的小型代表性樣本。

α定義為靜態(tài)值，規(guī)定了頂點(diǎn)在緩存區(qū)中的跳躍概率，在Twitter數(shù)據(jù)集中進(jìn)行5次采樣繪制不同α值的樣本頂點(diǎn)平均度分布圖如圖1所示。

圖1中橫坐標(biāo)為α的值，縱坐標(biāo)為樣本平均度，黑色線Ori為原始Twitter社交圖的平均度。圖1(a)為(0，1)范圍內(nèi)α的取值對(duì)采集的樣本平均度的影響，可看出最優(yōu)的α值在(0，0.2)之間，圖1(b)為(0，0.2)范圍內(nèi)α的取值對(duì)采集的樣本平均度的影響，由于圖1(b)中5次采集的樣本平均度與原始網(wǎng)絡(luò)平均度差距較小，但α在(0.1,0.2)范圍內(nèi)時(shí)采樣平均度高于原始平均度，所有從(0.05,0.1)選取的α值均可，本文以α=0.08進(jìn)行采樣。

(a) α在(0,1)范圍內(nèi)取值

(b) α在(0，0.2)范圍內(nèi)取值

2.2 JPS采樣工作流程

上面確定了跳躍機(jī)制中頂點(diǎn)緩存區(qū)D中的跳躍概率α=0.08，全局跳躍概率，下面是JPS采樣方法的代碼實(shí)現(xiàn)過(guò)程。

算法1JPS Sampling

1 Input: GraphG=(V,E)

2 Select 10 random vertexvfrom theVas the initial node

3 Addvto thes

4 Node jump area dictD←empty

5 While stopping criterion not met Do

6 Foriin neighbors ofv

7 Addito theD

8 While stopping criterion not met Do

9 Forvins(-11:-1)

10 Select nodewuniformly at random from neighbors ofv

11 Generatep1,p2,p3from uniform distributionU(0,1)

13 Addwto thes,v←w

14 elifp2<βthen

15 Selectarandom vertexufrom theV

16 Adduto thes,v←u

18 Stay atv

19 else

20 Selectdfrom dictD, whilekv=kd

21 Adddto thes,v←d

22 end if

23 end while

24 end while

25 Output: The set of sample verticess

2.3 JPS采樣的無(wú)偏見性

JPS采樣方法中下一樣本頂點(diǎn)w的選擇取決于當(dāng)前頂點(diǎn)v。w可能是v的鄰居，可能是與v相同度數(shù)的頂點(diǎn)，還可能是從全局社交圖中隨機(jī)選擇的頂點(diǎn)。因此JPS方法采樣過(guò)程可以建模為馬爾可夫鏈，并且從當(dāng)前頂點(diǎn)v到下一頂點(diǎn)w的概率是：

(3)

其中，v和w表示頂點(diǎn)，P表示從v轉(zhuǎn)移到w的概率，kv和kw分別是頂點(diǎn)v和w的度數(shù),而α是頂點(diǎn)緩存區(qū)D中的選擇概率,取值為0.08,β為全局社交圖中頂點(diǎn)的選擇概率。

2.4 JPS采樣的度分布

公式(3)完整地概括了JPS采樣方法的實(shí)現(xiàn)原理，因?yàn)镴PS采樣方法是基于MHRW方法提出的，所以也可以構(gòu)造一個(gè)靜態(tài)分布的Markov Chain鏈?zhǔn)蛊淠軌蜻M(jìn)行無(wú)偏采樣。雙重跳躍降低了頂點(diǎn)的自循環(huán)概率，增加了全局頂點(diǎn)的入樣概率，改善了現(xiàn)有采樣方法無(wú)法適用于連通性低的網(wǎng)絡(luò)。網(wǎng)絡(luò)度分布是評(píng)估網(wǎng)絡(luò)中不同度數(shù)頂點(diǎn)數(shù)量的一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)，能夠直觀地展示在線社交網(wǎng)絡(luò)中頂點(diǎn)的度數(shù)分布情況。下面針對(duì)Twitter數(shù)據(jù)集采樣評(píng)估JPS采樣方法采集的樣本度分布圖，如圖2所示。

圖2 Twitter中各采樣方法的度分布

從圖2可以看出，JPS采樣方法獲取的樣本頂點(diǎn)平均度基本與原始Twitter數(shù)據(jù)集的網(wǎng)絡(luò)度分布一致。

3 評(píng)估實(shí)驗(yàn)

第2章解決的問(wèn)題是如何設(shè)計(jì)采樣算法才能更高效地從一個(gè)大規(guī)模的在線設(shè)計(jì)網(wǎng)絡(luò)數(shù)據(jù)集中獲取一個(gè)與原始數(shù)據(jù)集性能屬性相符的樣本數(shù)據(jù)頂點(diǎn)。本章根據(jù)網(wǎng)絡(luò)性能繪制頂點(diǎn)屬性分布圖，驗(yàn)證JPS采樣方法所采集樣本的各個(gè)屬性[3,5,7]都更加接近于原始社交網(wǎng)絡(luò)數(shù)據(jù)集，是符合要求的小型代表性樣本頂點(diǎn)網(wǎng)絡(luò)。一個(gè)數(shù)據(jù)集的屬性有很多，所以對(duì)其的評(píng)價(jià)標(biāo)準(zhǔn)也是多種多樣，在選擇評(píng)價(jià)標(biāo)準(zhǔn)時(shí)，并不是越多越好，所以不需要對(duì)所有屬性進(jìn)行比較，本文僅使用較為常用的一些網(wǎng)絡(luò)統(tǒng)計(jì)量。往年的研究表明，類似于網(wǎng)絡(luò)頂點(diǎn)平均度、度分布、同配性等網(wǎng)絡(luò)統(tǒng)計(jì)量[17-22]足夠代表大部分評(píng)價(jià)標(biāo)準(zhǔn)。本文主要使用網(wǎng)絡(luò)的平均度、頂點(diǎn)更新率、度分布P(k)以及收斂性對(duì)JPS采樣方法與現(xiàn)有的MHRW、BFS、AS、UD等采樣方法進(jìn)行評(píng)估。

為了更公平地評(píng)估各采樣方法獲取樣本的優(yōu)劣，評(píng)估時(shí)選擇了連通強(qiáng)度不同的Twitter和Epinions數(shù)據(jù)集，2個(gè)數(shù)據(jù)集的基本信息如表1所示。

表1 數(shù)據(jù)集的基本信息

表1中強(qiáng)連通分量表示有向圖中最大連接子圖的頂點(diǎn)數(shù)的值[23]。

3.1 樣本網(wǎng)絡(luò)的平均度

分別對(duì)Twitter和Epinions數(shù)據(jù)集進(jìn)行采樣，繪制樣本頂點(diǎn)的平均度分布圖如圖3所示。

圖3 樣本頂點(diǎn)平均度

圖3中，橫坐標(biāo)表示采集的樣本頂點(diǎn)數(shù)量，縱坐標(biāo)表示樣本平均度，使用黑色線Ori來(lái)表示原始數(shù)據(jù)集的平均度。從圖中可以看出不同的采樣方法分別應(yīng)用于Twitter和Epinions數(shù)據(jù)集時(shí)獲取的樣本頂點(diǎn)平均度變化情況。從圖3(a)和圖3(b)可以看出，樣本平均度最接近于原始數(shù)據(jù)集平均度的采樣方法為JPS，UD次之，AS與MHRW方法獲取的樣本平均度基本相同，BFS采集樣本的平均度浮動(dòng)較大、不夠穩(wěn)定，RW采集的樣本偏向于高度頂點(diǎn)。

3.2 頂點(diǎn)更新率

頂點(diǎn)更新率(Ps)是衡量采樣效率以及自循環(huán)的評(píng)價(jià)指標(biāo)，更新率越高說(shuō)明采樣過(guò)程中采集到重復(fù)頂點(diǎn)的概率越低，同時(shí)也表明JPS采樣方法更有效地跳出局部連通良好的區(qū)域并且降低了頂點(diǎn)的自循環(huán)概率。下面分別在Twitter和Epinions數(shù)據(jù)集中使用不同采樣方法，進(jìn)行樣本頂點(diǎn)更新率的比較，繪制分布圖如圖4所示。

圖4 樣本頂點(diǎn)更新率

圖4橫坐標(biāo)表示采樣頂點(diǎn)數(shù)量S，縱坐標(biāo)表示更新率Ps。從圖中可以看出，無(wú)論在Twitter還是Epinions中，更新率比較高的是JPS和RW采樣方法。但從圖4(b)可以明顯看出，RW采樣方法不穩(wěn)定，隨著需要的樣本數(shù)量S的增加，頂點(diǎn)更新率一直在降低。主要原因在于RW沒有跳躍機(jī)制，容易受困于連通良好的網(wǎng)絡(luò)子區(qū)域，當(dāng)采樣頂點(diǎn)數(shù)量增加時(shí)，就會(huì)過(guò)度采集重復(fù)頂點(diǎn)。綜上，JPS采樣方法相較于其他采樣方法來(lái)說(shuō)頂點(diǎn)更新率更高且更加穩(wěn)定。

3.3 網(wǎng)絡(luò)的度分布

圖2展示了JPS采樣方法應(yīng)用于高連通的Twitter數(shù)據(jù)集中采集的樣本度分布，而在低連通的Epinions數(shù)據(jù)集上進(jìn)行采樣，采集的樣本度分布圖如圖5所示。

圖5 Epinions中各采樣方法的度分布

從圖5可以看出，JPS采集的樣本度分布依然近乎與Epinions原始數(shù)據(jù)網(wǎng)絡(luò)度分布相同。由此可知，無(wú)論是高連通的Twitter還是低連通的Epinions的數(shù)據(jù)集中，JPS采樣方法與原始網(wǎng)絡(luò)的度分布都很接近，能很好地適用于不同連通強(qiáng)度的網(wǎng)絡(luò)。

3.4 采樣方法的收斂性

為了更公平地評(píng)估各種采樣方法的性能，在Twitter數(shù)據(jù)集下使用MCMC診斷測(cè)試中廣泛使用的Geweke診斷方法，繪制了MHRW、UD、AS和JPS采樣方法的收斂曲線，如圖6～圖9所示。

圖6 MHRW采樣方法的收斂性

圖7 UD采樣方法的收斂性

圖8 AS采樣方法的收斂性

圖9 JPS采樣方法的收斂性

圖6～圖9中，橫坐標(biāo)表示采樣的頂點(diǎn)數(shù)量，縱坐標(biāo)表示收斂值，曲線的條數(shù)表示采樣次數(shù)。可以看出，JPS方法的收斂性明顯優(yōu)于MHRW與UD采樣方法，相較于AS方法也有部分改進(jìn)。主要是由于在采樣過(guò)程中引入了雙重跳躍，因此確保了在采樣過(guò)程中可以及時(shí)跳出連接良好的子區(qū)域和頂點(diǎn)的自循環(huán)。

結(jié)合以上對(duì)比實(shí)驗(yàn)可以看出，JPS采樣方法的性能優(yōu)于其他采樣方法，是一種有效的社交圖采樣方法。

4 結(jié)束語(yǔ)

本文基于MHRW采樣方法提出了改進(jìn)的頂點(diǎn)采樣算法JPS，它將雙重跳躍機(jī)制、頂點(diǎn)緩存區(qū)以及多路并行應(yīng)用到MHRW中。根據(jù)第3章的性能評(píng)估，JPS獲取的樣本網(wǎng)絡(luò)度分布和樣本頂點(diǎn)平均度更接近原始網(wǎng)絡(luò)數(shù)據(jù)集，雙重跳躍機(jī)制增強(qiáng)了檢測(cè)整個(gè)網(wǎng)絡(luò)的能力，適用于不同連接強(qiáng)度的社交網(wǎng)絡(luò)，且有效地優(yōu)化了MHRW中自循環(huán)率過(guò)高的問(wèn)題，因此JPS是非?？煽康脑诰€社交網(wǎng)絡(luò)數(shù)據(jù)樣本采集算法。在未來(lái)的工作中，將使用JPS采樣方法測(cè)試更多的大型社交網(wǎng)絡(luò)數(shù)據(jù)集，進(jìn)一步改進(jìn)JPS方法使其能夠在線抽樣真實(shí)的社交網(wǎng)絡(luò)，以應(yīng)對(duì)更多復(fù)雜情況。