社交網絡中低代價路徑發現

張若愚

（四川大學計算機學院，成都610065）

0 引言

六度空間理論[1]（Six Degrees of Separation）是上世紀60年代心理學教授Stanley Milgram提出的，又稱為六度分割理論。該理論指出：任何兩個陌生人之間，最多通過六個人，就可以建立聯系。用一個簡單的說法，最多通過六個中間人，你能夠認識任何一個原本素不相識的人。

六度空間理論旨在呈現出這一概念：世界很小，研究表明，在某些特定的社交網絡中，任意的兩個節點可能通過更少的中間節點就能聯系起來。Lars Back?stromd等人在Facebook上驗證了四度分割[2]，他們得到Facebook上用戶的“度分離”為3.74,進一步證實了“社交網絡拉近了不同國家、地區人與人之間的關系”這一論斷，但是文獻[2]只是驗證了Facebook用戶間隔距離更小，并沒有對用戶之間的關系進行定量分析，而且在線社交網絡中用戶互相關注就可以建立連接，這與現實社交網絡還是有一定區分。文獻[4]發現在科研合作者網絡DBLP中，學者在過去的15年里平均距離都穩定在6附近，驗證了在科研合作者網絡中也存在所謂的“六度分離”的現象。David Liben-Nowell等人在文獻[5]中研究了社交網絡中的鏈接預測問題。James Cheng等人在文獻[6]中研究了有向圖中k-hop可達性查詢的問題。

本文所要解決的問題就是在人際關系傳播中發現強關聯傳遞，更清楚地發現各類交際圈子，以梳理自己的人際關系網絡?？紤]下面的例子：

假設，我想認識曾在中央電視臺馬年春節聯歡晚會演唱的法國影星Madame Sophie Marceau（蘇菲瑪索），我可以通過我的導師A，他認識大學校長B，B認識教育部部長C，C又認識中央電視臺臺長D，D在春晚邀請過Madame SophieMarceau，顯然他們是認識的，這樣我可以通過A→B→C→D→Sophie Marceau。但是通過這條人際關系鏈聯系到Sophie Marceau可行嗎？我的導師A會幫我傳遞到校長B，可是B會輕易去麻煩C嗎？C又會拿這不靠譜的事情去動用他的關系D嗎？盡管我與SophieMarceau之間僅僅隔了四個人，但三個環節都可能面臨無法逾越的阻力。如果換種方式，我的研究生舍友E，他的好朋友F在某大學讀書，F的同學G認識劉一絲（劉歡女兒），劉歡曾在春晚和Sophie Marceau合作過，這條關系傳播雖然多了一跳，但每一步的可達性顯然要比上一種方法強，問題描述如圖1。

圖1 問題描述

傳統的六度空間考慮了人與人之間的聯系，但并沒有考慮社交網絡中關系傳遞的成本、阻尼和激勵等問題,也就是說未對社交網絡中的人際關系進行強弱區分。兩個人僅僅是認識，但較少聯系，他們之間的聯系可稱之為“微弱聯系”（Weak ties）。親人、配偶、關系密切的朋友可被認為是強聯系。本文在六度空間理論的基礎上進一步考慮個體關系的強弱，進而可得在任意給定兩個陌生個體之間建立聯系的代價，以及建立聯系的低代價路徑發現算法，并將本文算法與傳統六度空間理論下最短路徑進行比較，實驗證明本文算法所得路徑代價更低。

1 社交網絡特征分析

大量研究發現，與許多其它種類的復雜網絡相似，社交網絡也具有一些結構特性，例如，小世界現象、無標度特性、冪律分布等。

1.1 社交網絡好友數量分析

美國社會學家格蘭諾維特認為：無論你認識多少人，那些強關系符合150法則，即80%的社會活動可能被150個強關系所占有。以自己為中心，關系最近的人（密友）僅有3-5人，越外層關系越弱，但人數卻越多，如圖2[8]所示。

圖2 朋友關系親疏程度分布

本文對Gowalla社交網絡中用戶的平均好友數量進行了統計，50%用戶的好友少于5個，70%用戶的好友少于10個，這也比較符合社交網絡中大多數節點有少量連邊，少數節點有大量連邊的現象。結果如圖3所示（圖中縱坐標代表累計分布比例，橫坐標代表每個用戶的好友數），曲線分布并沒有之前想象的那么陡峭。

圖3 Gowalla用戶好友數量統計

1.2 無標度特性

自然界與社會生活中，我們感興趣的事件往往都會有一個典型的模型，比如說人的身高分布符合泊松分布（Poisson Distribution）。如圖4所示，大部分個體數據都會集中在網絡平均度＜k＞附近并達到峰值，而遠離平均值的個體數按照指數衰減。另一些真實網絡的度分布則有很大不同，如財富分布、國家人口分布、社交網絡朋友數量分布等。這些網絡中個體間差異懸殊，大多數節點有少量連邊，少數節點有大量連邊，將這種節點度分布不存在有限衡量分布范圍的特征標度的性質稱為無標度。Albert-Laszlo Barabasi和Reka Albert發現這類異質網絡的度分布服從冪律分布（Pow?er-law Distribution）:P(k)∝Ck-r,r為冪律指數，將這種度分布形式的網絡稱為無標度網絡，其網絡頂點的度所表現出來的冪律分布特征稱為無標度特性。

圖4

重尾現象是無標度網絡中冪律分布的重要特征，由圖4（b）可知，冪律分布不存在泊松分布一樣的峰值，曲線拖著一條長尾巴，在線社交網絡中的度分布普遍具有重尾現象。

Gowalla社交網絡中用戶節點的度分布統計結果如圖5所示，實驗結果表明其好友度分布明顯符合冪律分布。

圖5 Gowalla社交網絡度分布

1.3 小世界現象

社交網絡具有顯著的小世界現象,網絡的平均路徑長度越短，小世界現象越明顯。相對于傳統復雜網絡，社交網絡具有更短的平均路徑長度和有效直徑。聚集系數和平均最短路徑一起能展示所謂的小世界效應，有較短的平均路徑長度和較高的聚集系數的網絡就可以稱為小世界網絡。

2 社交網絡人際傳播模型

六度空間理論雖然揭示了人與人之間存在普遍聯系，但沒有對這種聯系作定量的分析。研究表明社會型社交網絡中的朋友關系存在強弱之分[12]，而那些強關系是個體時常能意識到的，往往對該個體有直接影響。我們會認識成百上千的人，并且會根據某一屬性，對這些關系做出分類：比如由血緣關系而產生的親屬這一分類，且根據血緣的相似程度，可進一步確定這種關系的強弱；根據地理位置的遠近，可以劃分出同一國家，同鄉，同城，甚至是鄰居；還有因人類活動而產生的同事、同學、朋友。然而，六度空間理論并沒有對這些關系種類做區分，亦沒有考慮關系之間的相對強弱。在實際生活中，若一個人想通過中間人認識新朋友，往往會考慮到其中的成本，以此確定合適的中間人選，一般每個個體在選擇下一個節點時，往往會優先考慮與自身關系密切的人，即強連接。強連接最有可能的是你目前工作同事，事業伙伴，親屬等，弱連接范圍更加廣泛，同學、朋友、親友等皆有可能。

2.1 人際傳播模型

由于社交關系數據涉及隱私問題，真實數據集難以獲取，所以本文根據獲取的社交網絡數據集，在社交網絡三方閉合和近鄰機制理論的基礎上，研究建立人際傳播模型。

（1）三方閉合

社會網絡發展的基本原則之一三方閉合（Triadic Closure）[14]認為如果兩個未連接的用戶有共同的朋友，則他們成為朋友的可能性增加。

進而，兩個節點的鄰居重疊程度越高，這兩個節點之間的關系越緊密?？梢杂肑accard系數度量這種關系的緊密程度：

其中，Γ(i)表示節點i的鄰居節點集合,Γ(j)表示節點j的鄰居節點集合。

（2）近鄰機制

本文研究的近鄰機制主要是指地理鄰近。一般認為，兩個人活動的地理位置越接近，則二者相似度越大，他們更可能有相似的背景、年齡、興趣，因而他們之間的關系可能更密切。進一步地，如果兩個人體活動區域（每個人的活動區域往往不止一個）的重合度越高，則他們的關系可能越密切。雖然計算機技術的發展促進了交流，使地理的作用在減弱,但研究發現人們仍然趨向于和空間近似的人聯系[15]。因此，本文假設,地理位置越近，社交網絡用戶認識或者成為朋友的可能性更大。

本文在實驗中獲取了Gowalla用戶2008年4月到2010年10月之間的簽到記錄，根據這些簽到數據，對經緯度按合適的網格劃分后，得到不同的區域，每個經緯度會對應到唯一的區域，計算每個用戶在不同區域簽到的次數，得到用戶的簽到向量，并根據這些簽到向量計算用戶之間位置的相似性，本文使用余弦相似度來度量：

具體地，分別用向量A=(A1,A2,…,An)和B=(B1,B2,…,Bn)來表示用戶ui和uj基于位置的簽到向量，用戶位置的相似性可表示為：

基于以上原則，本文建立人際傳播模型，選取合適的傳播個體，實現以較小的代價進行人際傳播的目的。

2.2 社交網絡陌生個體聯系路徑

在實際生活中，兩個人的關系可能存在不對等的情況。考慮以下兩種情況：（1）領導與下屬的關系，從下屬到領導花費的代價可能遠高于從領導到下屬的代價；（2）微博、Twitter這類社交應用，其中的聯系通過“關注”這一方式來建立，這類關系則是單向的，可能A可以從B獲取信息，而B可能獲取不到A的信息。

本文使用的Gowalla數據集中，邊均為雙向邊，即若存在邊A-＞B，則一定存在B-＞A這一條邊。實際上這種情況可以看作上面第二種情況的一個特例，本文結論同樣適用于上面第二種情況。對于上面第一條這種不對等關系，因相關數據難以獲取，因而本文不做考慮，即在后續工作中，均認為A-＞B與B-＞A兩條邊代價一定相等。

根據之前介紹的社交網絡的傳播理論和原則，人際傳播在選擇路徑的下一跳時總是在鄰居節點中選取，在上一節定義的用戶ui和ui的關系強度score(ui,uj)的基礎上，我們只需考慮(ui,uj∈E)的情況，并且認為傳播代價反比于用戶關系的強度，定義如下播代價函數cost：

|Γ(j)|表示下一跳節點j的鄰居節點集合的數量。

基于公式（4）確定網絡中每條邊的代價后，原始的社交網絡可轉化為帶權圖，而本文問題則轉化為在帶權圖求“最小代價路徑”問題，而不同于六度空間理論中的“最短路徑”問題。對該問題求解，可通過傳統的Dijkstra算法來進行。然而考慮到社交網絡規模龐大，求解“最小代價路徑”代價過高，且在人際交往中，用戶往往并不追求代價絕對最小，而僅僅要求代價可接受，即選取合適的傳播個體，實現以較小的代價進行人際傳播的目的。因而，本文在考慮共同好友和近鄰機制的基礎上，本文提出 DLCRP（Discover Low Cost and Reachable Path）算法，具體實現如算法1，對任意兩個陌生個體可以找到一條低代價可達路徑。

算法 1：Discover Low Costand Reachable Path

輸入：好友關系網絡FN，起始節點s，目標節點d，每一跳候選節點個數k

3 實驗分析

3.1 數據集

Gowalla是一個基于位置的社會型社交網絡平臺。本文獲取了Gowalla數據集中完整的社交關系數據,共有196591個用戶，950327條社交關系，6442890條2008年4月到2010年10月的簽到記錄，簽到記錄中包含用戶簽到的具體時間，經緯度信息。

3.2 實驗結果

離心率（Eccentricity），是指從一個給定起始節點到距其最遠節點的距離。圖6給出了Gowalla社交網絡用戶的離心率分布，從下圖可以看出Gowalla社交網絡用戶的離心率主要集中在10附近。

圖6 Gowalla用戶離心率

圖7 傳播代價對比

圖7為進行10次實驗后的傳播代價對比結果，每次實驗隨機生成1000對用戶，然后計算生成1000對用戶人際傳播路徑所需要的平均傳播代價。從對比實驗結果可看出，整體上DLCRP算法要優于BFS，并且可以看出在發現路徑的代價相對較小時，DLCRP的優勢并不是很明顯，但當尋找路徑的代價比較大時，DL?CRP就能明顯表現出其優勢。

隨機選取1000對用戶節點，兩種算法發現的路徑長度統計結果如圖8所示?？梢钥闯?，相比于DLCRP算法，BFS算法發現的路徑長度整體要較低,廣度優先搜索算法在不考慮路徑代價的情況下總能找出跳數最短的路徑。并且路徑長度主要集中2附近，也側面反映了Gowalla網絡的小世界特性。相比之下，本文提出的算法在考慮低代價的情況下路徑長度主要集中在5附近，這也側面說明了最短路徑不一定是最佳路徑。

圖8 路徑長度對比

圖9 運行時間

圖9為隨機選取100到600對用戶節點，兩種算法發現路徑的運行時間的對比結果，DLCRP雖然時間開銷上比廣度優先搜索大，但從實驗結果可以看出其時間開銷基本呈線性增長，算法的可擴展性也很強。

通過以上實驗結果可以觀察到，DLCRP算法雖然在傳播代價上優于廣度優先搜索算法，但在平均路徑的長度和時間開銷上卻劣于BFS，正如天下“沒有免費的午餐”的定理（No Free Lunch THeorem），任何一種學習算法必有其偏好，在某些方面表現好，在另一些方面卻可能不盡如人意。本文提出的模型和算大主要是解決社交網絡中人際傳播低代價的問題。

4 結語

本文在分析社交網絡結構特征及特性的基礎上，根據社交網絡中的三方閉合和近鄰機制建立人際傳播模型，并在模型基礎上進行陌生個體之間的低代價可達路徑發現，實驗結果表明本文提出的DLCRP算法在陌生個體之間路徑發現時的傳播代價明顯低于BFS算法。本文在三方閉合原則的基礎上只考慮了朋友的朋友是朋友，下一步工作還可以進行更有意思的考慮，例如三角關系中“朋友的敵人是敵人”、“敵人的敵人是朋友”等。

參考文獻：

[1]Travers J,Milgram S.An Experimental Study of the Small World Problem[J].Sociometry,1969:425-443.

[2]Backstrom L,BoldiP,RosaM,etal.Four Degrees of Separation[C].Proceedings of the 4th Annual ACMWeb Science Conference.ACM,2012:33-42.

[3]汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].清華大學出版社,2006.

[4]Elmacioglu E,Lee D.On Six Degrees of Separation in DBLP-DB and More[J].ACM SIGMOD Record,2005,34（2）:33-40.

[5]Liben NowellD,Kleinberg J.The Link Prediction Problem for Social Networks[J].Journal of the American Society for Information Science and Technology,2007,58（7）:1019-1031.

[6]Cheng J,Shang Z,Cheng H,etal.K-reach:Who is in Your Small World[J].Proceedings of the VLDB Endowment,2012,5（11）:1292-1303.

[7]WUXin-dong,LIYi,LILei.Influence Analysis of Online Social Networks[J].Chinese Journal of Computers 2014,37（4）:735-752.

[8]姜開達.社交網絡中陌生個體間人際關系形態研究[D].上海交通大學,2013.

[9]luo J.Analysisof Social Network[M].Beijing:Social Sciences Academic Press,2005:152-168

[10]Watts D.J，Strogatz S.H.Collective Dynamics of'Small-World'Networks[J].Nature,1998:440-442.

[11]Freeman LC.Centrality in Social Networks Conceptual Clarification[J].Social Networks,1978,1（3）:215-239.

[12]Newman M E J.A Measure of Betweenness Centrality Based on Random Walks[J].Socialnet works,2005,27（1）:39-54.

[13]Xiang R,Neville J,RogatiM.Modeling Relationship Strength in Online Social Networks[C].Proceedings of the 19th International Conference on World Wide Web.ACM,2010:981-990.

[14]X Shi,LA Adamic,M JStrauss.Networks of Strong Ties.Physicia A:Statistical Mechaics and its Applications,2007,387（1）:33～47.

[15]俞琰.社交網絡朋友推薦算法研究[D].南京航空航天大學,2014.