張 永，和 凱

蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，蘭州 730050

1 引言

社交網(wǎng)絡(luò)服務(wù)SNS（Social Network Service）近年來(lái)發(fā)展迅速，其憑借網(wǎng)絡(luò)的強(qiáng)大連通力將人們的社交范圍從現(xiàn)實(shí)的人際關(guān)系擴(kuò)展到虛擬的網(wǎng)絡(luò)中來(lái)。通過(guò)即時(shí)聊天工具、微博、博客、網(wǎng)絡(luò)社區(qū)等網(wǎng)絡(luò)應(yīng)用將人們的社交范圍逐步擴(kuò)大，最終形成一個(gè)人與人關(guān)聯(lián)的巨大的復(fù)雜網(wǎng)絡(luò)。Facebook是目前世界上最大的在線社交網(wǎng)絡(luò)，目前已擁有超過(guò)22億的總用戶，并據(jù)Facebook預(yù)測(cè)到2030年用戶總數(shù)將會(huì)達(dá)50億人。社交網(wǎng)絡(luò)不但具有互聯(lián)網(wǎng)絡(luò)的物理特性，還包含了人際關(guān)系的社交特性，是一個(gè)典型的復(fù)雜網(wǎng)絡(luò)，其規(guī)模及影響范圍正在不斷擴(kuò)大。

針對(duì)社交網(wǎng)絡(luò)上的信息傳播問(wèn)題已有一定的研究成果，如謠言傳播問(wèn)題[1-3]、社交網(wǎng)絡(luò)中的信息轉(zhuǎn)發(fā)預(yù)測(cè)[4-6]、信息傳播的模型研究[7-11]等，其中用戶影響力問(wèn)題[12-20]一直是一個(gè)熱點(diǎn)。由于社交網(wǎng)絡(luò)的復(fù)雜特性，影響信息傳播的因素非常多，要提取所有對(duì)信息傳播有影響的特征不現(xiàn)實(shí)，過(guò)多的特征會(huì)使得模型復(fù)雜度過(guò)高。在上述研究問(wèn)題中，無(wú)論是謠言傳播與轉(zhuǎn)發(fā)預(yù)測(cè)，還是構(gòu)造信息傳播模型，信息源節(jié)點(diǎn)的權(quán)威性這一特征會(huì)對(duì)信息的傳播結(jié)果有重要的影響。因此量化信息源節(jié)點(diǎn)的權(quán)威性，對(duì)精確描述信息傳播的過(guò)程有重要意義。其中文獻(xiàn)[13]利用網(wǎng)絡(luò)拓?fù)鋵ふ抑匾?jié)點(diǎn)，文獻(xiàn)[19]則研究了在有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)中如何尋找重要節(jié)點(diǎn)。

本文主要解決的問(wèn)題是如何通過(guò)衡量信息源節(jié)點(diǎn)的影響力來(lái)確定一條信息的初始傳播概率。本文的研究重點(diǎn)是在實(shí)際傳播開(kāi)始之前給出一個(gè)明確的傳播概率，取代以往研究中根據(jù)經(jīng)驗(yàn)設(shè)定的固定值，而不考慮在傳播過(guò)程中，由于輿論導(dǎo)向，人際關(guān)系的相互影響等因素而引起的動(dòng)態(tài)傳播狀態(tài)變化。本文參考了基于隨機(jī)游走的知識(shí)圖譜問(wèn)題的解決方案[21-22]，提出一種基于節(jié)點(diǎn)影響力的初始傳播概率計(jì)算方法。實(shí)驗(yàn)以SIR傳染病模型[23]為信息傳播基礎(chǔ)模型，首先證明節(jié)點(diǎn)影響力對(duì)傳播結(jié)果有重要影響，其次證明了基于影響力的算法的有效性，最后對(duì)比了基于節(jié)點(diǎn)影響力的信息傳播概率與固定傳播概率在傳播過(guò)程中的差異。信息傳播概率可以為預(yù)測(cè)信息傳播規(guī)模、分析信息傳播特點(diǎn)、挖掘輿論導(dǎo)向等問(wèn)題提供一定的依據(jù)。

2 基于節(jié)點(diǎn)影響力的信息傳播概率

2.1 節(jié)點(diǎn)影響力問(wèn)題

社交網(wǎng)絡(luò)上影響力的研究是社交計(jì)算的重要內(nèi)容，找出有影響力的節(jié)點(diǎn)在社會(huì)輿論導(dǎo)向、商業(yè)營(yíng)銷、謠言識(shí)別以及專家發(fā)現(xiàn)等問(wèn)題上都有重要意義。目前對(duì)于如何確定一個(gè)社交網(wǎng)絡(luò)用戶的影響力有很多的研究，其方法大致可以歸結(jié)為兩類：基于網(wǎng)絡(luò)拓?fù)涞姆椒ㄅc基于用戶行為的方法。其中基于網(wǎng)絡(luò)拓?fù)涞挠绊懥λ惴ㄏ啾然谟脩粜袨榈乃惴ǜ雍?jiǎn)單且復(fù)雜度低，常用的有基于節(jié)點(diǎn)度（Degree Centrality）、基于最短路徑的介數(shù)中心度（Betweenness Centrality）、緊密中心度（Closeness Centrality）、基于隨機(jī)游走的特征向量中心度等算法。

確定節(jié)點(diǎn)的影響力問(wèn)題，類似于PageRank算法對(duì)網(wǎng)頁(yè)排名的問(wèn)題，需要對(duì)每一個(gè)節(jié)點(diǎn)確定影響力。針對(duì)大規(guī)模社交網(wǎng)絡(luò)而言，傳統(tǒng)的節(jié)點(diǎn)影響力度量指標(biāo)效果均不理想。比如用度中心度來(lái)衡量節(jié)點(diǎn)影響力的效果很差，而介數(shù)中心度與緊密中心度雖然效果較好，但是時(shí)間復(fù)雜度高達(dá)O(n3)，性能無(wú)法接受。

節(jié)點(diǎn)ui的度中心度以Ck(ui)表示：

節(jié)點(diǎn)ui的介數(shù)中心度CB用以衡量網(wǎng)絡(luò)中包含節(jié)點(diǎn)ui的任意兩個(gè)節(jié)點(diǎn)間的最短路徑的條數(shù)，占所有最短路徑條數(shù)的比例大小。它可以較好地描述節(jié)點(diǎn)ui在網(wǎng)絡(luò)中的中心性，即對(duì)其他節(jié)點(diǎn)的影響力大小，以CB(ui)表示：

其中，σst是節(jié)點(diǎn)s與節(jié)點(diǎn)t間所有最短路徑的條數(shù)，而σst(v)則是包含節(jié)點(diǎn)ui的s與t間最短路徑的條數(shù)。

節(jié)點(diǎn)ui的緊密中心度CC用以衡量節(jié)點(diǎn)ui到網(wǎng)絡(luò)中其他節(jié)點(diǎn)的距離之和，即如果節(jié)點(diǎn)ui發(fā)出一條信息，需要多久能傳播到所有能夠到達(dá)的節(jié)點(diǎn)。

其中，dG=(ui,t)是節(jié)點(diǎn)v到節(jié)點(diǎn)t 的距離。

但是，在社交網(wǎng)絡(luò)中，有一種如圖1所示的常見(jiàn)現(xiàn)象。在圖1（a）中，中心節(jié)點(diǎn)雖然本身具有很大影響力，但它的鄰居節(jié)點(diǎn)卻都是小影響力節(jié)點(diǎn)。而圖1（b）中，中心節(jié)點(diǎn)雖然本身影響力小，但它有4個(gè)影響力大的鄰居。這種情況會(huì)使得圖1（b）的中心節(jié)點(diǎn)比圖1（a）的中心節(jié)點(diǎn)擁有更大的影響力，而圖1（b）中心節(jié)點(diǎn)的度卻比圖1（a）中心節(jié)點(diǎn)的度小。進(jìn)一步的，本文發(fā)現(xiàn)如果有圖1（c）這樣的結(jié)構(gòu)，在中心節(jié)點(diǎn)本身度很小的情況下，在它的附近有幾個(gè)權(quán)威節(jié)點(diǎn)，信息可能需要經(jīng)過(guò)一次傳播，或經(jīng)過(guò)較少的兩次或三次的傳播后，能到達(dá)這幾個(gè)重要的節(jié)點(diǎn)。在這種情況下，如圖1（c）這樣的中心節(jié)點(diǎn)仍會(huì)擁有較大的影響力。圖2為以類似圖1（a）、圖1（b）、圖1（c）的中心節(jié)點(diǎn)為信息源節(jié)點(diǎn)，在SIR模型上的傳播結(jié)果，橫軸t為傳播輪次，縱軸為最大感染率。在圖2中可以看到度數(shù)最大的中心節(jié)點(diǎn)影響力卻最小，這表明簡(jiǎn)單的節(jié)點(diǎn)影響力度量單位不能很好反映出潛在重要節(jié)點(diǎn)所帶來(lái)的影響力變化。

圖1 三種不同情況下的信息源節(jié)點(diǎn)

圖2 三種不同情況下的信息源節(jié)點(diǎn)影響力比較

文獻(xiàn)[7]中的方法考慮到了圖1（b）中的這種情況，如果一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)或鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是影響力很大的節(jié)點(diǎn)，即沿著網(wǎng)絡(luò)拓?fù)湎蛲鈧鞑?層時(shí)，若這個(gè)信息源節(jié)點(diǎn)周圍有重要節(jié)點(diǎn)與之相連，那么這個(gè)節(jié)點(diǎn)因此影響力也會(huì)比較大。但是考慮到圖1（c）的情況，也許在一個(gè)節(jié)點(diǎn)向外傳播3層或4層就會(huì)有許多重要節(jié)點(diǎn)，那么上述的各種方法便不能反映出這些重要節(jié)點(diǎn)對(duì)信息源節(jié)點(diǎn)影響力的作用。

2.2 基于節(jié)點(diǎn)影響力的傳播概率算法

本文針對(duì)社交網(wǎng)絡(luò)上的信息傳播特點(diǎn)，用基于隨機(jī)游走的節(jié)點(diǎn)影響力算法來(lái)確定信息傳播概率。其主要思想為：對(duì)于一個(gè)社交網(wǎng)絡(luò)G=(V,E)，其中V為所有頂點(diǎn)的集合，E為所有邊集合，設(shè)置N個(gè)從信息源節(jié)點(diǎn)v出發(fā)隨機(jī)游走器，游走長(zhǎng)度為L(zhǎng)的路徑，計(jì)算每條路徑權(quán)重，最后將沿著信息源節(jié)點(diǎn)出發(fā)游走到的路徑權(quán)重求和，得到信息源節(jié)點(diǎn)的影響力大小，歸一化后設(shè)為信息傳播概率。詳細(xì)算法描述如下。

從所求節(jié)點(diǎn)v出發(fā)，設(shè)置隨機(jī)游走器數(shù)量為N，游走路徑長(zhǎng)度為L(zhǎng)。則隨機(jī)游走器Ni的一次長(zhǎng)度為L(zhǎng)的隨機(jī)游走所帶來(lái)的權(quán)重為：

其中，本文N的取值根據(jù)計(jì)算量要求可靈活設(shè)置，LNi為隨機(jī)游走器Ni在長(zhǎng)度L的游走路徑上的所有節(jié)點(diǎn)的集合。Cv′為節(jié)點(diǎn)v′的權(quán)重值，計(jì)算公式如下：

其中，Γ(v′)為節(jié)點(diǎn)v′的最近鄰居節(jié)點(diǎn)集合，Q(u)的計(jì)算公式為：

其中，Γ(u)為節(jié)點(diǎn)u的最近鄰居節(jié)點(diǎn)集合，degree為節(jié)點(diǎn)z的度。然后將所有隨機(jī)游走器帶來(lái)的權(quán)值求平均，即得最終節(jié)點(diǎn)的影響力評(píng)分，表示為：

其中Nc為設(shè)置的degree(e)×3個(gè)隨機(jī)游走器的集合。最后利用Score的最大與最小值的差將Score值歸一化為傳播概率。

以圖3為例解釋上述影響力算法。節(jié)點(diǎn)1為信息源節(jié)點(diǎn)，假設(shè)有2個(gè)隨機(jī)游走器，游走到了2條路徑，分別是LN1=(1,3,6),LN2=(1,12,13)。節(jié)點(diǎn)1的影響力評(píng)分Score(1)=hN1(1)+hN2(1)=78+43=121。其中有hN1(1)=C(1)+C(3)+C(6)，C(3)=Q(1)+Q(6)，Q(3)=degree(1)+degree(6)，其余同理可得。

圖3 隨機(jī)游走示例圖

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

3.1 數(shù)據(jù)描述

本文實(shí)驗(yàn)中使用四種社交網(wǎng)絡(luò)：MSN Space（MS）、NetsScience（NS，一種科學(xué)家發(fā)表論文的合作關(guān)系網(wǎng)絡(luò)）、Twitter（TW）、新浪微博（XL）。其中實(shí)驗(yàn)所用MS的 數(shù) 據(jù) 取 自 http：//www.cs.bris.ac.uk/～steve/networks/peacockpaper；NS 數(shù)據(jù)取自 http：//www.personal.umich.edu/～mejn/netdata；TW數(shù)據(jù)取自http：//snap.stanford.edu/data/；XL數(shù)據(jù)取自http：//www.nlpir.org/?action-viewnewsitemid-299。假設(shè)這四種網(wǎng)絡(luò)均為無(wú)向無(wú)權(quán)圖，以G=(V,E)表示，其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E表示鏈接V的邊的集合。詳細(xì)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)如表1所示，具體網(wǎng)絡(luò)度分布如圖4所示。

表1 網(wǎng)絡(luò)參數(shù)

首先可以看到圖4所示的四種社交網(wǎng)絡(luò)均很好地服從了冪率分布，符合典型社交網(wǎng)絡(luò)的分布特點(diǎn)。其中Twitter的聚類系數(shù)相對(duì)較大，為同配性網(wǎng)絡(luò)，MSN Space、NetsScience、Twitter與新浪微博為異配性網(wǎng)絡(luò)。需要注意的是Twitter與新浪微博中存在權(quán)威節(jié)點(diǎn)的現(xiàn)象相對(duì)更加明顯，可以看到大量節(jié)點(diǎn)分布在103量級(jí)附近，而MSN Space與NetsScience中權(quán)威節(jié)點(diǎn)則更多分布在102量級(jí)附近。在圖4（d）中可以看到，在度2 000的位置有一個(gè)明顯的尾部上升趨勢(shì)，這是因?yàn)樾吕宋⒉┍旧硐拗谱畲箨P(guān)注2 000人，在節(jié)點(diǎn)度數(shù)達(dá)到2 000后，便不能再增長(zhǎng)。

3.2 傳播模型及傳播規(guī)則

SIR傳染病模型可將社交網(wǎng)絡(luò)中信息的傳播過(guò)程描述如下：某幾個(gè)節(jié)點(diǎn)首先發(fā)出一條信息，成為初始信息源節(jié)點(diǎn)，這些處于傳播信息狀態(tài)的節(jié)點(diǎn)為感染狀態(tài)（Infected，I），其余暫時(shí)未接觸到這條信息的節(jié)點(diǎn)為易感染狀態(tài)（Susceptible，S）。這些處于感染狀態(tài)節(jié)點(diǎn)的直接鄰居節(jié)點(diǎn)會(huì)接收到信息，并以一定的概率傳播這條信息，由易感染狀態(tài)變?yōu)楦腥緺顟B(tài)，這個(gè)概率就是上述提到信息的初始傳播概率。而處于感染狀態(tài)節(jié)點(diǎn)不會(huì)一直處于感染狀態(tài)，它們會(huì)在一定時(shí)間后，結(jié)束傳播過(guò)程，轉(zhuǎn)變?yōu)槊庖郀顟B(tài)（Recovered，R），不再傳播該信息。SIR模型可用下列微分方程組描述：

圖4 各網(wǎng)絡(luò)的度分布

表2 各網(wǎng)絡(luò)中影響力前五的節(jié)點(diǎn)

實(shí)際上使用簡(jiǎn)單的SIR模型不能完全描述社交網(wǎng)絡(luò)中各種復(fù)雜的節(jié)點(diǎn)狀態(tài)，且模型在計(jì)算節(jié)點(diǎn)狀態(tài)的改變概率時(shí)并沒(méi)有考慮到社交網(wǎng)絡(luò)中節(jié)點(diǎn)相互影響的重要特性。針對(duì)此問(wèn)題，文獻(xiàn)[2]，文獻(xiàn)[9]與文獻(xiàn)[11]的研究?jī)?nèi)容主要是在模型信息傳播過(guò)程時(shí)，對(duì)簡(jiǎn)單病毒傳播模型的改進(jìn)。目前主要的改進(jìn)手段為添加新類型的節(jié)點(diǎn)以描述社交網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播狀態(tài)，或設(shè)定一些符合特定社交網(wǎng)絡(luò)中信息的規(guī)則。本文為了保持除初始傳播概率這一影響傳播的因素外，其他影響因素不變，故使用了傳統(tǒng)的SIR模型，以方便對(duì)照實(shí)驗(yàn)結(jié)果。

3.3 實(shí)驗(yàn)?zāi)M

實(shí)驗(yàn)首先通過(guò)對(duì)比已有的節(jié)點(diǎn)權(quán)威性度量單位：度中心度、介數(shù)中心度、緊密中心度來(lái)確定本文影響力評(píng)分Score計(jì)算方法的有效性。最后對(duì)比了使用基于影響力算法的傳播概率，與使用固定傳播概率的最終傳播結(jié)果的差異。

表2為根據(jù)上述指標(biāo)得到影響力最大的前5個(gè)節(jié)點(diǎn)。其中CK表示度中心度的計(jì)算結(jié)果，CB表示介數(shù)中心度的計(jì)算結(jié)果，CC表示緊密中心度的計(jì)算結(jié)果，Score為本文方法的計(jì)算結(jié)果，游走長(zhǎng)度L取值為5，隨機(jī)游走器數(shù)量取值為degree(e)×100。如表2所示，總體來(lái)看本文提出的Score值與度中心度的衡量結(jié)果相似度更大，和介數(shù)中心度與緊密中心度的衡量結(jié)果相似度較小。介數(shù)中心度與緊密中心度的衡量結(jié)果較為相似，因?yàn)檫@兩個(gè)指標(biāo)都是基于最短路徑的，而本文提出的方法采用的是隨機(jī)游走與度中心度結(jié)合的一種方法，因而結(jié)果更接近于度中心度。現(xiàn)今社交網(wǎng)絡(luò)的規(guī)模越來(lái)越大，許多社交網(wǎng)絡(luò)上有數(shù)億個(gè)節(jié)點(diǎn)，即使截取部分網(wǎng)絡(luò)，如同介數(shù)中心度與緊密中心度這樣時(shí)間復(fù)雜度高達(dá)O(n3)的算法仍然是不可接受的。本文Score算法好處在于通過(guò)控制隨機(jī)游走器的數(shù)量與游走的路徑長(zhǎng)度，可以很好地控制算法的時(shí)間消耗，在計(jì)算效率與精確度之間的關(guān)系上具有良好的靈活性。

因?yàn)镾core的計(jì)算方法是基于隨機(jī)游走的，而隨機(jī)游走本身帶有一定的不確定性，所以為確保實(shí)驗(yàn)結(jié)果的穩(wěn)定性，本文在隨機(jī)游走器的數(shù)量分別設(shè)為degree(e)×10、degree(e)×50、degree(e)×100的情況下對(duì)每個(gè)網(wǎng)絡(luò)上的Score評(píng)分最大的節(jié)點(diǎn)進(jìn)行了10次評(píng)分。實(shí)驗(yàn)結(jié)果表明，在degree(e)×100的情況下，隨機(jī)游走的結(jié)果能夠達(dá)到比較穩(wěn)定的狀態(tài)，特別是針對(duì)權(quán)威節(jié)點(diǎn)的評(píng)分更加穩(wěn)定。如圖5所示，橫軸t為實(shí)驗(yàn)輪次，縱軸為Score評(píng)分。隨著隨機(jī)游走器數(shù)量的增加，基于隨機(jī)游走的方法的實(shí)驗(yàn)結(jié)果是越來(lái)越穩(wěn)定的，所以Score算法應(yīng)具有足夠的健壯性。

針對(duì)上述結(jié)果，本文根據(jù)以往研究，采取固定傳播概率PSI=0.2進(jìn)行輪次t=15的傳播仿真。最終感染比率I(t)分別與表2中的四種指標(biāo)比較其關(guān)聯(lián)性，繪制如圖6與圖7所示的關(guān)系圖。好的影響力指標(biāo)應(yīng)當(dāng)在影響力增大的同時(shí)，使最終感染人數(shù)增大?？梢栽趫D6與圖7中看到，在四種網(wǎng)絡(luò)中緊密中心度的表現(xiàn)相對(duì)較好，特別是在MSN Space與NetsScience中，緊密中心度的結(jié)果與最終感染人數(shù)比率有很強(qiáng)的正相關(guān)性，在Twitter與新浪微博中的相關(guān)性相對(duì)較小。這可能是因?yàn)橄啾萂SN Space與NetsScience，Twitter與新浪微博這類社交網(wǎng)絡(luò)的社交性更強(qiáng)，網(wǎng)絡(luò)更加復(fù)雜。人們?cè)谶@種網(wǎng)絡(luò)上傳播信息會(huì)受到更多種因素的影響，如是否是熱點(diǎn)話題，是否含有圖片與超鏈接等因素都會(huì)影響最終的傳播結(jié)果，所以信息源節(jié)點(diǎn)對(duì)權(quán)威性這一因素的作用可能會(huì)被稀釋。在MSN Space與NetsScience網(wǎng)絡(luò)中，Score值的效果雖不如緊密中心度，但明顯優(yōu)于度中心度與介數(shù)中心度。而在Twitter網(wǎng)絡(luò)中緊密中心度表現(xiàn)出一定的關(guān)聯(lián)性，其余指標(biāo)表現(xiàn)結(jié)果均不理想。在新浪微博中，Score值略優(yōu)于其他三種指標(biāo)。

圖5 Score評(píng)分的穩(wěn)定性示意圖

圖6 MSN Space與NetsScience上最終感染比率與各影響力指標(biāo)間的關(guān)系

為了驗(yàn)證Score值的有效性，圖8為在MSN Space、NetsScience、Twitter與新浪微博中以各影響力指標(biāo)排名第一的節(jié)點(diǎn)作為信息源節(jié)點(diǎn)，同樣以固定傳播概率PSI=0.2在SIR模型中傳播10次，得到的最終感染率變化的曲線圖。可以看到在MSN Space中，四種影響力指標(biāo)均排名第一的節(jié)點(diǎn)cjun50在最終感染比率上明顯高于其他節(jié)點(diǎn)，這首先可以說(shuō)明節(jié)點(diǎn)權(quán)重對(duì)信息傳播結(jié)果有明顯的影響，高影響力節(jié)點(diǎn)傳播的信息會(huì)感染更多節(jié)點(diǎn)。其次，可以看到cjun50節(jié)點(diǎn)的最終感染率是明顯高于其他節(jié)點(diǎn)的，由表2所示數(shù)據(jù)可知，Score值將此節(jié)點(diǎn)排名第一，且cjun50的Score值是明顯高于其他節(jié)點(diǎn)的，而其他評(píng)價(jià)值卻相差不大，這顯示出Score值一定的優(yōu)越性。由Score值識(shí)別出的一個(gè)重要節(jié)點(diǎn)chanxiner，與緊密中心度、介數(shù)中心識(shí)別為第二重要節(jié)點(diǎn)的xhzd其最終感染率相近，但其他指標(biāo)卻未識(shí)別出此節(jié)點(diǎn)。在NetsScience網(wǎng)絡(luò)中，由度中心度、緊密中心度與Score識(shí)別為排名第一的AKIMITSU，J，它的最終感染率的確較高，而介數(shù)中心度識(shí)別出的排名第一的節(jié)點(diǎn)AFFLECK，I的最終感染率也比較高，這說(shuō)明這四種指標(biāo)NetsScience網(wǎng)絡(luò)中均有良好的表現(xiàn)。其中Score值將AEPPLI，G節(jié)點(diǎn)排在第二位，而度中心度與介數(shù)中心度也識(shí)別出了這個(gè)重要節(jié)點(diǎn)，且Score排名前五個(gè)重要節(jié)點(diǎn)中，有三個(gè)節(jié)點(diǎn)由其他評(píng)價(jià)指標(biāo)確定為排名前五的重要節(jié)點(diǎn)，說(shuō)明這些節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)有一定程度的相似性。在Twitter網(wǎng)絡(luò)中，首先可以看到由各個(gè)評(píng)價(jià)指標(biāo)選出的影響力排名前五的節(jié)點(diǎn)差異很大，與圖8數(shù)據(jù)所示結(jié)論一致，各個(gè)評(píng)價(jià)指標(biāo)的表現(xiàn)均不穩(wěn)定，差異較大。感染率最高的節(jié)點(diǎn)7861312由度中心度與介數(shù)中心度識(shí)別出，但得分不高。在新浪微博中，感染率較高的10413節(jié)點(diǎn)，除了緊密中心度為將其排名前五外，其他三種指標(biāo)均識(shí)別出了這個(gè)重要節(jié)點(diǎn)?？偟膩?lái)說(shuō)，Score評(píng)分與其他影響力指標(biāo)選擇出的重要節(jié)點(diǎn)，對(duì)信息傳播的結(jié)果均有一定影響，證明Score值在評(píng)價(jià)節(jié)點(diǎn)影響力方面的有效性。且各指標(biāo)在不同的網(wǎng)絡(luò)上，性能好壞有差異。

圖7 Twitter與新浪微博上最終感染比率與各影響力指標(biāo)間的關(guān)系

表3 對(duì)比固定傳播概率與基于影響力的傳播概率

實(shí)驗(yàn)最后，在上述四種網(wǎng)絡(luò)上，任選一個(gè)節(jié)點(diǎn)為信息源節(jié)點(diǎn)，分別采用由本文提出的基于影響力的信息傳播概率P(v)，與固定概率Fixed=0.2進(jìn)行傳播模擬。具體選取情況見(jiàn)表3。實(shí)驗(yàn)結(jié)果如圖9所示，橫軸t為傳播輪次，縱軸為感染節(jié)點(diǎn)比例?？梢悦黠@看到，不同的初始傳播概率對(duì)信息的傳播過(guò)程影響極大。對(duì)于不同的初始傳播概率，曲線斜率代表的信息傳播的速度不一致，曲線頂點(diǎn)代表的最大信息傳播范圍不一致，達(dá)到信息傳播的最大范圍時(shí)間也不一致，同時(shí)感染節(jié)點(diǎn)比例再次歸零，即信息消亡的時(shí)間也不一致，尤其在NetScience網(wǎng)絡(luò)上差異極大。這些結(jié)果證明了在以往的研究中，所有傳播過(guò)程均指定固定概率，忽略不同信息源節(jié)點(diǎn)的差異，是極為不準(zhǔn)確的。根據(jù)節(jié)點(diǎn)的影響力，給信息源節(jié)點(diǎn)不同的傳播概率，相比人為設(shè)定固定的傳播概率更為合理。

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

在以往的研究中，研究者的研究重點(diǎn)往往在于信息的傳播過(guò)程中，而忽略在傳播開(kāi)始之前的環(huán)境影響。本文提出了一種基于節(jié)點(diǎn)影響力的信息傳播概率算法，用以確定不同信息源節(jié)點(diǎn)的初始傳播概率。實(shí)驗(yàn)通過(guò)在SIR模型上模擬信息傳播過(guò)程，通過(guò)驗(yàn)證影響力算法的有效性，證明計(jì)算后的傳播概率更加合理。影響力算法不僅可以用于計(jì)算信息傳播概率，同樣在謠言傳播、專家發(fā)現(xiàn)、傳染病控制等方面均有重要價(jià)值。

圖8 各權(quán)威節(jié)點(diǎn)的最終感染比率

圖9 固定傳播概率對(duì)比基于節(jié)點(diǎn)影響力的傳播概率

本文重點(diǎn)是在模擬傳播開(kāi)始之前，根據(jù)節(jié)點(diǎn)本身屬性確定一個(gè)合適的初始傳播概率，代替以往研究中人為設(shè)定的固定概率。應(yīng)當(dāng)明確的是，在實(shí)際信息傳播過(guò)程中，傳播概率會(huì)受到很多因素的影響，如會(huì)受到周圍權(quán)威節(jié)點(diǎn)，或當(dāng)前輿論導(dǎo)向的影響，這些在傳播過(guò)程中動(dòng)態(tài)的影響因素將會(huì)是日后的研究方向。

：

[1]Zhao L J，Wang J J，Chen Y C，et al.SIHR rumor spreading model in social networks[J].Physica A，2012，391（7）：2444-2453.

[2]顧亦然，夏玲玲.在線社交網(wǎng)絡(luò)中謠言的傳播與抑制[J].物理學(xué)報(bào)，2012，61（23）.

[3]王輝，韓江洪，鄧林，等.基于移動(dòng)社交網(wǎng)絡(luò)的謠言傳播動(dòng)力學(xué)研究[J].物理學(xué)報(bào)，2013，62（11）.

[4]曹玖新，吳江林，石偉，等.新浪微博網(wǎng)信息傳播分析與預(yù)測(cè)[J].計(jì)算機(jī)學(xué)報(bào)，2014（4）.

[5]Hong L，Dan O，Davison B D.Predicting popular messages in Twitter[C]//Proceedings of the 20th International Conference Companion on World Wide Web，2011.

[6]Dickens L，Molloy I，Lobo J.Learning stochastic models of information flow[C]//IEEE 28th International Conference on Data Engineering（ICDE），2012.

[7]張彥超，劉云，張海峰，等.基于在線社交網(wǎng)絡(luò)的信息傳播模型[J].物理學(xué)報(bào)，2011，60（5）.

[8]Yang J，Leskovec J.Modeling information diffusion in implicit networks[C]//Proceedings of the 2010 IEEE International Conference on Data Mining，Sydney，Australia，2010：599-608.

[9]王金龍，劉方愛(ài)，朱振方.一種基于用戶相對(duì)權(quán)重的在線社交網(wǎng)絡(luò)信息傳播模型[J].物理學(xué)報(bào)，2015，64（5）.

[10]Lü L，Chen D B，Zhou T.Small world yields the most effective information spreading[J].New Journal of Physics，2011，12.

[11]唐朝生.在線社交網(wǎng)絡(luò)信息傳播建模及轉(zhuǎn)發(fā)預(yù)測(cè)研究[D].河北秦皇島：燕山大學(xué)，2014.

[12]Kimura M，Saito K，Nakano R，et al.Extracting influential nodes on a social network for information diffusion[J].Data Min Knowl Disc，2010，20：70-97.

[13]Chen D，Lü L，Shang M S，et al.Identifying influential nodes in complex networks[J].Fuel&Energy Abstracts，2012，391（4）：1777-1787.

[14]Kitsak M，Gallos L K，Havlin S，et al.Identification of influentialspreadersin complex networks[J].Nature Physics，2010，6（11）：888-893.

[15]Batagelj V，Zaversnik M.An O(m)algorithm for cores decomposition of networks[J].Advances in Data Analysis and Classification，2011，5（2）：129-145.

[16]Hou B，Yao Y，Liao D.Identifying all-around nodes for spreading dynamics in complex networks[J].Physics A：Statistical Mechanics and Its Applications，2012，391（15）：4012-4017.

[17]Hu Q，Gao Y，Ma P，et al.A new approach to identify influential spreaders in complex networks[J].Acta Physica Sinica，2013，62（14）：99-104.

[18]Lü L，Zhang Y C，Chi H Y，et al.Leaders in social networks，the delicious case[J].Plos One，2011，6（6）.

[19]Zhang X，Zhu J，Wang Q，et al.Identifying influential nodes in complex networks with community structure[J].Knowledge-Based Systems，2013，42（2）：74-84.

[20]Wei D，Deng X，Zhang X，et al.Identifying influential nodes in weighted networks based on evidence theory[J].Physica A Statistical Mechanics& Its Applications，2013，392（10）：2564-2575.

[21]Lao N，Cohen W W.Relational retrieval using a combination ofpath-constrained random walks[J].Machine Learning，2010，81（1）：53-67.

[22]Lao N，Cohen W W.Fast query execution for retrieval models based on path-constrained random walks[C]//ACM SIGKDD InternationalConferenceonKnowledge Discovery and Data Mining，2010：881-888.

[23]Moreno Y，Nekovee M，Pacheco A F.Dynamics of rumor spreading in complex networks[J].Physical Review E，2004，69（6）.