劉衍珩，李飛鵬，孫鑫，朱建啟

（1. 吉林大學 計算機科學與技術學院，吉林 長春 130022；2. 吉林大學 符號計算與知識工程教育部重點實驗室，吉林 長春 130012）

1 引言

當前，以人際關系網(wǎng)為基礎的社交網(wǎng)絡平臺日益受到廣大網(wǎng)民與商家的追捧，國外的Facebook、Myspace以及國內的人人網(wǎng)、開心網(wǎng)等社交網(wǎng)站迅速發(fā)展，用戶的規(guī)模呈現(xiàn)爆發(fā)式增長，擁有大量擁躉。據(jù)報道Facebook的用戶數(shù)量已經(jīng)超過了7.5億，并且每天至少有大約 50%的用戶登錄 Facebook；2010年3月， Facebook的訪問流量占當月全美網(wǎng)絡流量的7%，而這一比例已超過了Google的訪問流量。根據(jù)CNNIC測算，截止到2009年底中國使用交友網(wǎng)站和社交網(wǎng)站的網(wǎng)民數(shù)已達到1.24億。社交網(wǎng)絡在為用戶提供交流信息平臺的同時，也具有一些社會功能，例如：社交網(wǎng)絡為電子商務的發(fā)展帶來了機遇，政府機構可以通過社交網(wǎng)絡為某個政策的制定征集信息，消費者可通過社交網(wǎng)絡對一個品牌及其產(chǎn)品進行評論等。

社交網(wǎng)絡正逐漸融入人們的日常生活并發(fā)揮著重要影響?？焖侔l(fā)展的社交網(wǎng)絡不僅為信息的傳播與分享提供了新的平臺，而且成為用戶展示自我價值、表達利益訴求和維護人際關系的重要途徑，因此，掌握社交網(wǎng)絡的用戶特征及其行為，分析社交網(wǎng)絡信息傳播的內容、特點、傳播方式及傳播效果具有重要的理論價值和現(xiàn)實意義。

然而，考慮到社交網(wǎng)絡龐大的規(guī)模和復雜的拓撲結構及安全問題，直接將某個社交網(wǎng)絡平臺作為實驗對象進行研究和分析是十分困難的。因此，研究者試圖根據(jù)真實網(wǎng)絡數(shù)據(jù)和網(wǎng)絡所具有的關鍵特征對社交網(wǎng)絡拓撲結構進行模型抽象，從而以拓撲模型代替社交網(wǎng)絡，通過拓撲模型認識社交網(wǎng)絡的基本特性并進行相關研究。同時，對社交網(wǎng)絡拓撲建模的研究有利于深刻理解人類信息交流的過程。

利用建模的方式研究網(wǎng)絡結構和行為的方法由來已久。早在20世紀60年代，Paul Erdos和Alfred Renyi[1]就提出利用隨機圖理論來分析網(wǎng)絡結構的拓撲復雜性，他們構建的網(wǎng)絡模型被稱為“ER模型”；1998年Watts和Strogatz[2]在Nature上發(fā)表的論文中提出了“小世界網(wǎng)絡”模型即WS模型，該模型的主要貢獻是提出了介于規(guī)則網(wǎng)絡和隨機網(wǎng)絡之間的小世界網(wǎng)絡，并能通過重連概率p進行調節(jié)，從而可使網(wǎng)絡結構在規(guī)則網(wǎng)絡和隨機網(wǎng)絡之間轉化；在Falatous等[3]提出了Internet的度分布具有冪律特性之后，無標度網(wǎng)絡便成為了研究者關注的主要對象。Barabasi和Albert對已有的網(wǎng)絡模型進行分析后發(fā)現(xiàn)許多模型都沒有考慮到實際網(wǎng)絡所具有的2個重要特性：增長特性和擇優(yōu)連接特性；基于以上2個特性，Barabasi和Albert[4]于1999年提出了一個無標度網(wǎng)絡模型，并舉例說明許多實際網(wǎng)絡都具有所謂的“無標度性”；隨著對復雜網(wǎng)絡無標度特性研究的深入，學者們發(fā)現(xiàn)社交網(wǎng)絡也具有明顯的無標度特性，Ebel等[5]最先研究了電子郵件網(wǎng)絡的無標度特性，他們建立的電子郵件網(wǎng)絡模型是典型的無標度網(wǎng)絡模型，其出度與入度的冪律指數(shù)分別為-2.0和-1.5；Kumar等[6]在對擁有 500萬用戶的某在線交友網(wǎng)絡的數(shù)據(jù)進行分析后，提出了一種網(wǎng)絡生長模型用以分析網(wǎng)絡的結構演化過程；Backstrom等[7]在對從Live Journal上采集到的有關用戶間所建立的朋友網(wǎng)絡原始數(shù)據(jù)進行分析后發(fā)現(xiàn)個體加入社區(qū)的偏好以及社區(qū)的生長速度都以微妙的方式依賴于網(wǎng)絡的底層結構；Leskovec和 Horvitz[8]利用微軟 Messager即時通信系統(tǒng)采集的數(shù)據(jù)構建了一個無向網(wǎng)絡模型，通過分析模型的結構發(fā)現(xiàn)人們傾向于與自己年紀相仿、語言相通或地區(qū)相近的人進行溝通，并且異性間的通信要遠比同性間的通信更頻繁和持續(xù)時間更長；Centola[9]通過研究在線社區(qū)上健康行為的傳播特點分析了網(wǎng)絡結構對行為傳播的影響作用，分析結果表明行為在具有較好集群結構的網(wǎng)絡中傳播得更快、更遠；孫鑫等[10]從社會工程學的角度研究了社交網(wǎng)絡蠕蟲的傳播機制，通過將影響用戶行為的若干因素進行量化，提出了微觀節(jié)點上的基于用戶安全意識的行為博弈模型，并且通過分析網(wǎng)絡用戶活動的習慣特性，構建了宏觀網(wǎng)絡上離散的基于用戶習慣的社交網(wǎng)絡訪問模型。

以上模型大多數(shù)僅僅給出了節(jié)點間相互作用存在與否的定性描述，而未能體現(xiàn)出實際網(wǎng)絡中節(jié)點間相互作用的強度，因而在反映網(wǎng)絡性質與功能方面存在一定的缺陷。Yook等[11]在考慮到無權網(wǎng)絡的這一缺陷之后，將“邊權”這一表征節(jié)點相互作用強度、頻率等意義的概念引入到網(wǎng)絡模型中，于 2001年提出了一個加權的無標度網(wǎng)絡模型；針對已有的一些加權網(wǎng)絡模型未考慮到模型增長過程中權值的動態(tài)演化這一缺陷，Barrat等[12]提出了BBV模型，該模型在綜合考慮了網(wǎng)絡結構和節(jié)點權重等因素的基礎上研究了網(wǎng)絡的動態(tài)演化情況，研究發(fā)現(xiàn)隨著 BBV模型規(guī)模的增大，模型的度、邊權值和節(jié)點的權重都呈現(xiàn)無標度特性。隨著加權網(wǎng)絡模型的涌現(xiàn)，越來越多的研究者將目光投向了加權網(wǎng)絡。

本研究在綜合考慮信息傳遞的有向特性和信息傳遞的強度以及頻率的基礎上，結合信息傳播所遵循的規(guī)律模擬信息傳遞的動態(tài)過程，通過構造加權有向拓撲模型以更好地仿真社交網(wǎng)絡的拓撲結構。

2 信息傳播的特點

信息傳播具有小范圍內有明確指向性、大范圍呈網(wǎng)狀發(fā)散性的特點。在現(xiàn)實生活中，每個人既是信息的接收者又是信息的傳播者，而接收和傳播信息的媒介主要包括大眾媒介和人際網(wǎng)絡。隨著大眾媒介的不斷升級與變革，人們通過大眾媒介獲取和傳播信息的途徑越來越多，但是不同人群利用大眾媒介獲取和傳播信息的能力是參差不齊的，這也為研究大眾媒介對個人接收和傳播信息的影響帶來了一定的困難。相比于大眾媒介，分析人際網(wǎng)絡對個人接收和傳播信息的影響似乎要容易得多。一般來說，一個人在人際網(wǎng)絡中的個人影響力越大，其獲得和傳播信息的途徑也就越多。

已有的一些研究已經(jīng)對信息在人際網(wǎng)絡中的傳播特點進行了探討。Leskovec等[13]為了探究信息在社會媒體中的傳播過程及其規(guī)律，利用帶標記的網(wǎng)絡對從 3個在線社交網(wǎng)站中獲得的數(shù)據(jù)進行分析，其結果顯示社交網(wǎng)絡中存在著大量的三角結構（由網(wǎng)絡中的3個節(jié)點相互連接所形成的三角形），這些三角結構對于研究信息的傳播以及人與人之間的相互關系具有重要的意義。Leskovec等的研究不僅對從在線社交網(wǎng)絡中獲得的實證數(shù)據(jù)進行了分析，而且還揭示了人際網(wǎng)絡中信息傳播的特點，即在人際網(wǎng)絡中，人們總是傾向于通過自己的朋友獲取信息或是將信息傳遞給自己的朋友。

社交網(wǎng)絡是對現(xiàn)實中人際網(wǎng)絡的一個真實反映，因此，社交網(wǎng)絡中的信息傳播就應該體現(xiàn)人際網(wǎng)絡中信息傳播的特點。因此，本研究在構建社交網(wǎng)絡拓撲模型時，不僅考慮了個體在網(wǎng)絡信息傳播中的影響力，而且借鑒了Holme等[14]在HK模型中使用的演化規(guī)則即TF法則：如果節(jié)點v和節(jié)點w在演化過程的前一步中已經(jīng)以擇優(yōu)規(guī)則連接了一條邊，則在本步演化中，從節(jié)點w的鄰居節(jié)點中選擇一個節(jié)點與節(jié)點v進行連接。TF法則反映了現(xiàn)實生活中普遍存在的“三角推薦”現(xiàn)象，即人們新結識的朋友或喜歡的東西在很大程度上可能是由朋友介紹或推薦的。

3 拓撲模型

3.1 模型簡介

本研究在考慮了社交網(wǎng)絡中信息傳播的有向性和強度的基礎上提出了一種加權有向拓撲模型。在所構建的拓撲模型中，每個節(jié)點代表社交網(wǎng)絡中的一個用戶，節(jié)點間的有向邊表示這2個節(jié)點所代表的用戶之間存在信息傳遞，而邊的權值反映的則是2個節(jié)點間信息傳遞的強度或頻率。節(jié)點間有向邊的權值越大，表明2個節(jié)點間信息傳遞的強度或頻率越大。模型中的節(jié)點可能是信息的接收者，也可能是信息的傳遞者，或者兼具這2種角色。

在描述本文構建拓撲模型的具體過程之前，先介紹模型中用到的如下術語。

1) 節(jié)點出度（Odi）：以節(jié)點i為起點有向邊的條數(shù)即為節(jié)點i的出度。

2) 節(jié)點入度（Idi）：以節(jié)點 i為終點有向邊的條數(shù)即為節(jié)點i的入度。

3) 節(jié)點度（Di）：節(jié)點 i的出度與入度之和即為節(jié)點i的度，Di=Odi+Idi。

4) 節(jié)點出勢（Osi）：以節(jié)點i為起點的所有有向邊的權值之和即為節(jié)點i的出勢。

5) 節(jié)點入勢（Isi）：以節(jié)點 i為終點的所有有向邊的權值之和即為節(jié)點i的入勢。

6) 節(jié)點勢（Si）：節(jié)點i的出勢與入勢之和即為節(jié)點i的勢，Si=Osi+Isi。

7) 集合Outset和Inset：若節(jié)點j是集合Outseti中的一個元素，那么存在節(jié)點i指向節(jié)點j的有向邊，表示為 Outseti={j|wij≠0}；類似地，若節(jié)點 j是集合Inseti中的一個元素，那么存在節(jié)點j指向節(jié)點i的有向邊，表示為Inseti={j|wji≠0}。

3.2 模型構建過程

為了使本文構建的模型能夠展現(xiàn)不同網(wǎng)絡結構的拓撲特征，在模型的構建過程中引入了一個外部參數(shù)δ（1≤δ＜k）來控制新節(jié)點加入網(wǎng)絡后新增有向邊的數(shù)量，以此來改變網(wǎng)絡的拓撲結構。

基于信息傳播的社交網(wǎng)絡拓撲模型的構建過程包括以下步驟。

1) 初始化

① 初始網(wǎng)絡是由 n0個節(jié)點組成的全耦合網(wǎng)絡，即網(wǎng)絡中任意2個節(jié)點之間都存在2條方向相反且權值為1的有向邊。

② 設定網(wǎng)絡中新增邊的權值都為1。

③ 設集合Seti表示節(jié)點i的鄰居節(jié)點的集合，即Seti=Outseti∪Inseti；集合 BSeti中存放集合 Seti中所有節(jié)點的鄰居節(jié)點，即BSeti={j | k∈Seti，j∈Setk}。

2) 模型生長演化

在每一個時間步內增加一個新的節(jié)點，直到網(wǎng)絡規(guī)模為N。

① 新節(jié)點 i根據(jù)網(wǎng)絡中已有節(jié)點的出勢所占比重按概率選擇一個節(jié)點j與新節(jié)點i建立有向連接，選擇節(jié)點所依據(jù)的概率公式為

② 求出集合Seti中各個節(jié)點的鄰居節(jié)點，具體過程為

④ 返回步驟②。

考慮到社交網(wǎng)絡中一個用戶在剛進入網(wǎng)絡時，一般傾向于與網(wǎng)絡中較活躍的用戶進行信息交流，而對于網(wǎng)絡中的已有節(jié)點，當其出勢很大時，通常表明其在網(wǎng)絡中是一個很重要的信息源，因此，不論新節(jié)點是想從網(wǎng)絡中獲取信息還是向網(wǎng)絡中傳播信息，都會傾向于與網(wǎng)絡中出勢較大的節(jié)點建立連接，故而在新節(jié)點剛進入網(wǎng)絡時，會根據(jù)節(jié)點出勢選擇已有節(jié)點與其建立連接。

由于模型中邊的權值表示節(jié)點間信息交流的強度，因此節(jié)點的勢越大，表明該節(jié)點在信息傳遞過程中的重要性越大，則新節(jié)點可通過與該節(jié)點建立連接從而迅速融入網(wǎng)絡。

3.3 模型描述與分析

通過模型構建的具體過程可以看出，本文在構建模型時綜合考慮了個體影響力和現(xiàn)實生活中普遍存在的朋友推薦現(xiàn)象對基于信息傳播的社交網(wǎng)絡拓撲結構的影響，并且通過引入外部參數(shù)δ來調節(jié)個體影響力和朋友推薦這2個因素對模型拓撲結構的影響。

圖1 一個時間步內構建模型的流程

如果設定外部參數(shù)δ的值為1，那么此時的模型僅考慮個體影響力對社交網(wǎng)絡拓撲結構的影響，在網(wǎng)絡的每一個生長演化時間步中，新節(jié)點根據(jù)節(jié)點的影響力選擇與一個已有節(jié)點進行信息交流。

當外部參數(shù)δ的值大于1時，模型綜合考慮個體影響力和朋友推薦這 2個因素對社交網(wǎng)絡拓撲結構的影響。當一個新節(jié)點i進入網(wǎng)絡后，首先會根據(jù)節(jié)點的影響力選擇與一個已有節(jié)點 j進行信息交流；接著，新節(jié)點可能會再次從網(wǎng)絡中選擇一個影響力較大的節(jié)點k與之進行信息交流，或者新節(jié)點會接受與之通信的節(jié)點j的推薦，進而從節(jié)點j的鄰居節(jié)點中選擇一個節(jié)點進行通信；若演化時間步還未結束，新節(jié)點i還是會進行類似的上述過程，即通過已有節(jié)點的個體影響力或朋友推薦選擇與一個節(jié)點交流信息，區(qū)別在于：隨著演化過程的不斷進行，新節(jié)點i的鄰居節(jié)點在不斷地增加，其獲取信息或傳播信息的途徑相應地也就增多了，新節(jié)點可能不需要與個體影響力大的節(jié)點建立連接就能獲取或傳播足夠的信息。而這一現(xiàn)象在模型中體現(xiàn)在模型的每一個演化時間步中，新節(jié)點選擇與個體影響力較大的節(jié)點建立連接的概率在不斷地減小。

下面具體分析模型中節(jié)點的度和節(jié)點的勢在演化過程中可能發(fā)生的變化。

由模型的構建過程可知，當一個新節(jié)點i進入網(wǎng)絡后，對于網(wǎng)絡中已有的節(jié)點 j，可知其度值和勢值受以下4個因素的影響。

1) 節(jié)點j在演化步驟①中被選中與新節(jié)點i建立連接，則其度值增加1，勢值增加1。

因此，一個時刻節(jié)點j的勢Sj的變化為

節(jié)點j的度Dj的變化為

通過上述對某一時刻節(jié)點的度和勢變化的數(shù)學分析（如式(7)和式(8)所示）可知，模型中節(jié)點的度分布和勢分布是與參數(shù)p相關的，而由模型的具體演化過程可知參數(shù) p的值是由外部參數(shù) δ決定的，因此，可通過設定不同的δ值來改變模型中節(jié)點的度和勢分布。

4 仿真實驗

為了驗證所構建的網(wǎng)絡模型的有效性，本文利用多個評估參數(shù)對所生成網(wǎng)絡的拓撲結構進行分析。在仿真實驗中，設定初始網(wǎng)絡規(guī)模n0=5，最后生成的網(wǎng)絡規(guī)模為N=5 000。

實驗中通過對比不同δ值下的節(jié)點度分布來分析外部參數(shù)δ對網(wǎng)絡拓撲結構的影響。從圖2中可以發(fā)現(xiàn)，對應不同的δ值，網(wǎng)絡的節(jié)點度分布是不同的。當δ=1時，節(jié)點度分布服從指數(shù)為-2.35的冪律分布，此時的網(wǎng)絡實際上就是以節(jié)點出勢為衡量指標的擇優(yōu)模型；當δ=5時，網(wǎng)絡的節(jié)點度分布服從指數(shù)為-2.73的冪律分布，此時的網(wǎng)絡主要從已連接節(jié)點的鄰居節(jié)點中選取節(jié)點。

圖2 不同δ所對應的節(jié)點度分布情況

在以下的仿真實驗分析中，本文不再贅述不同δ值對網(wǎng)絡拓撲屬性的影響，而是設定δ=3。

4.1 節(jié)點度分布

實驗中首先對模型中節(jié)點的度值分布進行研究。通過對實驗數(shù)據(jù)的分析，發(fā)現(xiàn)本文所構建的社交網(wǎng)絡模型中的節(jié)點出度和節(jié)點入度的分布都是服從冪律分布的，在對節(jié)點出度值和入度值的分布情況進行線性擬合后，發(fā)現(xiàn)節(jié)點出度服從冪指數(shù)為-2.19的冪律分布，節(jié)點入度服從冪指數(shù)為-2.16的冪律分布。圖3表明了節(jié)點出度和節(jié)點入度在雙對數(shù)坐標下的具體分布情況。

圖3 節(jié)點出度和入度在雙對數(shù)坐標系下的分布情況

4.2 節(jié)點勢分布

通過仿真實驗發(fā)現(xiàn)，不僅是網(wǎng)絡中節(jié)點的出度與入度服從冪律分布，節(jié)點的出勢與入勢也是服從冪律分布的。在對節(jié)點出勢值和入勢值的分布情況進行線性擬合后，發(fā)現(xiàn)節(jié)點出勢服從冪指數(shù)為-2.44的冪律分布，節(jié)點入勢服從冪指數(shù)為-2.45的冪律分布。圖4表明了節(jié)點出勢和節(jié)點入勢在雙對數(shù)坐標下的具體分布情況。

4.3 度—勢相關性

既然節(jié)點的度值與勢值都服從冪律分布，那么節(jié)點的度值和勢值之間是否也存在某種關聯(lián)呢？對度—勢相關性最早的研究是由 Barrat[15]等完成的。Barrat等在研究了大量實際網(wǎng)絡數(shù)據(jù)集的基礎上，發(fā)現(xiàn)加權網(wǎng)絡中節(jié)點的度值與勢值是存在冪律關系的，若用s表示節(jié)點的勢，k表示節(jié)點的度，則節(jié)點的度值與勢值的冪律相關性可以表示為

圖4 節(jié)點出勢和入勢在雙對數(shù)坐標系下的分布情況

Barrat等總結出冪律指數(shù) β的值一般是介于1～2之間的。

本文對節(jié)點的度—勢相關性進行了研究。通過對仿真實驗得到的有關節(jié)點的度值與勢值的數(shù)據(jù)進行線性擬合分析后發(fā)現(xiàn)，節(jié)點度值與勢值之間的確是存在冪律關系的，圖5(a)表明了節(jié)點出度與出勢的相關性，其中，直線是經(jīng)過線性擬合后得到的，其斜率為1.09；圖5(b)表明了節(jié)點入度與入勢的相關性，其中，直線也是經(jīng)過線性擬合后得到的，其斜率為1.18，與實證數(shù)據(jù)相符[15]。

圖5 節(jié)點度勢相關性

4.4 聚集特性

隨著對網(wǎng)絡拓撲的進一步研究，人們發(fā)現(xiàn)僅用節(jié)點度的分布來刻畫網(wǎng)絡拓撲結構是遠遠不夠的，滿足同樣冪律分布的網(wǎng)絡完全可以呈現(xiàn)截然不同的拓撲結構。在冪律分布特性的基礎上，人們開始研究網(wǎng)絡拓撲中存在的聚集特性。聚集特性是反映網(wǎng)絡節(jié)點關聯(lián)性[16]的特性之一，并通過計算網(wǎng)絡的聚集系數(shù)來反映網(wǎng)絡的聚集特性。常用的計算無向圖的聚集系數(shù)的公式為

其中，ci表示節(jié)點i的聚集系數(shù)值，ki表示節(jié)點i的度值，Ei表示節(jié)點i的鄰居節(jié)點間存在的連接數(shù)。

本文在探討了節(jié)點度與勢分布的基礎上，對網(wǎng)絡的聚集特性也進行了分析。由于節(jié)點的聚集系數(shù)是用來刻畫一個節(jié)點與鄰居之間的親疏程度的，即對于一個節(jié)點而言，只要其鄰居節(jié)點間在網(wǎng)絡拓撲圖中存在連邊，則認為其鄰居節(jié)點間是存在信息交流的，而不用考慮鄰居節(jié)點間連邊的具體方向，因此，在計算節(jié)點的聚集系數(shù)時是不需要考慮網(wǎng)絡的有向性的。本文在計算節(jié)點的聚集系數(shù)之前，先對加權有向模型進行了無向化處理，然后再利用式(10)進行計算。具體的無向化處理方式為：對于網(wǎng)絡中的節(jié)點i和節(jié)點j，只要wij和wji中有一個不為0，則令鄰接矩陣A中Aij和Aji的值為1。圖6表明了節(jié)點聚集系數(shù)與度數(shù)的關系，圖6(a)中直線是經(jīng)過線性擬合得到的，其斜率為-0.97。同時，本文還計算了網(wǎng)絡的平均聚集系數(shù)，其值為 0.312，該值與Newman M E J對一些社交網(wǎng)絡的平均聚類系數(shù)所做的統(tǒng)計相吻合。

圖6 聚集系數(shù)與度數(shù)的關系

4.5 網(wǎng)絡層次性

為了研究社交網(wǎng)絡自發(fā)的多層次性質，以核數(shù)[17]概念為基礎，利用本文提出的社交網(wǎng)絡模型對網(wǎng)絡的層次性做定量分析，這不僅可以細致地刻畫社交網(wǎng)絡的特征，而且可以全面地描述網(wǎng)絡拓撲結構。

若一個節(jié)點存在k-核，而在(k+1)-核中被移除，則稱這個節(jié)點的核數(shù)為 k；其中，k-核是指原始圖經(jīng)過迭代消去所有節(jié)點度小于或等于k的節(jié)點后得到的子圖。一個核數(shù)為k的節(jié)點可以出現(xiàn)在k核子圖中，但不會出現(xiàn)在(k+1)核的子圖里，筆者把所有節(jié)點核數(shù)中的最大值稱為圖的核數(shù)。

節(jié)點核數(shù)在某種程度上是比節(jié)點度數(shù)更能反映關聯(lián)性的度量指標，可以表明節(jié)點在核中的深度。若一個節(jié)點的節(jié)點度數(shù)很高而節(jié)點核數(shù)很小，則說明其關聯(lián)并不緊密。例如，在具有N個節(jié)點的星形網(wǎng)絡中，其中心節(jié)點的度數(shù)為N-1，而核數(shù)為0，此時，它與鄰居節(jié)點的連通性易于破壞。

圖7表明了本文構建的社交網(wǎng)絡模型中節(jié)點的核數(shù)和度數(shù)的關系，圖7中直線是經(jīng)過線性擬合得到的，從圖7中可以發(fā)現(xiàn)當節(jié)點度小于100時，節(jié)點核數(shù)和度數(shù)呈現(xiàn)冪律關系，當節(jié)點度大于100時，節(jié)點的核數(shù)基本保持不變。

圖7 節(jié)點核數(shù)與度數(shù)的關系

4.6 網(wǎng)絡異質性

網(wǎng)絡異質性是指網(wǎng)絡中節(jié)點的屬性不是大致相同的，而是存在著很大的差異。近年來的研究發(fā)現(xiàn)，絕大多數(shù)復雜網(wǎng)絡都呈現(xiàn)出極強的異質性[18]。以節(jié)點的度值分布為例，在絕大多數(shù)網(wǎng)絡中，節(jié)點的度值服從冪律分布，該冪律關系表明：網(wǎng)絡中節(jié)點的度值分布并不像想象中的那樣是均勻分布的，而是極其不均勻的，極少數(shù)節(jié)點的度值很大，而絕大多數(shù)節(jié)點的度值很小。為了定量地研究網(wǎng)絡的異質性程度。本文利用經(jīng)濟學中描述收入分配程度不均的2個重要概念：洛倫茲曲線和基尼系數(shù)，來分析本文構建的社交網(wǎng)絡模型的異質性。通過仿真實驗發(fā)現(xiàn)洛倫茲曲線和基尼系數(shù)在分析網(wǎng)絡拓撲結構的異質性方面具有很好的效果。

復雜網(wǎng)絡的洛倫茲曲線和基尼系數(shù)[19]是如下定義的：設一個復雜網(wǎng)絡具有 N個節(jié)點，記為 v1,v2,…,vN，將這 N個節(jié)點按照度值由小到大進行排序，將相應節(jié)點的度值記為則顯然有對于即

復雜網(wǎng)絡的洛倫茲曲線是以累計節(jié)點數(shù)除以總節(jié)點數(shù)為橫軸，以累計度值除以總度值為縱軸所建立的直角坐標系中的一條曲線曲線（如圖8中的曲線OED）。將基尼系數(shù)定義為圖8中的曲線OED與直線OD之間的面積（用A表示）和三角形OCD的面積（A+B）的比值定義為基尼系數(shù)G，即

圖8 復雜網(wǎng)絡的洛倫茲曲線

由于三角形OCD的面積為1/2，故可以得到復雜網(wǎng)絡基尼系數(shù)的計算公式為

通過復雜網(wǎng)絡基尼系數(shù)的計算公式（式(14)）可知：0≤G≤1，并且G的值越大，表明網(wǎng)絡的異質性程度越大；G的值越小，則表明網(wǎng)絡異質性程度越小。由此可見，通過計算復雜網(wǎng)絡的基尼系數(shù)可以定量地衡量網(wǎng)絡的異質性程度。

本文從節(jié)點度值與勢值這2個方面對所構建的社交網(wǎng)絡模型進行了異質性分析。節(jié)點度值的異質性分析結果顯示：相比于節(jié)點入度，節(jié)點出度的異質性較小，其基尼系數(shù)為 0.496，如圖 9所示。對節(jié)點勢值的異質性分析也得到了與節(jié)點度值相似的情況，在此不再贅述。

圖9 洛倫茲曲線和基尼系數(shù)

5 結束語

本文探究了信息在人際網(wǎng)絡中的傳播特點，基于信息傳遞的有向特性，通過構造加權的有向拓撲模型模擬了信息傳遞的動態(tài)性，更好地仿真了社交網(wǎng)絡的拓撲結構。利用該模型構建了社交網(wǎng)絡拓撲，從度、勢分布、度—勢相關性、網(wǎng)絡聚集特性、網(wǎng)絡層次性和網(wǎng)絡異質性等方面對網(wǎng)絡拓撲結構進行了分析。結果表明所生成網(wǎng)絡拓撲結構的度、勢分布以及度—勢相關性具有明顯的冪律特性。同時，網(wǎng)絡拓撲的聚類系數(shù)、核數(shù)和基尼系數(shù)均表明該模型能夠較好地體現(xiàn)社交網(wǎng)絡的聚集特性、層次性和異質性。綜上所述，本文所構建的網(wǎng)絡模型能夠正確地體現(xiàn)實際人際關系網(wǎng)絡的拓撲結構。

[1] ERDOS P, RENYI A. On the evolution of random graphs[J]. Publication of the Mathematical Institute of the Hungarian Academy of Science, 1960, 5(12)∶17-60.

[2] WATTS D J, STROGATZ S H. Collective dynamics of “small-world”networks[J]. Natrue, 1998, 393(6)∶440-442.

[3] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the Internet topology[J]. Proceedings of SIGCOMM,1999, 29(10)∶251-262.

[4] BARABASI A, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286 (5439)∶509-512.

[5] EBEL H, MIELSCH L I, BORNHOLDT S. Scale-free topology of E-mail networks[J]. Physical Review E, 2002, 66(3)∶35-103.

[6] KUMAR R, NOVAK J, TOMKINS A. Structure and evolution of online social networks[A]. KDD[C]. New York, USA, 2006. 611-617.

[7] BACKSTROM L, HUTTENLOCHER D P, KLEINBERG J. Group

而折線OED下的面積（用B表示）實際上是N-1個梯形和一個三角形面積的和，即formation in large social networks∶ membership, growth, and evolution[A]. KDD[C]. New York, USA, 2006. 44-54.

[8] LESKOVEC J, HORVITZ E. Planetary-scale views on a large instant-messaging network[A]. Proceedings of WWW 2008[C]. Beijing,China, 2008. 915-924.

[9] CENTOLA D. The spread of behavior in an online social network experiment[J]. Science, 2010, 329(9)∶1194-1197.

[10] 孫鑫，劉衍珩，朱建啟. 社交網(wǎng)絡蠕蟲仿真建模研究[J]. 計算機學報，2011, 34(7)∶1252-1261.SUN X, LIU Y H, ZHU J Q. Research on simulation and modeling of social network worm propagation[J]. Chinese Journal of Computers,2011, 34(7)∶1252-1261.

[11] YOOK S H, JEONG H, BARABASI A L. Weighted evolving networks[J]. Physical Review Letters, 2001, 86(25)∶5835.

[12] BARRAT A, BARTHELEMM Y, VESPIGNANI A. Weighted evolving networks∶ coupling topology and weights dynamics[J]. Physical Review Letters, 2004, 92(22)∶2287011-2287014.

[13] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Signed networks in social media[A]. CHI[C]. New York, USA, 2010. 1361-1370.[14] HOLME P, KIM B J. Growing scale-free networks with tunable clustering[J]. Physical Review E, 2002, 65(2)∶1071-1074.

[15] BARRAT A, BARTHELEMY M, PASTOR-SATORRAS R. The architecture of complex weighted networks[J]. The National Academy of Sciences of The United States, 2004, 101(11)∶3747-3752.

[16] NEWMAN M E J. Properties of highly clustered networks[J]. Physical Review E, 2003, 68(2)∶26121-26126.

[17] 周苗，楊家海，劉洪波. Internet網(wǎng)絡拓撲建模[J].軟件學報，2009,20(1)∶109-123.ZHOU M, YANG J H, LIU H B. Modeling the complex Internet topology[J]. Journal of Software, 2009, 20(1)∶109-123.

[18] KOSSINETS G, WATTS D J. Origins of homophily in a evolving social network[J].American Journal of Sociology, 2009, 115(2)∶405-450.

[19] 王林，戴冠中. 復雜網(wǎng)絡的Scale-free性、Scale-free 現(xiàn)象及其控制[M].北京∶科學出版社，2009.WANG L, DAI G Z. Scale-free Property, Scale-Free Phenomenon and Their Control in Complex Networks[M]. Beijing∶ Science Press, 2009.