基于相似性的社交網絡結構建模

馬 翔 徐名海 吳宇鵬

(南京郵電大學江蘇省無線通信重點實驗室 江蘇 南京 210003)(南京郵電大學通信與信息工程學院 江蘇 南京 210003)

0 引 言

社交網絡是一種特殊且廣泛存在的復雜網絡[1]，社交網絡結構建模是社交網絡眾多研究方向的基礎研究領域，社交網絡模型的合理性直接影響基于其上的其他相關領域研究成果的可靠性。在當今社交模式高度網絡化時代，社交網絡的研究是具有實用價值和重要理論意義的，社交網絡建模可以挖掘社會網絡中的關系，有效地模擬各種社會行為，更好地明白和解釋各種社會現象包括信息傳遞、病毒傳播、謠言傳播等，它能從各個方面協助人們更深入理解真實世界。但由于社交網絡具有很多動態性的結構特征以及無法對社交網絡特殊對象做實驗，研究面臨著如何定義和衡量節點鏈接關系相關的重大障礙。例如，估算社交網絡的主要工具是使用各種調查或對相關方的訪談。鑒于每個人有數百甚至數千個社交關系，讓他們以任何所需的準確度回憶相關的人是很困難的。此外，可能無法聯系或觀察網絡中的所有節點，并且在聯系時，他們可能有理由扭曲或隱藏關系。即使是最近對網頁、共同作者、電子郵件和引文網絡的研究，雖更容易獲得其中數據，但也忽略了其他測量特性。此外，社交網絡隨著時間的推移不斷變化，并以各種方式重疊，親密的朋友可能無法長時間互動。關于社交網絡結構的大部分信息來自對鏈接的有限測量，這些鏈接通常采用靜態和離散的視圖，而這些視圖本質上是動態的和易變的。所以有必要通過其建模來探究社交網絡的演化，而如何構建逼近真實社交網絡的結構模型是具有挑戰的。

目前學術界對社交網絡結構建模的研究相對較少，現有的研究主要從單一的網絡特征來建模或從大數據的統計特性來說明社交網絡，但這些方法具有一定的缺陷。從宏觀角度來看，大數據是用軟件工具捕捉收集到的一系列數據集合，所以由大數據得到的各種社交網絡拓撲結構和各種特性具有后驗性，其對于社交網絡在信息傳遞的預演無能為力。從微觀角度來看，社交網絡的拓撲結構呈現是由多種因素驅使的，單一特征不足以說明其演化的特性。

針對上述問題，本文創新性地提出了一種相似網絡模型。首先通過分析網絡中節點間的各種活動行為、節點的個性特征，對用戶行為相似度及特征相似度進行量化，將量化結果作為節點外部生長鏈接邊的概率；然后根據網絡結構影響完成內部演化；最后從度飽和的角度不停地更新網絡鏈路。

1 研究背景

許多學者們為了能夠更好地解釋和模仿社交網絡的生成規律和演化規律，紛紛提出各種方法模型試圖來構建符合現實世界特征的社交網絡。1998年，Watts等[2]提出了小世界網絡模型，該模型基于現實世界中人們有相同數量朋友的假設，其度分布為泊松分布且峰值取平均值，平均路徑短且聚集系數大。1999年，Barabasi等[3]提出了一種增長模型(BA無標度模型)，通過加入新的節點來實現網絡的連續增長，而這些新的節點總是傾向于連接已經擁有大量連接的節點，他們應用了優先附著的概念，其中新節點以非均勻概率附加到網絡圖。文獻[4]提出的最近鄰模型中，新節點i連接到隨機節點j和i周圍的兩跳鄰居的隨機對，可以對模型進行參數化來確定節點的數量及其連接的概率。Bodine-Baron等[5]提出了基于格的網絡模型，該模型在任何具有足夠小的距離依賴連接概率時的度分布服從泊松分布，并且這種網絡具有可搜索性。Newman[6]分析了科學合作網絡，發現兩個節點熟悉的可能性隨著他們共同的合作者數量的增加而增加。近年也有研究從社團結構[7]、優先連接與三角結構[8]來構建社交網絡模型。

這些網絡模型雖然捕獲了社交網絡的基本屬性，但其仍然忽視了一些社交網絡中存在的關鍵屬性，因此有必要進一步研究與現實世界更為一致的社交網絡結構特征。社交網絡的相似性屬性在真實世界中是具有廣泛實踐背景的。從心理學上來說，節點總傾向于與自己行為活動、個性特征相同的節點認識，他們的鏈路連接率比兩個個性不同、活動不同的對象連接率更高，這說明了節點在社會網絡中的連接有可能是基于某種相似的性質，節點與節點之間是由于存在某種共同的特性才相連。從歷史的演進來說，社交網絡的超穩定是基于網絡結構一些相似的特征，網絡的結構背景在網絡演化過程中會促使節點間邊的建立與斷開，節點間邊的斷開和新建又促使網絡不停地變化，但總體上各個時期的網絡結構是相似的。近年，學術界的關注焦點轉向了復雜網絡的相似性。文獻[9-11]證明了不同的局部網絡可以覆蓋不同的邊框，來揭示復雜網絡的自相似性，并使用盒子計數來統計復雜網絡的自相似性。還有許多研究人員從歷史位置[12]、節點影響力[13-14]、節點行為[15-16]和節點鄰居[17]來分析研究并計算節點的相似度。但是鮮有學者從相似性和網絡結構影響來探討社交網絡建模。本文就社交網絡廣泛存在的相似性提出一種基于相似性與網絡結構的社交網絡建模方法，本文所提出的相似性概念基于節點的內在屬性與外在行為活動。每個節點有自己活動范圍和個性特征，節點的相似性由這些節點間屬性重合集合決定，兩個節點的某種相似度特征越高，則這兩個節點越有可能建立邊的關系。相似性是社交網絡中存在的重要屬性，它不是偶然的，它應該發生并始終保持在網絡演化的進程中。因此建立并研究基于相似性網絡演化模型有利于更好地認識現實世界中的社交網絡。

2 相似網絡模型

復雜網絡的相似性屬性在真實世界中具有廣泛的實踐背景，人們總是樂于與那些在各個方面都與自己相似的人交朋友，類似于多米諾骨牌效應。社交網絡的節點并不總是異質的，在許多方面都表現了相似的特征。本文所提出的相似網絡模型是基于相似性的，并考慮網絡結構影響，如果兩個節點行為相似和特征相似大于相似度閾值，則其建立連接并形成復雜網絡的相似特征。要計算節點的相似性，必須選擇相關的節點屬性，對于節點間的相似性，我們從節點的內在屬性與外在行為活動來考慮。對于外在行為活動主要考慮簽到集，內在屬性主要考慮節點個性，而網絡結構則在整個網絡演化過程中影響網絡鏈路的刷新。

2.1 社交網絡相似性原理

每個活躍用戶在不同位置聚類上有不同活動程度的行為模式，一個用戶的外出位置一定程度上反映了該用戶的活動行為，用戶間所在位置相同的概率越大，用戶就越有可能認識。本文在基于位置的社交網絡中，組合節點所在物理位置與線上虛擬地點來探究用戶活動，通過將位置集群與用戶簽到相結合來挖掘個人外在的行為模式，然后基于個人用戶的所有簽到集，計算用戶之間的行為相似性。如圖1所示，網格代表了不同的位置，用戶可在不同的位置活動，當兩用戶所處同一位置越多時，行為相似度越高。

圖1 用戶位置活動

定義1在不同位置集群中各個節點的活動行為稱為簽到集。

節點A與節點B的行為相似定義在位置活動的一致性，則節點A與節點B的行為相似性表達式為：

(1)

用戶的內在屬性主要表現在節點的個性特征上。一個用戶的內在屬性決定他的網絡圈，也決定了他在信息傳遞過程中所參與的互動性，個性相同的用戶更樂意在一起交流，傳遞信息。若兩個對象存在共同的內在屬性，則定義兩個對象具有特征相似，其表達式為：

(2)

式中：C表示節點個性集合；Ci?C；C(A)表示節點A的共有多少種個性選擇；Ci(A)表示節點A個性為Ci；Ci(A)×Ci(B)表示節點A與節點B個性相同都為Ci。如果兩個節點具有相同的個性特征，則他們比兩個個性特征不同的對象更相似，更傾向于建立連接。

2.2 網絡結構的背景影響

構建社交網絡模型，除了考慮節點的特征外，還需考慮社交網絡結構的背景影響。對于單個節點周圍的網絡結構從節點鄰居切入，對于大規模的網絡結構從群結構切入。一個用戶在網絡結構中所受到的影響與其鄰居密切相關，用戶擁有共同的鄰居結構，受到的影響越相似，用戶越有可能建立連接。網絡拓撲在一定程度上能夠反映出節點之間的連接關系，如圖2所示，當兩個節點擁有多個相同的鄰居結構時，他們會傾向于建立連接，其中圖2(b)新出現的邊代表兩個節點基于擁有多個共同的節點建立的邊關系。

(a) (b)

社交網絡大規模的結構背景在網絡演化過程中會促使節點間邊的建立與斷開。當信息在社交網絡中傳輸時，會促使一些節點形成群結構，如果兩個節點在同一個網絡群范圍內接收相同的信息，則兩個節點受到網絡結構推動的影響，會相互建立連接。圖3展示了群結構的形成，信息傳輸促使節點形成群結構進而推進節點間邊的建立。社交網絡群結構在演變時，一些節點會在不同的群結構中來回切換并扮演不同的角色，那些微交互的節點在群結構的變化中更容易受到影響進而斷開連接。圖4展示了節點邊的斷開，網絡群隨著時間的推移而變化，弱連接的節點容易斷開連接，轉而與其他節點建立連接。

圖3 群結構的形成

圖4 節點邊的斷開

對于具有共同相鄰結構的節點，我們可通過節點網絡局部拓撲重合程度的量化，求其鄰居集來說明節點受到的影響。

定義2在網絡拓撲結構中節點兩跳內所有鄰居節點稱為節點的鄰居集。

若兩個節點擁有共同的鄰居結構，則節點受到相同的影響。節點A與節點B的共鄰結構定義為節點存在共同的鄰居集，其表達式如下：

(3)

式中：N(A)是指節點A的鄰居集；N(A)∩N(B)表示節點A和節點B共有的鄰居；N(A)∪N(B)表示節點A和節點B所有的鄰居。當節點A與節點B存在多個相同的鄰居時，則節點A與節點B共鄰結構性越高，他們所受到的影響越相同。

對于群結構變化作于節點的影響定義為:

ifn(i)join one group

thenn(i)neighbors increase and group clustering increase

ifn(i)leave one group

thenn(i)weight change with neighbor

它表示群結構的形成促使節點邊的建立和群聚類變化，群結構的變化促使節點邊緣權重發生變化，n(i)表示節點i。

3 基于相似性的社交網絡建模

綜合第2節內容，本文從節點的內在屬性與外在行為活動，以及網絡結構背景影響來提出相似網絡模型，在網絡演化過程中節點A與節點B的節點相似度S為：

S(A,B)=activity(A,B)?neighbor(A,B)?

character(A,B)

(4)

式中：?算子表示在社交網絡生長過程中由節點的內在屬性與外在行為活動以及網絡結構共同作用所產生的演化關系。節點A與節點B有邊的關系的概率取決于兩者某些屬性相似的程度，相似度越高，節點A與節點B越有可能連接。

基于以上所考慮的簽到集，節點特征，網絡結構，本文提出了一種相似網絡模型。在構建網絡的過程中針對不同屬性的新加入節點根據不同的相似性指標來進行網絡的外部增長，并對網絡中已有的節點進行內部演化，在此基礎上不斷更新網絡中的邊緣關系，直到網絡規模達到預期。具體模型算法過程如下所述。

步驟1網絡初始狀態下，設置共有m0個節點，它們呈現隨機連接的狀態并賦予這m0個節點屬性特征，同時設置一個規模上限N、相似度閾值T，以及一個節點度上限值θ。

步驟2網絡中每新增一個節點，就賦予該節點屬性特征，包括該節點的位置集群和個性特征。

步驟3根據式(1)-式(2)來計算所增節點與其他節點的行為相似與特征相似度。當行為相似與特征相似的加權和大于閾值相似度T時，建立新增節點與所屬網絡節點的邊。該步驟實現了社交網絡的外部增長。

步驟4已經存在于網絡中的個體節點根據節點共鄰結構和群結構來進行兩兩連接。節點會由于鄰居拓撲結構和群結構的形成與其他節點建立邊關系或斷開邊關系。當兩個節點擁有多個共同的節點或兩節點一起組成新的群結構時建立連接，當兩個節點屬性變化時不再存有共同的行為相似和特征相似，則斷開邊的連接關系，根據式(3)和群結構作用于節點影響的偽代碼來完成。該步驟實現了社交網絡的內部演化，即存在網絡中的節點有新的邊產生也有舊的邊斷開。

步驟5遍歷網絡中已生成的個體節點，判斷其節點度是否大于θ。對于節點度大于θ的個體節點，它們將與節點相似性最小的鄰居節點斷連；對于節點度小于等于θ的個體節點，它們將隨機與節點相似度低的一級鄰居節點斷連。根據鄧巴數的概念，人類擁有穩定社交網絡的人數，當社交網絡中某個用戶的節點度達到一定的上限值后，則認為該用戶的節點度達到飽和，其必然要與某些弱連接的鄰居移除邊緣關系來為下一步的網絡生長提供空間，而其他不飽和節點也會隨機與某些弱連接的鄰居進行斷連。該步驟實現了社交網絡邊緣關系的更新。

步驟6比較此時網絡中個體節點數N0與網絡規模上限N，當N0

與傳統模型算法相比，該算法在基于相似性的社交網絡演化生長的過程中，不僅考慮了節點的內在屬性和節點的外在行為，而且考慮了網絡結構的影響。網絡中節點邊緣關系的變化不只產生在新節點間，也存在于舊節點之間。節點間的邊緣關系也不僅考慮了鏈路的建立，還考慮了鏈路的移除。社交網絡的生命周期會經歷增長、擴展、均衡、更新四個階段。網絡中節點與節點間關系的變化是不規律的，呈現出局部起伏變化，整體節點規模呈螺旋式上升。本文所提出的基于相似性的社交網絡建模符合社交網絡的增長模式與內部演化結構。

4 仿真與結果分析

本文實驗使用Python語言，實驗初始化節點設為m0=6；根據鄧巴數的概念，每個節點的節點度上限設為θ=150；考慮到真實網絡相似節點的連接，我們建立相似度閾值T=0.75。網絡上限N∈{100,500,1 000,2 000,5 000，8 000,10 000}。

4.1 網絡拓撲

網絡構建效果如圖5所示。N=100的網絡是一個小型的社交網絡，其邊緣比較稀疏，節點的度值都比較小，存在少量孤立節點。N=1 000和N=5 000的網絡是中等的社交網絡，邊緣相對密集，節點的度值相對較大，它能劃分成多個結構相似的網絡，也顯現出了整體網絡結構與部分網絡結構相似性，即具有網絡相似性。隨著節點的不斷增加，得到了N=10 000的大型社交網絡，其邊緣密集，許多節點度達到了鄧巴數上限值150，具有一定的社團結構。節點的活動集群越多，就越容易與其他節點建立邊的關系。整個演化過程，隨著節點數的不斷添加，邊緣的密集性、節點度的變化呈現出網絡結構相似性，這與實際的社交網絡演化一致。

(a)N=100

4.2 度分布

在本文提出的相似網絡中，度分布表示的是網絡中一個節點所擁有的邊的數量。圖6展示了不同節點規模的社交網絡所呈現的度分布。可以看出擁有不同節點規模的社交網絡的度分布都近似呈現出冪律分布的特征，而且冪律指數變化區間為2～3。顯然，這表明冪律并不總是優先聯系的結果，并且隨著網絡規模的增大，節點度出現兩極分化，在考慮邊緣關系的更新與度飽和的狀態下消除了網絡中節點擁有巨大度的情況，這與實際社交網絡特征一致。

(a)N=100

4.3 聚類系數與平均最短路徑

本文將相似網絡的聚類系數和平均路徑長度與復雜網絡基本網絡模型進行了比較，其中：WS表示小世界網絡；BA表示無標度網絡；ER表示隨機網絡；RG表示規則網絡。越來越多的節點加入使得網絡規模增大，網絡的聚集性被不斷稀釋，這使得網絡的聚類系數不斷減小。圖7為聚類系數隨網絡大小增大的變化曲線，在相同的網絡規模下，相似網絡的聚類在[0.282,0.401]之間，BA的聚類在[0.021,0.088]之間，WS的聚類在[0.268,0.418]，ER與RG的聚類基本不變化，因此相似網絡的聚類高于BA網絡，低于WS網絡，這符合實際社交網絡聚類變化的特征。網絡中新的鏈路的生成促使網絡中的平均最短路徑長度不斷增大。從圖8所示的平均路徑長度變化曲線可知，相似網絡的平均路徑長度在[2.811,3.948]之間，而BA的平均路徑長度在[3.128,4.612]之間，小世界的平均最短路徑為[2.218,3.881]，ER與RG的平均最短路徑基本不變化，這表明相似網絡的平均路徑長度小于BA，大于WS，這與實際社交網絡最短路徑變化一致。可見，基于相似性和網絡結構影響形成的網絡更容易聚集，平均路徑長度更短，具有更快的信息傳輸，這些特征變化都符合實際社交網絡特征的變化。

圖7 聚類系數

圖8 平均最短路徑

表1直觀地給出了復雜網絡基本網絡模型的統計特征對比，其中新浪微博的數據從微博數據中心獲取。可以看出，現實生活中的社交網絡同時擁有較短的平均最短路徑和較大的聚類系數，度分布近似冪律分布。規則網絡和隨機網絡的平均最短距離太小，與實際情況不符。小世界網絡的度分布呈現泊松分布，也與實際情況不符。無標度網絡的度分布很好地呈現了現實網絡的特征，但其聚類系數較小，不符合實際情況。本文所提出的相似網絡模型不僅度分布呈現冪律分布，還同時具有較短的平均最短路徑和較大的聚類系數，可以較好地反映真實網絡的情況。

表1 復雜網絡基本網絡模型的統計特征對比

5 結 語

社交網絡結構建模與現實世界演化越一致，越有利于研究其他基于社交網絡動態特征分析的內容。本文提出了一種相似網絡模型。仿真結果顯示，該模型的度分布近似呈現出冪律分布，所產生平均路徑小于BA網絡，聚類系數大于BA，其鏈路數隨著網絡規模的擴大在建立與阻斷的過程中呈螺旋式增長，表明本文模型更接近社交網絡結構特征。

未來工作可以考慮節點間特定的關系對社交網絡的影響來構建社交網絡模型。如互鎖效應，當一個節點在網絡中受到影響時，與其相關的其他節點在某種程度上也會受到影響，此時網絡結構會有所波動，考慮更多符合實際網絡的特征來構建模型能夠達到更加逼近現實社交網絡的效果。