李鋼 王聿達 崔蓉

收稿日期：2020-03-19

基金項目：2019年國家社會科學(xué)基金項目“智能時代的意識形態(tài)風(fēng)險防范研究”（項目編號：19BKS098）。

作者簡介：李鋼（1968-），男，教授，博士，研究方向：網(wǎng)絡(luò)社會管理、網(wǎng)絡(luò)與公共信息管理。崔蓉（1989-），女，博士研究生，研究方向：復(fù)雜網(wǎng)絡(luò)理論與應(yīng)用。

通訊作者：王聿達（1989-），男，博士研究生，研究方向：復(fù)雜網(wǎng)絡(luò)與信息傳播、數(shù)據(jù)挖掘。

摘? 要：[目的/意義]在大規(guī)模社交網(wǎng)絡(luò)中快速搜索關(guān)鍵節(jié)點對于輿情的引導(dǎo)和控制具有重要意義。[方法/過程]本文提出一種適用于社交網(wǎng)絡(luò)的局部中心性關(guān)鍵節(jié)點識別算法，該方法綜合評估了節(jié)點的K殼、自身的聚集特性以及鄰居的擴散特性和節(jié)點自身傳播狀態(tài)，同時體現(xiàn)了節(jié)點在空間上的網(wǎng)絡(luò)位置和鄰居的拓撲結(jié)構(gòu)以及在時間上演化特征，評價指標更加全面高效。[結(jié)果/結(jié)論]實驗結(jié)果表明，該方法識別的關(guān)鍵節(jié)點對網(wǎng)絡(luò)魯棒性的影響與介數(shù)中心性接近，但計算僅基于節(jié)點局部信息，時間復(fù)雜度低。剔除這些節(jié)點后網(wǎng)絡(luò)的連通性受到較大影響，網(wǎng)絡(luò)聚類系數(shù)降低，平均路徑長度增加。同時，利用SIR傳播模型模擬驗證，以該算法識別的關(guān)鍵節(jié)點為初始傳播源可提升信息傳播范圍和平均傳播速度。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);關(guān)鍵節(jié)點;K殼;約束系數(shù);輿情傳播

DOI：10.3969/j.issn.1008-0821.2020.12.003

〔中圖分類號〕G201? 〔文獻標識碼〕A? 〔文章編號〕1008-0821（2020）12-0027-09

KiC：An Extended K-shell Decomposition Based on

Improved Network Constraint Coefficient

Li Gang? Wang Yuda*? Cui Rong

（School of Economics and Management，Beijing University of Posts and Telecommunications，

Beijing 100876，China）

Abstract：[Purpose/Significance]Evaluating vital nodes rapidly in large-scale social networks is of great significance for the control of information dissemination.[Method/Process]In this paper，we proposed a local centrality vital node identification algorithm.The method comprehensively evaluated the K-shell of a node，its own clustering characteristics，the diffusion characteristics of its neighbors and propagation state of nodes，which simultaneously reflected the network location of the nodes，the topology of the neighbors and evolutionary features in time.The evaluation indicators were more comprehensive and efficient.[Result/Conclusion]The experimental results showed that the vital nodes identified by this method had a greater impact on the robustness of the network.After removing these nodes，the connectivity of the network was greatly affected，the network clustering coefficient was reduced，and the average path length was increased.Meanwhile，SIR model was used to evaluate the ability to spread nodes.Simulations of five real networks showed that our proposed method could improve the scope and average speed of information dissemination.

Key words：complex network;vital node;K-shell;constraint coefficient;information dissemination

近年來，對復(fù)雜網(wǎng)絡(luò)的研究已成為許多領(lǐng)域關(guān)注的熱點。幾乎所有的復(fù)雜系統(tǒng)都可以表示為網(wǎng)絡(luò)，網(wǎng)絡(luò)的頂點代表實體，而邊則表示實體間的關(guān)系與相互作用。網(wǎng)絡(luò)中存在對提高系統(tǒng)魯棒性意義重大的節(jié)點，這些節(jié)點一般數(shù)量非常少，但其影響卻可以快速波及網(wǎng)絡(luò)中大部分節(jié)點。例如：在社交網(wǎng)絡(luò)中，對少量最重要節(jié)點的刪除能夠有效控制信息的傳播。可見重要節(jié)點對網(wǎng)絡(luò)的動力學(xué)行為有著巨大的影響。因此，在大規(guī)模社交網(wǎng)絡(luò)中快速搜索關(guān)鍵節(jié)點意義重大。

識別網(wǎng)絡(luò)中的關(guān)鍵節(jié)點受到物理、數(shù)學(xué)、計算機和管理科學(xué)等多學(xué)科的廣泛關(guān)注，使其成為各個學(xué)科所共同關(guān)注的交叉科學(xué)，各學(xué)科研究人員根據(jù)所關(guān)注的具體問題，提出了眾多重要節(jié)點排序方法。利用節(jié)點度中心性來判斷節(jié)點的重要性是最簡單的方法[1]，該方法認為，一個節(jié)點的度越大，影響力就越大，其缺點是沒有全局角度考慮節(jié)點所處的網(wǎng)絡(luò)位置和鄰居的拓撲結(jié)構(gòu)，在很多情況下不夠精確。介數(shù)中心性[2]和接近度中心性[3]從全局出發(fā)，分別考慮節(jié)點到達其余節(jié)點的最短路徑數(shù)目，節(jié)點與其他所有節(jié)點最短距離的平均值，此類方法在評估節(jié)點重要性方面有了明顯的效果，但由于需要獲得整個網(wǎng)絡(luò)的拓撲特征，導(dǎo)致時間復(fù)雜度高，不適用于當(dāng)前社交網(wǎng)絡(luò)關(guān)鍵節(jié)點的識別。為平衡識別效果和時間復(fù)雜度，Chen D等[4]提出了半局部中心性，半局部中心性使用了節(jié)點的四階鄰居的度作為判斷依據(jù)，相較介數(shù)中心性該算法消耗非常少的計算時間，然而該算法只考慮了鄰居節(jié)點信息，忽略了節(jié)點在全局網(wǎng)絡(luò)中所處的位置。Burt R S等[5-7]基于經(jīng)典社會學(xué)中的“結(jié)構(gòu)洞”理論，用網(wǎng)絡(luò)約束系數(shù)來衡量節(jié)點形成結(jié)構(gòu)洞時所受到的約束，該方法利用了局部屬性評價節(jié)點的重要性，具有較好的時間復(fù)雜度和計算精度，然而，該方案沒有考慮鄰居節(jié)點與其余節(jié)點相連的拓撲結(jié)構(gòu)對節(jié)點的影響。

Kitsak M等[8]依據(jù)網(wǎng)絡(luò)中節(jié)點處于網(wǎng)絡(luò)的核心位置往往有較高影響力的思想，提出用K殼分解法確定網(wǎng)絡(luò)中節(jié)點的位置，在分析大規(guī)模網(wǎng)絡(luò)的關(guān)鍵節(jié)點等方面具有良好的時間復(fù)雜度。然而此方法也有一定局限性，如未考慮刪除節(jié)點等。Zeng A等[9]提出了混合度分解算法，混合度以網(wǎng)絡(luò)中剩下的鄰居節(jié)點以及刪除的鄰居節(jié)點的混合度進行K殼計算，此方法較好地提高了節(jié)點區(qū)分度。王環(huán)等[10]提出了點權(quán)分解算法，該算法綜合考慮了節(jié)點的全局指標加權(quán)核值以及節(jié)點的局部指標度數(shù)，真實網(wǎng)絡(luò)的實驗結(jié)果表明，此算法在關(guān)鍵節(jié)點識別中可取得較好的效果。

綜上所述，要準確識別社交網(wǎng)絡(luò)環(huán)境下節(jié)點的傳播能力，不但要考慮節(jié)點所處的網(wǎng)絡(luò)位置和鄰居的拓撲結(jié)構(gòu)，還需考慮計算的時間復(fù)雜度，同時由于網(wǎng)絡(luò)輿情時間特性明顯，節(jié)點時序特性也是識別關(guān)鍵節(jié)點的重要因素。K殼分解算法可以高效準確地識別節(jié)點在網(wǎng)絡(luò)中的位置，然而當(dāng)前的K殼分解及其優(yōu)化算法還存在如下局限性：第一，沒有考慮鄰居之間的拓撲關(guān)系，不能在計算中反映鄰居節(jié)點間的相互作用。第二，缺乏“橋”節(jié)點的識別，在社交網(wǎng)絡(luò)中存在著一些度很小但是很重要的“橋接”節(jié)點，它們在信息的傳遞中擔(dān)任重要的角色[11]。第三，識別會受到網(wǎng)絡(luò)中類核（Core-like）的影響[12]，這些類核結(jié)構(gòu)里的節(jié)點對信息或者病毒的擴散能力通常較弱，但卻會被識別為處在網(wǎng)絡(luò)核心位置。第四，排序結(jié)果太過粗粒度，節(jié)點的區(qū)分度不大，尤其是在樹形結(jié)構(gòu)網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)中。第五，未考慮節(jié)點在不同時間自身的傳播屬性。因此，本文從以上5個角度出發(fā)，通過在K殼分解原理的基礎(chǔ)上，利用節(jié)點及其鄰居的聚集性和擴散性，并結(jié)合節(jié)點傳播狀態(tài)的時序變化優(yōu)化計算節(jié)點結(jié)構(gòu)洞約束值，以K殼值與結(jié)構(gòu)洞約束值聯(lián)合評價作為節(jié)點重要性指標。通過在真實的網(wǎng)絡(luò)中進行仿真驗證，結(jié)果表明，該算法識別的關(guān)鍵節(jié)點對于網(wǎng)絡(luò)魯棒性的影響較大，從這些關(guān)鍵節(jié)點傳入的信息能夠在網(wǎng)絡(luò)中更快地傳播，并且傳播范圍更廣。

1? 基礎(chǔ)理論

1.1? 網(wǎng)絡(luò)定義

對于一個無向無權(quán)網(wǎng)絡(luò)，可以通過G=（V，E）進行表示，其中V表示網(wǎng)絡(luò)中節(jié)點的集合，E是網(wǎng)絡(luò)邊的集合。eij用于表示節(jié)點i和節(jié)點j之間邊的關(guān)系，如果節(jié)點i與節(jié)點j有邊，則eij=1，否則eij=0。節(jié)點i的度表示為ki。為便于理論分析和實驗驗證，本文所用到的網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中的節(jié)點數(shù)量及節(jié)點間關(guān)系不會隨時間發(fā)生變化。

1.2? K殼分解算法

K殼分解算法可用于確定網(wǎng)絡(luò)中節(jié)點的位置。其核心思想是根據(jù)節(jié)點度數(shù)遞歸地刪除網(wǎng)絡(luò)中的節(jié)點，分解過程如下：網(wǎng)絡(luò)中如果存在度為1的節(jié)點，從度中心性的角度看它們就是最不重要的節(jié)點，刪除這些節(jié)點及其相連的邊，剩下的網(wǎng)絡(luò)中會新出現(xiàn)一些度為1的節(jié)點，再將這些度為1的節(jié)點去掉，循環(huán)直至所剩的網(wǎng)絡(luò)中沒有度為1的節(jié)點為止，記這些刪除的節(jié)點稱為1。按上述方法繼續(xù)剝殼，重復(fù)這些操作直到網(wǎng)絡(luò)中沒有節(jié)點為止。圖1為經(jīng)K殼算法分解后的網(wǎng)絡(luò)示意圖，其中1～3為3殼節(jié)點，5為2殼節(jié)點，6～14為1殼節(jié)點。

1.3? 結(jié)構(gòu)洞理論及網(wǎng)絡(luò)約束值

社會學(xué)理論中，結(jié)構(gòu)洞存在于社會網(wǎng)絡(luò)中沒有冗余連接的兩個個體之間，洞兩邊的個體可以帶來累加的網(wǎng)絡(luò)收益[5]。從復(fù)雜網(wǎng)絡(luò)的角度來看，結(jié)構(gòu)洞特征強的兩個節(jié)點之間的邊在網(wǎng)絡(luò)中能夠獲得更多競爭優(yōu)勢，是約束信息傳播的關(guān)鍵邊。Burt R S首先提出了用約束系數(shù)來衡量網(wǎng)絡(luò)節(jié)點受到結(jié)構(gòu)洞的約束，其表達式如下：

Ci=∑j∈τ（i）pij+∑qpiqpqj2， q≠i，j（1）

其中pij表示節(jié)點i為維持與節(jié)點j的鄰居關(guān)系所投入的精力占總精力的比例（也就是度），piq和pqj分別是節(jié)點i、j與共同鄰居q維持關(guān)系投入的精力占其總精力的比例。約束系數(shù)綜合考慮了節(jié)點的鄰居數(shù)目以及鄰居之間連接的緊密程度（鄰居間的閉合程度），節(jié)點鄰居數(shù)量越少且與其鄰居間的閉合程度越高，越不利于信息傳播。

1.4? SIR疾病傳播模型

疾病傳播是社交網(wǎng)絡(luò)上信息交換并可能傳播的一種抽象表現(xiàn)形式，其傳播是一個非常復(fù)雜的問題，結(jié)果依賴于傳播過程中的具體情況。由于存在著這種相似性，學(xué)術(shù)界關(guān)于謠言傳播模型的研究大多來源于經(jīng)典的疾病傳播模型。疾病傳播模型最初是Kermack[13]在研究黑死病時提出的SIR模型。該模型描述了有些疾病的傳播是具有免疫能力的，人被感染后就不會再次被感染。SIR模型將疾病流行范圍內(nèi)的人群分成易感者S，感染者I和免疫者R，人群中每個個體的時序狀態(tài)在3類之間轉(zhuǎn)換。在疾病演進過程中，處于感染態(tài)的節(jié)點以概率β向相鄰的易感節(jié)點進行傳播，同時每個感染節(jié)點則以概率γ治愈或死亡。

SIR模型適用于典型的社交網(wǎng)絡(luò)輿情傳播場景，針對一條信息，社交網(wǎng)絡(luò)中的人群可分為不知情者S、知情并傳播者I和知情不傳播者R，通過SIR模型可動態(tài)描述信息在社交網(wǎng)絡(luò)中的演進過程。

2? 社交網(wǎng)絡(luò)關(guān)鍵節(jié)點識別改進算法及算法論證

2.1? 理論及算法

從上述相關(guān)理論分析可以看到，K殼分解算法可以高效地識別出節(jié)點所處的網(wǎng)絡(luò)位置，“結(jié)構(gòu)洞”約束值可從節(jié)點局部拓撲分析鄰居節(jié)點之間的相互作用，節(jié)點傳播狀態(tài)可以從時間演進角度對輿情傳播中的節(jié)點重要性進行評估。本文所提出的改進算法（Extended K-shell Based on Improved Network Constraint）綜合考慮了K殼分解算法、優(yōu)化后的“結(jié)構(gòu)洞”約束值計算方法以及結(jié)合了節(jié)點傳播狀態(tài)的時序特征，更適用于社交網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別，算法定義如下：

KiCi（t）=ksi·ICi（t）（2）

KiCi（t）表示節(jié)點i在t時刻的KiC系數(shù)，ksi是節(jié)點i的K殼值，ICi（t）是本文優(yōu)化后的節(jié)點i在t時刻的約束系數(shù)。從式（2）可以看出，KiC是t時刻由K殼值與約束系數(shù)點乘得出，因此該值既能夠體現(xiàn)出節(jié)點的網(wǎng)絡(luò)位置，又能夠結(jié)合鄰居的拓撲結(jié)構(gòu)和時間維度上的傳播狀態(tài)。網(wǎng)絡(luò)約束系數(shù)（Improved Constraint）的表達式為：

ICi（t）=TFi（t）·∑j∈τiTFj（t）·pij+∑k∈τjTFk（t）·qij·qjk， k≠i，j（3）

在Burt R S提出的算法中，通過節(jié)點的鄰居數(shù)目（度）以及鄰居之間連接的緊密程度（鄰居之間的閉合程度）計算約束系數(shù)來識別關(guān)鍵節(jié)點，該算法應(yīng)用在社交網(wǎng)絡(luò)中存在3個問題：一是用節(jié)點度的大小來衡量節(jié)點是否處于社團的局部中心性不夠全面;二是僅使用一階鄰居的閉合情況無法準確發(fā)現(xiàn)一些重要的“橋”節(jié)點;三是只考慮了網(wǎng)絡(luò)空間特性，未考慮輿情演化的時間特性。因此，本文改進了約束系數(shù)的計算方式，通過邊的聚集性代替度表示節(jié)點的局部中心性，通過邊的二階擴散性代替鄰居閉合程度解決了“橋”節(jié)點識別不準的問題，通過節(jié)點的當(dāng)前傳播狀態(tài)還原不同時序下節(jié)點的真實重要性。

式（3）中τi代表了節(jié)點i的鄰居節(jié)點的集合，pij定義為邊eij的聚集系數(shù)，qij定義為邊eij的擴散系數(shù)，TFi（t）表示節(jié)點的時間演化因子（Time Evolution Factor）。其中：

pij={k∶k∈τ（i，j）＼i，j，Δijk∈ΔG}τ（i，j）＼i，j（4）

qij=∑k∈τ（i，j）＼i，jθkτ（i，j）＼i，j（5）

TFi（t）=1， t時刻i狀態(tài)為S

1+β， t時刻i狀態(tài)為I， β為傳播概率

0， t時刻i狀態(tài)為R（6）

1）邊eij的聚集特性[14-16]可通過節(jié)點i和j的鄰居節(jié)點與eij構(gòu)成的三角形的占比來表示，無法構(gòu)成三角形的鄰居節(jié)點占比表示邊eij的聚集特性。如圖2所示，當(dāng)信息從節(jié)點i經(jīng)過邊eij傳播時，可通過擴散特性中的節(jié)點2和節(jié)點3將信息傳播到網(wǎng)絡(luò)中的其他節(jié)點，也可通過聚類特性中的節(jié)點1回傳至節(jié)點j，因此邊的聚類與擴散特性通過點的二階鄰居信息，有效地描述了對信息傳播的影響作用。

2）時間演進因子TFi（t）表示在輿情演進過程中，i節(jié)點在t時刻所處的不同狀態(tài)對節(jié)點約束系數(shù)正向促進或負向抑制的作用。本文認為S狀態(tài)為節(jié)點的基礎(chǔ)狀態(tài)，在某時刻不知情狀態(tài)（S狀態(tài)）的節(jié)點將不會對約束系數(shù)起到作用;當(dāng)節(jié)點處于I狀態(tài)時，由于該節(jié)點當(dāng)前具有傳播性，因此會比網(wǎng)絡(luò)空間中的其他節(jié)點更加重要，此時與該節(jié)點重要性相關(guān)的約束系數(shù)會加強;當(dāng)節(jié)點處于R狀態(tài)時，該節(jié)點當(dāng)前及之后的時間將不會對信息進行傳播，因此從輿情傳播的角度來看該節(jié)點重要性降為0。

通過上述表述可知通過式（3）的改進，在約束系數(shù)的計算中同時體現(xiàn)了節(jié)點的聚類性、鄰居拓撲結(jié)構(gòu)的擴散特性以及節(jié)點當(dāng)前時刻狀態(tài)對節(jié)點重要性的加強和削弱作用。

2.2? 算法論證

本文所提出的KiC算法相較以往的K殼及其改進算法，能夠從空間上以低時間復(fù)雜度識別一些重要的“橋節(jié)點”，能夠有效消除類核（局部聚類結(jié)構(gòu)）的影響，能夠更加細粒度、有區(qū)分度地識別節(jié)點的重要性，能夠隨著信息的傳播從時間維度識別關(guān)鍵節(jié)點。本節(jié)以圖1所示的小規(guī)模數(shù)據(jù)集為例，進行算法準確性分析，為保證實驗結(jié)果的可對比性，論證一至論證三只考慮網(wǎng)絡(luò)空間特性而不考慮時間特性，即網(wǎng)絡(luò)是一個所有節(jié)點都處于S狀態(tài)的靜態(tài)網(wǎng)絡(luò);論證四中節(jié)點2為初始信息傳播者（I狀態(tài)），其余節(jié)點為不知情者（S狀態(tài)），傳播率β為0.41（網(wǎng)絡(luò)的平均度=2.43，為保證傳播能夠進行，取傳播率為1k），康復(fù)率γ為0.1。

論證一：提供細粒度化關(guān)鍵節(jié)點識別能力。針對圖1的網(wǎng)絡(luò)，本文分別用幾種算法對其分解，進而獲得了節(jié)點重要性的排序結(jié)果。表1所示的是節(jié)點重要性排序結(jié)果。從表中可以看出，度中心性、K殼分解、MDD分解存在大量排序相同的節(jié)點，區(qū)分度相對較低。EKSDN（點權(quán)中心性）、結(jié)構(gòu)洞算法相對較好，本文提出的KiC算法相較上述兩種算法區(qū)分度更大，相比于其他算法效果稍好。

論證二：能夠有效過濾影響力較低的類核節(jié)點。類核節(jié)點是指局部與大量節(jié)點緊密相連，而與網(wǎng)絡(luò)中其他節(jié)點連接較少的節(jié)點。通過類核節(jié)點的信息更容易在這個緊密社團內(nèi)部擴散，而不容易將信息擴散出去，因此將其識別為影響力最大的節(jié)點是不準確的。表1的結(jié)果可以看出，傳統(tǒng)的K殼分解算法和結(jié)構(gòu)洞算法將節(jié)點1識別為最重要節(jié)點。

本文提出的算法可以從節(jié)點1、2、3和4組成的相互緊密連接的類核中過濾出影響力較小的節(jié)點1。因此本算法在過濾類核方面優(yōu)于傳統(tǒng)算法。

論證三：能夠發(fā)現(xiàn)重要局部“橋”節(jié)點。KiC算法綜合考慮了節(jié)點的聚集性和擴散性，使既有橋接特性也具有社區(qū)中心性的節(jié)點2和4排名靠前，同時本文提出的算法通過從局部二階節(jié)點的角度來衡量節(jié)點的“橋”特征，使得能夠識別出更重要的“橋”節(jié)點5，觀察圖1可知，將節(jié)點2和4排在首位，將“橋”特性明顯的節(jié)點5排在節(jié)點1前顯然更加合理，所以KiC算法在識別“橋”特性方面優(yōu)于其他算法。

論證四：能夠隨著信息的傳播從時間維度更加準確地識別關(guān)鍵節(jié)點。觀察圖3，在t=1時刻節(jié)點2為初始信息傳播者，該節(jié)點既具備最重要的網(wǎng)絡(luò)空間特性，又是該時刻唯一信息傳播者，被識別為關(guān)鍵節(jié)點。隨著信息的傳播，在t=2時刻節(jié)點2變?yōu)镽狀態(tài)，節(jié)點3和節(jié)點5變?yōu)镮狀態(tài)，由于節(jié)點2不再具備傳播特性，從輿情傳播的角度來看，該節(jié)點重要性降為0，節(jié)點3變?yōu)樽钪匾?jié)點。當(dāng)t=3時，由于節(jié)點6變?yōu)樾畔鞑フ?，增強了?jié)點5的信息傳播特性，根據(jù)算法計算結(jié)果此時刻節(jié)點5重要程度超過節(jié)點3。在t=4時刻，由于節(jié)點6變?yōu)榱薘狀態(tài)，此刻節(jié)點3重新變?yōu)樽钪匾?jié)點。從信息傳播的時間維度來看，相較于靜態(tài)空間網(wǎng)絡(luò)，KiC算法充分結(jié)合網(wǎng)絡(luò)時空特性，能夠有效地根據(jù)節(jié)點的不同傳播狀態(tài)動態(tài)識別關(guān)鍵節(jié)點。

3? 實驗與結(jié)果分析

3.1? 數(shù)據(jù)集及信息傳播模型

在實驗中采用的網(wǎng)絡(luò)為：①Karate網(wǎng)絡(luò)[17]，美國一個大學(xué)空手道俱樂部成員;②Dophins網(wǎng)絡(luò)[18]，以聲音相互聯(lián)系的海豚社交網(wǎng)絡(luò);③Polbooks網(wǎng)絡(luò)[19]，美國政治書籍網(wǎng)絡(luò);④Football網(wǎng)絡(luò)[20]，經(jīng)典的美國橄欖球俱樂部社會網(wǎng)絡(luò);⑤NetScience網(wǎng)絡(luò)[21]，從事網(wǎng)絡(luò)理論和實驗科學(xué)家合著的關(guān)系網(wǎng)絡(luò)。表2為這5個網(wǎng)絡(luò)的一些統(tǒng)計特性。

3.2? 剔除關(guān)鍵節(jié)點后網(wǎng)絡(luò)結(jié)構(gòu)統(tǒng)計特性對比分析

為了驗證關(guān)鍵節(jié)點對信息傳播的影響，本實驗使用KiC算法對5個真實網(wǎng)絡(luò)的關(guān)鍵節(jié)點進行識別，并分別將識別出的排名前3%的關(guān)鍵節(jié)點隔離（剔除與這些節(jié)點相連的邊）。網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計特性變化情況如表3，從表中可見，網(wǎng)絡(luò)的平均度和聚類系數(shù)有所降低，平均路徑長度有所增加。從信息傳播角度分析，聚類系數(shù)的降低使得網(wǎng)絡(luò)社團緊密度降低，信息在社團內(nèi)部傳播閾值將隨之降低，而平均路徑長度的提升使信息更難傳播到網(wǎng)絡(luò)的其他部分。從網(wǎng)絡(luò)統(tǒng)計特性的角度驗證了控制KiC算法所識別的關(guān)鍵節(jié)點對抑制信息傳播的有效性。

3.3? 關(guān)鍵節(jié)點對網(wǎng)絡(luò)魯棒性影響的分析

為了進一步分析KiC算法識別的節(jié)點的重要性，本組實驗分別通過KiC、度中心性、K殼、接近中心性、介數(shù)中心性和隨機6種算法將Karate網(wǎng)絡(luò)的所有節(jié)點按照重要性進行排序，然后按照重要性從大到小的順序依次移除節(jié)點，通過對比網(wǎng)絡(luò)中剩余節(jié)點所構(gòu)成的最大連通子圖的節(jié)點個數(shù)，評估不同算法在識別關(guān)鍵節(jié)點的差異。從信息傳播角度來看，移除相同節(jié)點，最大連通子圖變化越大，說明圖的連通性越差，信息傳播到網(wǎng)絡(luò)其他部分的可行性越低，移除的節(jié)點越重要。從圖4可知，初始時刻Karate網(wǎng)絡(luò)是一個完全連通的網(wǎng)絡(luò)，開始移除節(jié)點后，通過隨機算法移除節(jié)點的網(wǎng)絡(luò)變化較小，而其他5種算法移除關(guān)鍵節(jié)點后最大連通子圖變化明顯，其中KiC算法、介數(shù)中心性、接近中心性相較度中心性和K殼算法下降較快。當(dāng)移除重要性前5%的節(jié)點時，5種算法的最大連通子圖分別為初始時刻的76%、69%、79%、83%、85%，而當(dāng)移除重要性前12%的節(jié)點時，最大連通子圖分別較移除5%時下降36%、36%、32%、21%、22%至49%、44%、52%、83%、84%。通過實驗數(shù)據(jù)可知KiC算法所識別的關(guān)鍵節(jié)點較K殼算法和度中心性算法更加準確，與介數(shù)中心性和接近中心性相近，KiC、介數(shù)中心性、接近中心性在控制10%左右的重要節(jié)點后最大連通子圖降至50%左右，能夠有效地降低網(wǎng)絡(luò)連通性，降低信息傳播能力。

3.4? 網(wǎng)絡(luò)傳播動力學(xué)模型有效性驗證

為了驗證KiC算法識別的重要節(jié)點在社交網(wǎng)絡(luò)上的傳播能力，本節(jié)通過在真實社交網(wǎng)絡(luò)上使用SIR模型模擬信息傳播，對比不同信息傳入節(jié)點平均信息傳播范圍和平均傳播速度來考察節(jié)點的真實影響力。本實驗共設(shè)置5組，對應(yīng)5個不同的真實社交網(wǎng)絡(luò)，每組實驗設(shè)置一個對照組，分別以KiC算法識別的最重要節(jié)點和隨機選取一個節(jié)點為初始感染節(jié)點，觀察每一時間步網(wǎng)絡(luò)中感染過的節(jié)點數(shù)目和最終穩(wěn)定態(tài)時感染過的節(jié)點數(shù)目，為保證傳播能夠進行，取SIR模型中傳播率為1k，康復(fù)率為0.1。

通過對比圖5中的5個真實網(wǎng)絡(luò)的傳播情況可以發(fā)現(xiàn)，整體上看對于各個傳播時間t通過KiC算法識別的重要節(jié)點傳入的信息，其傳播范圍都明顯大于隨機傳入網(wǎng)絡(luò)的信息，并且最終穩(wěn)定狀態(tài)下受到信息影響的節(jié)點數(shù)量較多，其中Karate網(wǎng)絡(luò)多6.2%，Dolphins網(wǎng)絡(luò)多3.4%，Polbooks網(wǎng)絡(luò)多6%，F(xiàn)ootball網(wǎng)絡(luò)持平，NetScience網(wǎng)絡(luò)多89%。同時從圖5曲線斜率看，傳播到達穩(wěn)態(tài)之前通過KiC算法識別的節(jié)點傳入的信息斜率要高于隨機節(jié)點傳入，表明本文提出的算法所識別的節(jié)點網(wǎng)絡(luò)信息擴散速度較快。通過以上實驗可知，以KiC算法獲得的節(jié)點為初始感染源的傳播又快又廣，說明本算法能夠識別網(wǎng)絡(luò)中傳播影響力高的節(jié)點。

4? 總? 結(jié)

在大規(guī)模社交網(wǎng)絡(luò)中快速搜索關(guān)鍵節(jié)點對于信息的引導(dǎo)和傳播控制具有重要的意義。實踐表明，社交網(wǎng)絡(luò)輿情傳播不同于傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)，具有明顯的時空特性，在空間方面，要準確識別規(guī)模性社交網(wǎng)絡(luò)中不同節(jié)點的傳播能力，既要考慮節(jié)點所處的網(wǎng)絡(luò)位置和鄰居的拓撲結(jié)構(gòu)，同時需兼顧計算的時間復(fù)雜度;在時間方面，要結(jié)合網(wǎng)絡(luò)中節(jié)點的傳播狀態(tài)進行綜合評判?；谝陨峡紤]，本文提出一種結(jié)合節(jié)點局部中心性特征的K殼改進算法（KiC算法），該方法利用節(jié)點的聚集性特征及其鄰居的擴散性特征，并結(jié)合節(jié)點傳播狀態(tài)的時序變化作為改進后的“結(jié)構(gòu)洞”約束值，綜合K殼算法對節(jié)點所處位置的高效識別能力，作為評價節(jié)點重要性的指標。該改進方法同時考慮了節(jié)點的自身屬性、所處的網(wǎng)絡(luò)位置及其局部拓撲、不同時刻節(jié)點傳播狀態(tài)屬性，評價結(jié)果更加全面高效。

實驗結(jié)果表明：①該算法在網(wǎng)絡(luò)結(jié)構(gòu)上能夠消除類核影響，細粒度的識別重要的“橋節(jié)點”，并充分結(jié)合網(wǎng)絡(luò)時空特性，有效地根據(jù)節(jié)點的不同傳播狀態(tài)動態(tài)識別關(guān)鍵節(jié)點。②移除該算法所識別的重要節(jié)點后，網(wǎng)絡(luò)聚類系數(shù)降低、平均路徑長度增加，這些網(wǎng)絡(luò)特征的變化能夠控制信息傳播范圍的擴大。移除該算法所識別的10%的重要節(jié)點，能夠?qū)⒕W(wǎng)絡(luò)最大連通子圖的節(jié)點數(shù)降低50%，對于網(wǎng)絡(luò)魯棒性的影響與介數(shù)中心性、接近中心性接近，但其計算僅基于節(jié)點局部信息，時間復(fù)雜度低。③通過基于SIR模型的信息傳播驗證，以該算法識別的重要節(jié)點為初始傳播源可提升信息傳播范圍和平均傳播速度，以Karate網(wǎng)絡(luò)為例，其傳播范圍平均擴大6.2%，到達最大影響范圍時傳播時間平均縮短50%。

本文所提出的KiC算法是通過經(jīng)典社交網(wǎng)絡(luò)進行仿真驗證的，但我們相信本文所做的研究對于政府決策部門對輿情的擴散和控制具有一定的參考價值。后續(xù)我們將重點根據(jù)實驗仿真結(jié)果抓取真實社交網(wǎng)絡(luò)數(shù)據(jù)進行驗證。

參考文獻

[1]Bonacich P.Factoring and Weighting Approaches to Status Scores and Clique Identification[J].Journal of Mathematical Sociology，1972，2（1）：113-120.

[2]Freeman L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry，1977，40（1）：35-41.

[3]Latora V，Marchiori M.Efficient Behavior of Small-World Networks[J].Physical Review Letters，2001，87（19）.

[4]Chen D，Lu L，Shang M，et al.Identifying Influential Nodes in Complex Networks[J].Physica A-statistical Mechanics and Its Applications，2012，391（4）：1777-1787.

[5]Burt R S.Structural Holes：The Social Structure of Competition[M].Cambridge，MA，USA：Harvard Univ，Press，2009.

[6]蘇曉萍，宋玉蓉.利用鄰域“結(jié)構(gòu)洞”尋找社會網(wǎng)絡(luò)中最具影響力節(jié)點[J].物理學(xué)報，2015，64（2）：5-15.

[7]Ruan Y，Lao S，Xiao Y，et al.Identifying Influence of Nodes in Complex Networks with Coreness Centrality：Decreasing the Impact of Densely Local Connection[J].Chinese Physics Letters，2016，33（2）.

[8]Kitsak M，Gallos L K，Havlin S，et al.Identification of Influential Spreaders in Complex Networks[J].Nature Physics，2010，6（11）：888-893.

[9]Zeng A，Zhang C.Ranking Spreaders By Decomposing Complex Networks[J].Physics Letters A，2013，377（14）：1031-1035.

[10]王環(huán)，朱敏.基于點權(quán)的混合-shell關(guān)鍵節(jié)點識別方法[J].華東師范大學(xué)學(xué)報：自然科學(xué)版，2019，（3）：101-109.

[11]Cheng X，Ren F，Shen H，et al.Bridgeness：A Local Index on Edge Significance in Maintaining Global Connectivity[J].Physics，2010，（5）.

[12]Liu Y，Tang M，Zhou T，et al.Core-like Groups Result in Invalidation of Identifying Super-spreader By K-shell Decomposition[J].Scientific Reports，2015，5（1）：9602-9602.

[13]Pastor-Satorras R，Vespignani A.Epidemic Spreading in Scale-Free Networks[J].Physical Review Letters，2001，86（14）：3200-3203.

[14]Malliaros F D，Rossi M G，Vazirgiannis M，et al.Locating Influential Nodes in Complex Networks[J].Scientific Reports，2016，6（1）：19307-19307.

[15]楊李，宋玉蓉，李因偉.考慮邊聚類與擴散特性的信息傳播網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法[J].物理學(xué)報，2018，67（19）：92-102.

[16]Liu Y，Tang M，Do Y，et al.Accurate Ranking of Influential Spreaders in Networks Based on Dynamically Asymmetric Link Weights[J].Physical Review E，2017，96（2）.

[17]Zachary W W.An Information Flow Model for Conflict and Fission in Small Groups1[J].Journal of anthropological research，1976，33（4）：452-473.

[18]Lusseau D，Schneider K，Boisseau O，et al.The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-lasting Associations[J].Behavioral Ecology and Sociobiology，2003，54（4）：396-405.

[19]V Krebs.http：//www.orgnet.com/[EB].

[20]Girvan M，Newman M E.Community Structure in Social and Biological Networks[J].Proceedings of the National Academy of Sciences of the United States of America，2002，99（12）：7821-7826.

[21]Newman M E.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E，2006，74（3）.

（責(zé)任編輯：陳? 媛）