一種基于節點影響力的信息傳播概率算法

張 永，和 凱

蘭州理工大學 計算機與通信學院，蘭州 730050

1 引言

社交網絡服務SNS（Social Network Service）近年來發展迅速，其憑借網絡的強大連通力將人們的社交范圍從現實的人際關系擴展到虛擬的網絡中來。通過即時聊天工具、微博、博客、網絡社區等網絡應用將人們的社交范圍逐步擴大，最終形成一個人與人關聯的巨大的復雜網絡。Facebook是目前世界上最大的在線社交網絡，目前已擁有超過22億的總用戶，并據Facebook預測到2030年用戶總數將會達50億人。社交網絡不但具有互聯網絡的物理特性，還包含了人際關系的社交特性，是一個典型的復雜網絡，其規模及影響范圍正在不斷擴大。

針對社交網絡上的信息傳播問題已有一定的研究成果，如謠言傳播問題[1-3]、社交網絡中的信息轉發預測[4-6]、信息傳播的模型研究[7-11]等，其中用戶影響力問題[12-20]一直是一個熱點。由于社交網絡的復雜特性，影響信息傳播的因素非常多，要提取所有對信息傳播有影響的特征不現實，過多的特征會使得模型復雜度過高。在上述研究問題中，無論是謠言傳播與轉發預測，還是構造信息傳播模型，信息源節點的權威性這一特征會對信息的傳播結果有重要的影響。因此量化信息源節點的權威性，對精確描述信息傳播的過程有重要意義。其中文獻[13]利用網絡拓撲尋找重要節點，文獻[19]則研究了在有社區結構的網絡中如何尋找重要節點。

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

2 基于節點影響力的信息傳播概率

2.1 節點影響力問題

社交網絡上影響力的研究是社交計算的重要內容，找出有影響力的節點在社會輿論導向、商業營銷、謠言識別以及專家發現等問題上都有重要意義。目前對于如何確定一個社交網絡用戶的影響力有很多的研究，其方法大致可以歸結為兩類：基于網絡拓撲的方法與基于用戶行為的方法。其中基于網絡拓撲的影響力算法相比基于用戶行為的算法更加簡單且復雜度低，常用的有基于節點度（Degree Centrality）、基于最短路徑的介數中心度（Betweenness Centrality）、緊密中心度（Closeness Centrality）、基于隨機游走的特征向量中心度等算法。

確定節點的影響力問題，類似于PageRank算法對網頁排名的問題，需要對每一個節點確定影響力。針對大規模社交網絡而言，傳統的節點影響力度量指標效果均不理想。比如用度中心度來衡量節點影響力的效果很差，而介數中心度與緊密中心度雖然效果較好，但是時間復雜度高達O(n3)，性能無法接受。

節點ui的度中心度以Ck(ui)表示：

節點ui的介數中心度CB用以衡量網絡中包含節點ui的任意兩個節點間的最短路徑的條數，占所有最短路徑條數的比例大小。它可以較好地描述節點ui在網絡中的中心性，即對其他節點的影響力大小，以CB(ui)表示：

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

節點ui的緊密中心度CC用以衡量節點ui到網絡中其他節點的距離之和，即如果節點ui發出一條信息，需要多久能傳播到所有能夠到達的節點。

其中，dG=(ui,t)是節點v到節點t 的距離。

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

圖1 三種不同情況下的信息源節點

圖2 三種不同情況下的信息源節點影響力比較

文獻[7]中的方法考慮到了圖1（b）中的這種情況，如果一個節點的鄰居節點或鄰居節點的鄰居節點是影響力很大的節點，即沿著網絡拓撲向外傳播2層時，若這個信息源節點周圍有重要節點與之相連，那么這個節點因此影響力也會比較大。但是考慮到圖1（c）的情況，也許在一個節點向外傳播3層或4層就會有許多重要節點，那么上述的各種方法便不能反映出這些重要節點對信息源節點影響力的作用。

2.2 基于節點影響力的傳播概率算法

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

從所求節點v出發，設置隨機游走器數量為N，游走路徑長度為L。則隨機游走器Ni的一次長度為L的隨機游走所帶來的權重為：

其中，本文N的取值根據計算量要求可靈活設置，LNi為隨機游走器Ni在長度L的游走路徑上的所有節點的集合。Cv′為節點v′的權重值，計算公式如下：

其中，Γ(v′)為節點v′的最近鄰居節點集合，Q(u)的計算公式為：

其中，Γ(u)為節點u的最近鄰居節點集合，degree為節點z的度。然后將所有隨機游走器帶來的權值求平均，即得最終節點的影響力評分，表示為：

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

以圖3為例解釋上述影響力算法。節點1為信息源節點，假設有2個隨機游走器，游走到了2條路徑，分別是LN1=(1,3,6),LN2=(1,12,13)。節點1的影響力評分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 隨機游走示例圖

3 實驗仿真

3.1 數據描述

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

表1 網絡參數

首先可以看到圖4所示的四種社交網絡均很好地服從了冪率分布，符合典型社交網絡的分布特點。其中Twitter的聚類系數相對較大，為同配性網絡，MSN Space、NetsScience、Twitter與新浪微博為異配性網絡。需要注意的是Twitter與新浪微博中存在權威節點的現象相對更加明顯，可以看到大量節點分布在103量級附近，而MSN Space與NetsScience中權威節點則更多分布在102量級附近。在圖4（d）中可以看到，在度2 000的位置有一個明顯的尾部上升趨勢，這是因為新浪微博本身限制最大關注2 000人，在節點度數達到2 000后，便不能再增長。

3.2 傳播模型及傳播規則

SIR傳染病模型可將社交網絡中信息的傳播過程描述如下：某幾個節點首先發出一條信息，成為初始信息源節點，這些處于傳播信息狀態的節點為感染狀態（Infected，I），其余暫時未接觸到這條信息的節點為易感染狀態（Susceptible，S）。這些處于感染狀態節點的直接鄰居節點會接收到信息，并以一定的概率傳播這條信息，由易感染狀態變為感染狀態，這個概率就是上述提到信息的初始傳播概率。而處于感染狀態節點不會一直處于感染狀態，它們會在一定時間后，結束傳播過程，轉變為免疫狀態（Recovered，R），不再傳播該信息。SIR模型可用下列微分方程組描述：

圖4 各網絡的度分布

表2 各網絡中影響力前五的節點

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

3.3 實驗模擬

實驗首先通過對比已有的節點權威性度量單位：度中心度、介數中心度、緊密中心度來確定本文影響力評分Score計算方法的有效性。最后對比了使用基于影響力算法的傳播概率，與使用固定傳播概率的最終傳播結果的差異。

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

因為Score的計算方法是基于隨機游走的，而隨機游走本身帶有一定的不確定性，所以為確保實驗結果的穩定性，本文在隨機游走器的數量分別設為degree(e)×10、degree(e)×50、degree(e)×100的情況下對每個網絡上的Score評分最大的節點進行了10次評分。實驗結果表明，在degree(e)×100的情況下，隨機游走的結果能夠達到比較穩定的狀態，特別是針對權威節點的評分更加穩定。如圖5所示，橫軸t為實驗輪次，縱軸為Score評分。隨著隨機游走器數量的增加，基于隨機游走的方法的實驗結果是越來越穩定的，所以Score算法應具有足夠的健壯性。

針對上述結果，本文根據以往研究，采取固定傳播概率PSI=0.2進行輪次t=15的傳播仿真。最終感染比率I(t)分別與表2中的四種指標比較其關聯性，繪制如圖6與圖7所示的關系圖。好的影響力指標應當在影響力增大的同時，使最終感染人數增大。可以在圖6與圖7中看到，在四種網絡中緊密中心度的表現相對較好，特別是在MSN Space與NetsScience中，緊密中心度的結果與最終感染人數比率有很強的正相關性，在Twitter與新浪微博中的相關性相對較小。這可能是因為相比MSN Space與NetsScience，Twitter與新浪微博這類社交網絡的社交性更強，網絡更加復雜。人們在這種網絡上傳播信息會受到更多種因素的影響，如是否是熱點話題，是否含有圖片與超鏈接等因素都會影響最終的傳播結果，所以信息源節點對權威性這一因素的作用可能會被稀釋。在MSN Space與NetsScience網絡中，Score值的效果雖不如緊密中心度，但明顯優于度中心度與介數中心度。而在Twitter網絡中緊密中心度表現出一定的關聯性，其余指標表現結果均不理想。在新浪微博中，Score值略優于其他三種指標。

圖5 Score評分的穩定性示意圖

圖6 MSN Space與NetsScience上最終感染比率與各影響力指標間的關系

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

圖7 Twitter與新浪微博上最終感染比率與各影響力指標間的關系

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

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

4 結束語

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

圖8 各權威節點的最終感染比率

圖9 固定傳播概率對比基于節點影響力的傳播概率

本文重點是在模擬傳播開始之前，根據節點本身屬性確定一個合適的初始傳播概率，代替以往研究中人為設定的固定概率。應當明確的是，在實際信息傳播過程中，傳播概率會受到很多因素的影響，如會受到周圍權威節點，或當前輿論導向的影響，這些在傳播過程中動態的影響因素將會是日后的研究方向。

：

[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]顧亦然，夏玲玲.在線社交網絡中謠言的傳播與抑制[J].物理學報，2012，61（23）.

[3]王輝，韓江洪，鄧林，等.基于移動社交網絡的謠言傳播動力學研究[J].物理學報，2013，62（11）.

[4]曹玖新，吳江林，石偉，等.新浪微博網信息傳播分析與預測[J].計算機學報，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]張彥超，劉云，張海峰，等.基于在線社交網絡的信息傳播模型[J].物理學報，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]王金龍，劉方愛，朱振方.一種基于用戶相對權重的在線社交網絡信息傳播模型[J].物理學報，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]唐朝生.在線社交網絡信息傳播建模及轉發預測研究[D].河北秦皇島：燕山大學，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）.