KiC：一種結(jié)合“結(jié)構(gòu)洞”約束值與K殼分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法

李鋼 王聿達(dá) 崔蓉

收稿日期：2020-03-19

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

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

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

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

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

DOI：10.3969/j.issn.1008-0821.2020.12.003

〔中圖分類(lèi)號(hào)〕G201? 〔文獻(xiàn)標(biāo)識(shí)碼〕A? 〔文章編號(hào)〕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

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

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

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

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

1? 基礎(chǔ)理論

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

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

1.2? K殼分解算法

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

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

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

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

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

1.4? SIR疾病傳播模型

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

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

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

2.1? 理論及算法

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

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

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

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

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

式（3）中τi代表了節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的集合，pij定義為邊eij的聚集系數(shù)，qij定義為邊eij的擴(kuò)散系數(shù)，TFi（t）表示節(jié)點(diǎn)的時(shí)間演化因子（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時(shí)刻i狀態(tài)為S

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

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

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

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

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

2.2? 算法論證

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

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

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

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

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

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

3? 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

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

通過(guò)對(duì)比圖5中的5個(gè)真實(shí)網(wǎng)絡(luò)的傳播情況可以發(fā)現(xiàn)，整體上看對(duì)于各個(gè)傳播時(shí)間t通過(guò)KiC算法識(shí)別的重要節(jié)點(diǎn)傳入的信息，其傳播范圍都明顯大于隨機(jī)傳入網(wǎng)絡(luò)的信息，并且最終穩(wěn)定狀態(tài)下受到信息影響的節(jié)點(diǎn)數(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%。同時(shí)從圖5曲線(xiàn)斜率看，傳播到達(dá)穩(wěn)態(tài)之前通過(guò)KiC算法識(shí)別的節(jié)點(diǎn)傳入的信息斜率要高于隨機(jī)節(jié)點(diǎn)傳入，表明本文提出的算法所識(shí)別的節(jié)點(diǎn)網(wǎng)絡(luò)信息擴(kuò)散速度較快。通過(guò)以上實(shí)驗(yàn)可知，以KiC算法獲得的節(jié)點(diǎn)為初始感染源的傳播又快又廣，說(shuō)明本算法能夠識(shí)別網(wǎng)絡(luò)中傳播影響力高的節(jié)點(diǎn)。

4? 總? 結(jié)

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

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

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

參考文獻(xiàn)

[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)洞”尋找社會(huì)網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)[J].物理學(xué)報(bào)，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)，朱敏.基于點(diǎn)權(quán)的混合-shell關(guān)鍵節(jié)點(diǎn)識(shí)別方法[J].華東師范大學(xué)學(xué)報(bào)：自然科學(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]楊李，宋玉蓉，李因偉.考慮邊聚類(lèi)與擴(kuò)散特性的信息傳播網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法[J].物理學(xué)報(bào)，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é)任編輯：陳? 媛）