基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ?/h1>

2013-09-18 02:41:24劉衍珩李飛鵬孫鑫朱建啟

通信學(xué)報訂閱 2013年4期 收藏

關(guān)鍵詞：信息模型

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

（1. 吉林大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130022；2. 吉林大學(xué) 符號計算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長春 130012）

1 引言

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

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

然而，考慮到社交網(wǎng)絡(luò)龐大的規(guī)模和復(fù)雜的拓?fù)浣Y(jié)構(gòu)及安全問題，直接將某個社交網(wǎng)絡(luò)平臺作為實(shí)驗(yàn)對象進(jìn)行研究和分析是十分困難的。因此，研究者試圖根據(jù)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)和網(wǎng)絡(luò)所具有的關(guān)鍵特征對社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行模型抽象，從而以拓?fù)淠Ｐ痛嫔缃痪W(wǎng)絡(luò)，通過拓?fù)淠Ｐ驼J(rèn)識社交網(wǎng)絡(luò)的基本特性并進(jìn)行相關(guān)研究。同時，對社交網(wǎng)絡(luò)拓?fù)浣５难芯坑欣谏羁汤斫馊祟愋畔⒔涣鞯倪^程。

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

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

本研究在綜合考慮信息傳遞的有向特性和信息傳遞的強(qiáng)度以及頻率的基礎(chǔ)上，結(jié)合信息傳播所遵循的規(guī)律模擬信息傳遞的動態(tài)過程，通過構(gòu)造加權(quán)有向拓?fù)淠Ｐ鸵愿玫胤抡嫔缃痪W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

2 信息傳播的特點(diǎn)

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

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

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

3 拓?fù)淠Ｐ?/h2>

3.1 模型簡介

本研究在考慮了社交網(wǎng)絡(luò)中信息傳播的有向性和強(qiáng)度的基礎(chǔ)上提出了一種加權(quán)有向拓?fù)淠Ｐ汀Ｔ谒鶚?gòu)建的拓?fù)淠Ｐ椭?，每個節(jié)點(diǎn)代表社交網(wǎng)絡(luò)中的一個用戶，節(jié)點(diǎn)間的有向邊表示這2個節(jié)點(diǎn)所代表的用戶之間存在信息傳遞，而邊的權(quán)值反映的則是2個節(jié)點(diǎn)間信息傳遞的強(qiáng)度或頻率。節(jié)點(diǎn)間有向邊的權(quán)值越大，表明2個節(jié)點(diǎn)間信息傳遞的強(qiáng)度或頻率越大。模型中的節(jié)點(diǎn)可能是信息的接收者，也可能是信息的傳遞者，或者兼具這2種角色。

在描述本文構(gòu)建拓?fù)淠Ｐ偷木唧w過程之前，先介紹模型中用到的如下術(shù)語。

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

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

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

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

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

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

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

3.2 模型構(gòu)建過程

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

基于信息傳播的社交網(wǎng)絡(luò)拓?fù)淠Ｐ偷臉?gòu)建過程包括以下步驟。

1) 初始化

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

② 設(shè)定網(wǎng)絡(luò)中新增邊的權(quán)值都為1。

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

2) 模型生長演化

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

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

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

④ 返回步驟②。

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

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

3.3 模型描述與分析

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

圖1 一個時間步內(nèi)構(gòu)建模型的流程

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

為了驗(yàn)證所構(gòu)建的網(wǎng)絡(luò)模型的有效性，本文利用多個評估參數(shù)對所生成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析。在仿真實(shí)驗(yàn)中，設(shè)定初始網(wǎng)絡(luò)規(guī)模n0=5，最后生成的網(wǎng)絡(luò)規(guī)模為N=5 000。

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

圖2 不同δ所對應(yīng)的節(jié)點(diǎn)度分布情況

在以下的仿真實(shí)驗(yàn)分析中，本文不再贅述不同δ值對網(wǎng)絡(luò)拓?fù)鋵傩缘挠绊?，而是設(shè)定δ=3。

4.1 節(jié)點(diǎn)度分布

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

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

4.2 節(jié)點(diǎn)勢分布

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

4.3 度—勢相關(guān)性

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

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

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

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

圖5 節(jié)點(diǎn)度勢相關(guān)性

4.4 聚集特性

隨著對網(wǎng)絡(luò)拓?fù)涞倪M(jìn)一步研究，人們發(fā)現(xiàn)僅用節(jié)點(diǎn)度的分布來刻畫網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是遠(yuǎn)遠(yuǎn)不夠的，滿足同樣冪律分布的網(wǎng)絡(luò)完全可以呈現(xiàn)截然不同的拓?fù)浣Y(jié)構(gòu)。在冪律分布特性的基礎(chǔ)上，人們開始研究網(wǎng)絡(luò)拓?fù)渲写嬖诘木奂匦?。聚集特性是反映網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)聯(lián)性[16]的特性之一，并通過計算網(wǎng)絡(luò)的聚集系數(shù)來反映網(wǎng)絡(luò)的聚集特性。常用的計算無向圖的聚集系數(shù)的公式為

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

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

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

4.5 網(wǎng)絡(luò)層次性

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

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

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

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

圖7 節(jié)點(diǎn)核數(shù)與度數(shù)的關(guān)系

4.6 網(wǎng)絡(luò)異質(zhì)性

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

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

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

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

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

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

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

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

5 結(jié)束語

本文探究了信息在人際網(wǎng)絡(luò)中的傳播特點(diǎn)，基于信息傳遞的有向特性，通過構(gòu)造加權(quán)的有向拓?fù)淠Ｐ湍M了信息傳遞的動態(tài)性，更好地仿真了社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。利用該模型構(gòu)建了社交網(wǎng)絡(luò)拓?fù)?，從度、勢分布、度—勢相關(guān)性、網(wǎng)絡(luò)聚集特性、網(wǎng)絡(luò)層次性和網(wǎng)絡(luò)異質(zhì)性等方面對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行了分析。結(jié)果表明所生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的度、勢分布以及度—勢相關(guān)性具有明顯的冪律特性。同時，網(wǎng)絡(luò)拓?fù)涞木垲愊禂?shù)、核數(shù)和基尼系數(shù)均表明該模型能夠較好地體現(xiàn)社交網(wǎng)絡(luò)的聚集特性、層次性和異質(zhì)性。綜上所述，本文所構(gòu)建的網(wǎng)絡(luò)模型能夠正確地體現(xiàn)實(shí)際人際關(guān)系網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

[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表示）實(shí)際上是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)絡(luò)蠕蟲仿真建模研究[J]. 計算機(jī)學(xué)報，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)絡(luò)拓?fù)浣J].軟件學(xué)報，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] 王林，戴冠中. 復(fù)雜網(wǎng)絡(luò)的Scale-free性、Scale-free 現(xiàn)象及其控制[M].北京∶科學(xué)出版社，2009.WANG L, DAI G Z. Scale-free Property, Scale-Free Phenomenon and Their Control in Complex Networks[M]. Beijing∶ Science Press, 2009.

猜你喜歡

信息模型

一半模型

童話王國·奇妙邏輯推理(2024年5期)2024-06-19 16:03:38

重要模型『一線三等角』

中學(xué)生數(shù)理化·七年級數(shù)學(xué)人教版(2020年10期)2020-11-26 08:24:50

重尾非線性自回歸模型自加權(quán)M-估計的漸近分布

數(shù)學(xué)物理學(xué)報(2020年2期)2020-06-02 11:29:24

訂閱信息

中華手工(2017年2期)2017-06-06 23:00:31

3D打印中的模型分割與打包

光學(xué)精密工程(2016年6期)2016-11-07 09:07:19

FLUKA幾何模型到CAD幾何模型轉(zhuǎn)換方法初步研究

核科學(xué)與工程(2015年4期)2015-09-26 11:59:03

展會信息

中外會展(2014年4期)2014-11-27 07:46:46

一個相似模型的應(yīng)用

中學(xué)數(shù)學(xué)雜志(初中版)(2006年1期)2006-12-29 00:00:00

信息

建筑創(chuàng)作(2001年3期)2001-08-22 18:48:14

健康信息

祝您健康(1987年3期)1987-12-30 09:52:32

通信學(xué)報2013年4期

通信學(xué)報的其它文章

一類密碼函數(shù)的構(gòu)造與分析

基于拍賣的P2P內(nèi)容分發(fā)網(wǎng)絡(luò)帶寬分配機(jī)制

對一種混合結(jié)構(gòu)洋蔥路由方案的密碼學(xué)分析

基于預(yù)測的機(jī)會式網(wǎng)絡(luò)編碼

融合時間戳和同態(tài)簽名的安全網(wǎng)絡(luò)編碼方法