群體對個體影響力傳播算法

顧亦然，趙 棟，孟繁榮

（南京郵電大學自動化學院，江蘇 南京 210023）

0 引言

社交網絡興起在一定程度上打破了固化的社會結構，使得社會各階層的領袖、精英和大眾都可以在社交媒體上擁有自己的“麥克風”，扮演著信息制造者、傳播者和接收者的多重角色。信息經由一層一層的信息傳播圈迅速向外傳遞的過程中，逐漸形成不同的群體化行為。

扎利亞·戈維特在一篇關于“群體極端化”的文章中寫到，人們的頭腦總是受周圍群體的影響而出現意見趨同現象。網絡群體作為虛擬網絡社會中的網民，對某一事件或主題表現出的群體行為，已經被多次的真實事件表明，這些群體性行為可以撼動事件的結果。因此，社交網絡的輿情已經從公眾輿論的折射場轉為了引發地、爆發場，成為網絡輿情的重要陣地，對社會活動影響深遠。身處輿論中的普羅大眾們通過各自的影響力相互作用，組織演化，使得在線社交網絡的輿情呈現出多樣化和復雜性[1-3]。

群體行為作為大規模的非正式的行為，往往帶有一定破壞性。如，網絡輿情、社會突發事件、公共危機、網絡攻擊等。因此，有必要針對個體的行為特點和影響力的關聯性進行研究，進一步理解和揭示影響力的作用機制和潛在的機理[4]。

1 研究現狀

近年來，隨著社會中突發輿論事件的不斷增多，關于網絡群體及群體行為的研究備受學界的關注。有很多學者從自然科學和交叉學科的角度建模研究網絡輿論中的個體和群體的社會化影響，試圖深入分析傳播的交互機制。從建模方式上來看，有的模型側重于群體特征的描述，直接建立群體行為的動態演化過程模型；有的模型側重于刻畫個體的交互機制[4]，通過建立個體觀點的更新規則模型，研究宏觀上產生的群體觀點演化現象。Li等[5]對在人類行為中普遍存在的極化現象的機理進行深入研究，并運用閾值理論解釋騷亂暴動等激進群體行為，以及 Web上群體觀點極化與社會認同理論之間的聯系；朱麗萍等[6]認為情緒效價作為社會信息的重要特征，影響著人們對信息的感知與加工，相對于中性刺激，人們對情緒性刺激（正性和負性）的加工更加迅速，表現為對情緒刺激的反應時間縮短，說明情緒刺激能更快地進入認知加工，信息的情緒特征能更快地調動認知資源；劉凱等[7]通過構建結構方程模型計算了互聯網輿情中網民參與心理對參與行為的路徑系數，測定了網民不同輿情參與心理下輿情參與行為的強度，同時對各因素進行了有效分析；Hegselmann R等[3]探討了不同在線論壇用戶參與行為，發現在線論壇用戶之間的關系存在隨機性且用戶之間信任性較弱，用戶對在線參與行為顯示出了強有力的規律。Li N等[6]以人類的信息傳播行為為例做了實證研究，發現在人類的行為中普遍存在冪律特性；Gunjan Verma等[8]認為當出現相斥證據時，有些人的觀點容易受到他人影響而改變其原有觀點；不斷有學者指出等[9-10]指出處于社會網絡結構中的有些人會受到鄰居節點的影響[12]，并證明影響值正比于累計的回報值。Bonzom V基于Ising模型，在無標度網絡結構中，考慮個體的空間位置和人際交往的雙層等級結構，構建了人際交往的觀點形成模型。該模型認為個體對其他個體的影響程度取決于他們的權威度；Gargiulo F等[13]證明了有些人在制定決策時會受歷史選擇與旁人的影響。可見，群體一個很重要的特征就是群體化的影響力。而從影響力的角度來看，上述描述現階段多數都是從個體與個體的角度分析影響力。還鮮有從個體與群體角度來分析研究影響力，也沒有對影響值進行定量分析。因此本文通過研究群體對個體行為的影響力作用，提出了群體對個體的影響力交互模型，并對該算法進行定量分析。

2 相關概念及定義

2.1 K-Shell

Kitask等人認為位于網絡核心位置的節點i即使其度值很小，其對網絡的影響力也很大，相反的，即使節點 j具有很高的度值，但是位于網絡邊緣位置，則其對網絡的影響力并沒有節點i大，基于此提出了K-Shell (K-殼)分解算法，這是一種粗粒化的節點重要性分類方法。它體現了網絡中節點影響力的擴散，類似能量向外一層一層在涌動。

K-Shell分解算法分解步驟如下：假設網絡中不存在度為0的節點，即每個節點度值 k ≥ 1，先將網絡中所有度值為 1的節點剝落，剝落所有度值為 1的節點后，生成的新網絡中會繼續有度值為1的節點，重復之前的步驟，繼續進行剝落度值為1的節點，直到新網絡中所有的節點的度值 k ≥ 2 ，把所有剝落的節點稱為網絡的1-Shell（1-殼）；新網絡中節點的度值有 k ≥ 2 ，同第一步相同，重復剝落度值為2的節點，直到網絡中所有節點的度值 k ≥ 3 ，將這一步剝落的節點稱為網絡的2-Shell。以此類推，進一步得到網絡的3-Shell、4-Shell等更高的Shell層，直到網絡中的所有的節點都被剝落，這樣網絡中的每個節點都有對應的K-Shell值 ks，例如屬于2-Shell的節點，其 ks= 2 ，對于屬于K-Shell層的節點都有度值 k ≥ks。

2.2 貢獻度

網絡可以抽象為節點集 V(Vertex)與連邊集E(Edge)組成的圖 G=(V,E)。通過節點間連邊關系反應網絡情況，在現實網絡中節點對彼此間的影響力是不同的，比如Vi節點是一個影響力很大的節點而Vj節點則是一個影響力較小的節點，Vi對Vj的影響力要高于Vj對Vi的影響力，為了表征這種差異，引入貢獻度[11]這一概念，節點 i對 j的貢獻度定義見公式（1），其中 i和j分別為節點Vi和Vj鄰居節點的集合。

3 群體對個體影響力算法

3.1 親密度

表1 社交關系親密度的符號和含義Tab.1 The symbol and meaning of social relationship intimacy

3.2 群體對個體的影響力

上文中節點的 Ks值的大小表示網絡中該節點所在的核心位置，既影響力傳播深度。貢獻度表述節點某屬性對各鄰居節點的貢獻情況。綜合考慮節點對全網信息的傳播影響力，將相鄰個體間影響力定義如下。節點iv對節點jv的影響力，為節點iv的K-Shell值、節點iv對節點jv的貢獻度、節點iv對節點jv的親密度因子三者的乘積：

定義 1：群體由微博、微信最新數據分析，在線社交網絡兩節點間的平均距離為 3，因此本文在做群體對個體影響力分析時，計算僅考慮路徑距離為3以內的所有節點群體。

節點在群體中受到的平均影響力定義：首先本文使用廣度優先搜索算法，可以尋找到網絡中，某節點iv三步之內的所有節點集合iV（實驗表明兩步范圍太小不夠全面，四步開始對結果影響很小，故這里選擇了三步）。由公式（2）可以計算出iv對集合內所有節點的影響力，再進行求和記為節點iv對群體的影響力iGF 。其次，本文計算出網絡中 m個節點對群體的影響力之和，再求平均數記為 i節點在群體中受到的平均影響力大小：

群體對個體影響力算法：假設要求群體對目標節點 t的影響力大小，考慮到每個群體對個體造成最直接影響的因素，往往是群體內具有群體觀點，且與目標個體有直接交際關系的節點，對目標節點帶來的影響。因此本文使用廣度優先搜索算法找出群體內與節點tv相連一步之內的所有節點（m節點，l節點…），然后用群體影響力與相鄰個體影響力的乘積，再求和記為整個群體對個體的影響力：

3.3 基于影響力的傳播

綜上所述，可以得出群體對個體影響力傳播的算法，如下所示：

輸入：G=(V,E)

輸出：群體對節點 vt的影響力 FGt

1）開始，通過廣度優選搜索算法獲取節點 vi到集合Vi中節點的路徑與距離表；

2）計算網絡中每個節點的k-shell值；

3）計算網絡中每個節點間的貢獻度 Cn(i, j)；

4）計算i節點在群體中受到的平均影響力大小FG；

5）由公式（4）求得群體對目標節點 vt的影響力 FGt。

6）END

4 仿真實驗

4.1 Email網絡仿真

通過本文的算法可以確定群體轉移給每個節點的影響力值，考慮到從群體轉移到目標節點的影響力越大，反過來從該節點向群體可以傳播的速度就越快，廣度也相應越遠。本節使用經典的傳染病模型進行仿真，能夠較為直觀地監測到節點傳播情況。本文使用SI傳染模型，并在隨機網絡與Email網絡中實現仿真。在 Email網絡總進行群體對個體的影響力排序分析，結果如表2所示。

表2 Email網絡本算法與經典K-shell算法排名前三節點Tab.2 The algorithm of Email network and classic k-shell algorithm rank the top three points

根據上述排序結果，首先選定節點105號與299號進行傳播仿真，結果如圖 1所示，105號傳播效果明顯優于299號；同時將排序第二位及第三位的節點對進行傳播仿真，結果如圖 2、圖 3所示。綜上所述，本算法獲得的節點傳播效果均優于其它算法。

下面將整個網絡中的節點，按群體對節點傳播的影響力從小到大排序，其橫坐標為節點序號的對數，縱坐標為群體對個體的影響力值。

如圖4所示，對曲線分析可知，曲線的切線的斜率隨著橫坐標的增大而增大的更明顯，網絡整體對大部分節點傳播的影響力很少，而對小部分節點傳播了很大的影響力。通過這一研究分析，整個網絡群體更多的將影響力，傳播給了少數不足20%的節點。因此，只需要對GtF 算法中排序靠前的重要節點進行監控，便能了解一個群體影響力的作用程度。

4.2 隨機網絡仿真

在隨機網絡總進行群體對個體的影響力排序分析，結果如表3所示。

圖1 Email網絡105, 299號節點傳播結果Fig.1 Email network 105, 299 node communication results

圖3 Email網絡196, 434號節點傳播結果Fig.3 Email network 196, 434 node communication results

表3 隨機網絡本算法與經典K-shell算法排名前三節點Tab.3 Random network algorithm and classic k-shell algorithm rank the top three nodes

在隨機網絡中仿真結果如圖5(a)(b)表明，在GtF算法中排名前三的節點1、2、3號傳播效果均優于，在K-shell算法中排名前三的1、3、5號節。

圖2 Email網絡16, 389號節點傳播結果Fig.2 Email network 16, 389 node communication results

圖4 影響力值排序后分布情況Fig.4 Distribution after ranking of influence values

5 結論及未來工作

現如今社交網絡的輿情已經從公眾輿論的折射場轉為了引發地、爆發場，成為網絡輿情的重要陣地，對社會活動影響深遠。社交網絡的輿情又呈現出多樣化和復雜性，能夠準確地掌握和控制輿情在群體中的演化過程迫在眉睫，因此有必要針對群體對個體的行為特點和影響力的關聯性進行研究，進一步理解和揭示影響力的作用機制和潛在的機理。本文提出了群體對個體影響力的計算方法，并建立了算法模型。進行了SI傳播仿真分析，群體對個體影響力分布分析，結果表明本文提出的算法在傳播仿真中表現優異，能夠準確地找出重要的節點。希望能夠在控制網絡輿情傳播、處理社會突發事件等方面，為決策者提供更全面、更準確的幫助。

圖5 (a) 隨機網絡2, 3號節點傳播結果Fig.5(a) Random network node 2, 3 transmission results

下一階段的研究重點是在本文研究的基礎之上，進一步分析研究群體對個體的影響是如何隨時間而演化的。

[1] 趙旭劍, 張立, 李波, 等. 網絡新聞話題演化模式挖掘[J].軟件, 2015, 36(6): 1-6

[2] 王非. 基于微博的情感新詞發現研究[J]. 軟件, 2015,36(11): 06-08

[3] Hegselmann R, Krause U. Opinion Dynamics and Bounded Confidence Models, Analysis and Simulation[J]. Journal of Artificial Societies & Social Simulation, 2002, 5(3): 2.

[4] Li N N, Zhang N, Zhou T. Empirical analysis on temporal statistics of human correspondence patterns[J]. Physica A Statistical Mechanics & Its Applications, 2008, 387(25):6391-6394.

[5] Li Z, Tang X. From Global Polarization to Local Social Mechanisms: A Study Based on ABM and Empirical Data Analysis[M]. Springer Japan, 2015: 29-40.

[6] ZHU Li-ping, YUAN Jia-jin, Li Hong. The Influence of Emotional Valence and Intensity on Vocabulary Processing[J].Psychological Science, 2011, (02): 284-288(In Chinese)朱麗萍, 袁加錦, 李紅. 情緒效價及強度對詞匯加工的影響[J].心理科學, 2011, (02): 284-288.

圖5 (b) 隨機網絡3, 5號節點傳播結果Fig.5(b) Random network node 3, 5transmission results

[7] LIU Kai, ZHU Hengmin, LIU Jingxian, Lu Zifang. R esearch on Netizens Factors in Internet Public Opinion Spread.Journal of Intellige, 2014, (04): 102-104 ( In Chinese)劉凱,朱恒民, 劉靜嫻等. 互聯網輿情傳播中的網民作用因素研究[J]. 情報雜志, 2014, (04): 102-104.

[8] Verma G, Swami A, Chan K. The impact of competing zealots on opinion dynamics[J]. Physica A Statistical Mechanics& Its Applications, 2014, 395(4): 310-331.

[9] Portillo I G. Cooperative networks overcoming defectors by social influence[J]. Physica A Statistical Mechanics & Its Applications, 2014, 394(2): 198-210.

[10] 劉璇, 于雙元. 非結構化P2P 網絡基于馬爾科夫鏈的搜索算法研究[J]. 軟件, 2015, 36(3): 116-121

[11] Li Lei, Liu Ji. Empirical Analysis of Micro－blogger Behavior Clustering on Public Opinion Topics. Journal of Intellige, 2014, (03): 118-121 ( In Chinese)李磊, 劉繼. 面向輿情主題的微博用戶行為聚類實證分析[J]. 情報雜志,2014, (03): 118-121.

[12] Bonzom V, Gurau R, Rivasseau V. The Ising Model on Random Lattices in Arbitrary Dimensions[J]. Physics Letters B, 2011, 711(1): 88-96.

[13] Floriana G, Ramasco J J. Influence of Opinion Dynamics on the Evolution of Games[J]. Plos One, 2012, 7(11): e48916.

[14] 顧亦然, 王兵, 孟繁榮. 一種基于K-Shell的復雜網絡重要節點發現算法[J]. 計算機技術與發展, 2015(9): 70-74.GU Yi-ran, Wang Bing, Meng Fan-rong. A algorithm to find important nodes based on K-shell[J] Computer Technology and Development, 2015 25(09) 70-7.