宋甲秀，楊曉翠，張曦煌

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122

1 引言

目前，復(fù)雜網(wǎng)絡(luò)在人們的社會生活中日漸普及，而網(wǎng)絡(luò)信息傳播[1-2]在復(fù)雜網(wǎng)絡(luò)中是一個普遍存在的過程，它描述了社會中許多重要的活動，如病毒擴散、流行病、級聯(lián)故障等[3]。在理解和控制傳播過程的問題中，影響力節(jié)點的識別具有重要的研究意義和顯著的實用價值，引起了包括信息科學(xué)、社會學(xué)、軍事等領(lǐng)域的熱切關(guān)注。一個基本的問題是如何找出在網(wǎng)絡(luò)信息傳播過程中最具有影響力的一組個體，使其能夠?qū)⒂绊憘鞑サ骄W(wǎng)絡(luò)中最多的節(jié)點，在文獻中稱之為影響最大化問題[4-5]。針對此問題，社會網(wǎng)絡(luò)分析方法和系統(tǒng)科學(xué)方法給出了不同的思想。前者強調(diào)的是節(jié)點在網(wǎng)絡(luò)中發(fā)揮的作用和功能，后者則以計算某個節(jié)點移除后給網(wǎng)絡(luò)帶來的破壞程度來衡量。由于真實網(wǎng)絡(luò)的異質(zhì)性，節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)和功能上發(fā)揮的作用差異巨大，近年來求解影響最大化問題在許多場景中被廣泛應(yīng)用，包括輿情監(jiān)控、市場推廣[6]、水污染檢測、傳染性疾病的監(jiān)控等。

雖然學(xué)術(shù)界在識別網(wǎng)絡(luò)影響力節(jié)點這個方向已經(jīng)取得了一定的成果，但對這個方向的研究依然是方興未艾。傳統(tǒng)算法多數(shù)不能兼顧時間復(fù)雜度和精度，如何利用網(wǎng)絡(luò)的結(jié)構(gòu)信息，設(shè)計一種同時保證高精度和低時間復(fù)雜度的算法來識別網(wǎng)絡(luò)中的影響力節(jié)點依舊是一個具有挑戰(zhàn)性的課題?；诖?，本文提出了一個基于局部集體影響的自適應(yīng)排序算法（local collective influence rank-adaptive recalculation algorithm，LCIR-AR）。本文的主要貢獻總結(jié)如下：

（1）考慮到節(jié)點間的相互作用，引入集體影響（collective influence）[7]這一基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的指標(biāo)，在此基礎(chǔ)上創(chuàng)新性地提出了局部集體影響指標(biāo)（local collective influence index，LCII）及局部集體影響排序算法（local collective influence rank algorithm，LCIR），使得影響力的傳播更加穩(wěn)定，并有效避免了“富人俱樂部效應(yīng)”的出現(xiàn)。

（2）對LCIR算法進行改進，設(shè)計出適應(yīng)性更強的LCIR-AR算法，在保證算法精度的同時，實現(xiàn)比較低的時間復(fù)雜度，使其在大型網(wǎng)絡(luò)同樣適用。

（3）通過4個真實網(wǎng)絡(luò)數(shù)據(jù)集分別在獨立級聯(lián)模型（independent cascade model，IC）及網(wǎng)絡(luò)抗毀性實驗中的結(jié)果對比，驗證了本文算法的可行性、有效性及其在該研究領(lǐng)域的競爭力。

（4）驗證了在網(wǎng)絡(luò)中扮演主要經(jīng)紀人角色的低度節(jié)點在維持網(wǎng)絡(luò)穩(wěn)定性上的影響力，對未來的研究提供了一定的借鑒作用。

2 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)中一組影響力節(jié)點識別算法的目標(biāo)是尋找社會網(wǎng)絡(luò)中最終影響范圍最大的k個節(jié)點[8]。目前，典型的研究成果主要包括基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的啟發(fā)式算法和基于傳播的貪心算法[5]。

基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的啟發(fā)式算法中，最簡單的方法就是直接選擇如度和介數(shù)的網(wǎng)絡(luò)中心性度量指標(biāo)的top-k節(jié)點[4]，但此類指標(biāo)所選節(jié)點可能是高度聚集的，易出現(xiàn)“富人俱樂部效應(yīng)”，準確性較低，對此，Holme等人[9]進行了輕微的改進。Chen等人[10]提出了適應(yīng)性重新計算的度指標(biāo)的改進算法DegreeDiscount，在提高執(zhí)行精度的同時，達到了比最快的貪心算法快100萬倍的運行速度[4]。Kitsak等人[11]提出了作為節(jié)點傳播影響的核心度（coreness）指標(biāo)，在網(wǎng)絡(luò)中通過使用k-核分解[12]來獲得節(jié)點的影響力。該指標(biāo)具有較低的時間復(fù)雜度，已被許多真實的網(wǎng)絡(luò)所采用[11,13-14]，遺憾的是在樹型網(wǎng)絡(luò)中所有節(jié)點的coreness值都非常小，造成節(jié)點影響力大小難以區(qū)分，以及coreness指標(biāo)的高度粗粒度會導(dǎo)致出現(xiàn)許多具有相同coreness值的不可辨別的節(jié)點[4]。特征向量中心性指標(biāo)的提出是對節(jié)點影響力研究的進一步深入，揭示了節(jié)點的影響力不僅受鄰居節(jié)點的數(shù)量影響，還與鄰居節(jié)點的影響力大小有關(guān)，基于該理論的代表性變體算法有 PageRank[15-16]、HITs（hyperlink-induced topic search）[17]、SALSA（stochastic approach for link-structure analysis）[18]等。相關(guān)算法還有 ClusterRank[19]，不僅考慮最近鄰居的數(shù)量，還考慮網(wǎng)絡(luò)中節(jié)點間的聚類信息。Zhang等人[20]設(shè)計了在SIR模型上的仿真實驗結(jié)果表現(xiàn)好于ClusterRank和coreness[11]的VoteRank算法。最近，Morone和Makse在隨機網(wǎng)絡(luò)上基于滲透方法提出了時間復(fù)雜度較低的集體影響（collective influence，CI）算法[7]，其通過在最優(yōu)滲透模型中識別出最小數(shù)量的節(jié)點集使網(wǎng)絡(luò)崩潰瓦解。該算法根據(jù)破壞性等價于節(jié)點影響力大小的思想，僅從系統(tǒng)科學(xué)角度識別出破壞網(wǎng)絡(luò)連通性的最小節(jié)點集，首次揭示了網(wǎng)絡(luò)中的部分弱連接的低度節(jié)點體現(xiàn)出強大的影響力。

基于傳播的貪心算法將影響最大化問題作為離散組合優(yōu)化問題，利用貪心策略實現(xiàn)近似的最優(yōu)解[5]。這類算法的主要思想是：從一個空的影響力節(jié)點集開始，每輪迭代地把當(dāng)前最具影響力的節(jié)點加入影響力節(jié)點集，最終得到規(guī)模為k的影響力節(jié)點集。2003年，Kempe等人[21]首次證明了影響最大化問題在獨立級聯(lián)模型和線性閾值模型上都為NP-hard問題，并且設(shè)計出具有1-1/e最優(yōu)解近似比的原始貪心算法。原始貪心算法雖簡單，但是在每次迭代選擇種子節(jié)點的過程中都需要進行大量的蒙特卡洛模擬來估計影響范圍，造成運行效率非常低[22]。為了精簡計算，Leskovec等人[23]根據(jù)影響擴散的子模性質(zhì)來避免影響范圍的冗余計算，提出了CELF（cost-effective lazy-forward）算法，使算法精度在保證與原始貪心算法一致的前提下，比原始貪心算法的執(zhí)行效率快了700倍[4,22]。Goyal等人[24]設(shè)計出算法復(fù)雜度略優(yōu)于CELF算法，運行時間卻縮短了35%~55%的CELF++算法。Chen等人[10]基于原始貪心算法提出了New-Greedy算法和MixGreedy算法。其中NewGreedy算法在級聯(lián)模型上通過遍歷整個網(wǎng)絡(luò)去除一些邊之后形成的小網(wǎng)絡(luò)上進行影響力的傳播，其運行速率相比于CELF[23]算法提高了15%~34%。MixGreedy算法是一種改進的混合貪心優(yōu)化算法，首先運用New-Greedy算法選擇第一個節(jié)點，然后用CELF[23]算法選擇剩余節(jié)點實現(xiàn)了對原始貪心算法的優(yōu)化。然而，這類基于傳播的算法復(fù)雜度普遍較高，在大規(guī)模網(wǎng)絡(luò)問題求解中無法適用[25-26]。

綜上，在復(fù)雜網(wǎng)絡(luò)影響力節(jié)點識別這一課題的研究中，為了解決現(xiàn)有影響最大化方法多數(shù)不能兼顧時間復(fù)雜度和精度的這一矛盾，本文考慮到網(wǎng)絡(luò)中節(jié)點間的相互作用，創(chuàng)新性地提出了局部集體影響指標(biāo)，并在此基礎(chǔ)上設(shè)計出影響力節(jié)點識別的局部集體影響排序算法以及基于局部集體影響的自適應(yīng)排序算法，來實現(xiàn)網(wǎng)絡(luò)中發(fā)揮重要作用和功能的影響力節(jié)點的有效查找。

3 問題描述與基本方法介紹

問題定義：給定網(wǎng)絡(luò)G(V,E)，其中V和E分別代表節(jié)點集和邊集，n和m分別表示網(wǎng)絡(luò)G中節(jié)點和邊的數(shù)量。如果存在函數(shù)f(S)是子集S(S?V)的影響節(jié)點集合，則影響最大化問題（influence maximization problem，IMP）為找到給定大小k（通常為k?n）的子集S使得f最大化。其中k表示要選擇影響力節(jié)點（種子節(jié)點）的數(shù)量[4]。

3.1 基本方法介紹

至今，許多不同背景下的影響力節(jié)點識別方法已被提出。本文對6種經(jīng)典的影響力節(jié)點識別算法進行簡要介紹，包括接近度中心性[4]、DegreeDiscount算法[10]、K-核算法[12]、PageRank 算法[15-16]、NewGreedy算法[10]以及CI算法[7]，它們也將用作后續(xù)實驗研究中的基準算法。

接近度中心性（closeness centrality，CC）[4]，在一個相通的網(wǎng)絡(luò)G中，一個節(jié)點i的接近度中心性被定義為從節(jié)點i到網(wǎng)絡(luò)中所有其他節(jié)點的最短距離平均值的倒數(shù)，即：

其中，dij為節(jié)點i與節(jié)點j間的最短距離。由于節(jié)點對之間不連通時，會導(dǎo)致dij=∞，本文采用根據(jù)節(jié)點間的距離倒數(shù)的調(diào)和平均值來表示接近度中心性，即：

很顯然，接近度指標(biāo)越大，節(jié)點越處于網(wǎng)絡(luò)中心的位置，影響力就越大。

DegreeDiscount算法[10]是基于自適應(yīng)重新計算思想對網(wǎng)絡(luò)中MaxDegree[21]算法的一種改進，在Degree-Discount算法中以貢獻大小為依據(jù)來替代MaxDegree算法中的度值。首先，對網(wǎng)絡(luò)G中的任意節(jié)點x計算出其度中心性值，即度值dx，定義為網(wǎng)絡(luò)G中節(jié)點x的鄰居節(jié)點的數(shù)量。假設(shè)該最大值對應(yīng)的節(jié)點為u，即種子節(jié)點，v是節(jié)點u的鄰居節(jié)點。然后，在對節(jié)點v的貢獻值dv′進行計算時，由其度值dv減去其鄰居集合所含其他種子節(jié)點個數(shù)tv，即dv′=dv-tv。這一過程也被稱為SingleDiscount算法。最后，根據(jù)DegreeDiscount算法的折扣準則，選擇種子節(jié)點。即每次選擇上一步打折計算后貢獻最大的節(jié)點加入種子節(jié)點集合，但當(dāng)所選節(jié)點是種子節(jié)點的鄰居節(jié)點時，考慮到種子節(jié)點u會對其鄰居節(jié)點v產(chǎn)生影響，則不被加入。

K-核算法[12]的主要思想基于核心度，即位于網(wǎng)絡(luò)核心部分的節(jié)點的影響力要高于邊緣節(jié)點。算法分解流程如下：設(shè)網(wǎng)絡(luò)的孤立節(jié)點的核心度為0，首先把孤立節(jié)點從網(wǎng)絡(luò)中去除，接著進行K-核分解。第一步，把所有核心度為1的節(jié)點從網(wǎng)絡(luò)中移除，之后繼續(xù)移除剩余度小于等于1的節(jié)點，直到網(wǎng)絡(luò)中所有剩余節(jié)點的剩余度都大于1為止。在該步中所有移除的節(jié)點為1-核節(jié)點，其核心度都等于1。第二步，首先移除剩余度等于2的節(jié)點，然后繼續(xù)移除當(dāng)前剩余度不大于2的節(jié)點，直到網(wǎng)絡(luò)中所有剩余節(jié)點的剩余度大于2為止。第二步中所有刪除的節(jié)點為2-核節(jié)點，其核心度都等于2。以此類推，直到網(wǎng)絡(luò)中所有的節(jié)點都被移除。顯然，較大核心度的節(jié)點意味著位于網(wǎng)絡(luò)更中心的位置，有更大的影響力。

PageRank算法[15-16]最初用于Google搜索引擎中網(wǎng)頁影響力大小的評定，通過在網(wǎng)絡(luò)上隨機游走來構(gòu)建網(wǎng)頁之間的關(guān)系，從而區(qū)分不同網(wǎng)頁的重要性。算法設(shè)計如下：假設(shè)網(wǎng)頁的影響力與鏈接網(wǎng)頁的數(shù)量和質(zhì)量有關(guān)，首先為網(wǎng)絡(luò)中的所有節(jié)點（即網(wǎng)頁）預(yù)設(shè)一個PR值，然后每個節(jié)點沿著出度方向?qū)R值均勻地分配給其鄰居節(jié)點，在t時間步長節(jié)點i的PR值為：

其中，n為網(wǎng)絡(luò)節(jié)點數(shù)量；koutj為節(jié)點j的出度；z為上網(wǎng)者瀏覽網(wǎng)頁概率跳躍因子，一般取0.85。

NewGreedy算法[10]是為了縮短原始貪心算法GeneralGreedy的執(zhí)行時間而提出的改進算法。該算法通過每輪遍歷整個網(wǎng)絡(luò)圖，以一定的概率刪除原圖的一些邊形成較小子圖，然后在子圖上進行影響力傳播。

集體影響（CI）算法[7]定義Ball(i,l)為圍繞節(jié)點i，且屬于半徑（最短路徑）l的球內(nèi)的節(jié)點集合，?Ball(i,l)為該球的邊界，那么節(jié)點i在l層所獲得的集體影響強度，即CI值為：

其中，di是節(jié)點i的度；l是預(yù)定義的不超過有限網(wǎng)絡(luò)直徑的非負整數(shù)，在大中型網(wǎng)絡(luò)中一般取3或4，在小網(wǎng)絡(luò)中取2。算法流程如下：首先，基于整個網(wǎng)絡(luò)計算所有節(jié)點的CIl值，把CIl值最大的節(jié)點從網(wǎng)絡(luò)中移除。然后，重新計算網(wǎng)絡(luò)中最大連通分量所包含節(jié)點的CIl值，并且繼續(xù)將新的CIl值最大的節(jié)點從網(wǎng)絡(luò)中移除，重復(fù)該過程直到網(wǎng)絡(luò)中的最大連通分量消失，算法結(jié)束。

3.2 傳播模型及破壞性實驗

信息的發(fā)布、分享和擴散是網(wǎng)絡(luò)環(huán)境中最主要的交互活動，而節(jié)點的影響力在社會網(wǎng)絡(luò)中的作用過程機理類似于信息的擴散過程，二者之間存在著緊密的聯(lián)系。因此傳播模型在影響力傳播問題的研究過程中發(fā)揮著至關(guān)重要的作用，是對信息傳播過程進行建模的有效方法。而網(wǎng)絡(luò)破壞性實驗同樣是通過觀察網(wǎng)絡(luò)的破壞性來衡量影響力節(jié)點識別算法有效性的一種常用策略。以下就廣泛使用的獨立級聯(lián)模型[27]以及網(wǎng)絡(luò)破壞性實驗進行簡要介紹。

3.2.1 獨立級聯(lián)模型

獨立級聯(lián)模型[28-29]為廣泛使用的信息理論傳播模型。對于給定的網(wǎng)絡(luò)G，網(wǎng)絡(luò)中節(jié)點的狀態(tài)分為激活狀態(tài)和未激活狀態(tài)?，F(xiàn)在t時刻網(wǎng)絡(luò)中某一節(jié)點u與其鄰居節(jié)點v存在一條邊e(u,v)，節(jié)點u成功激活節(jié)點v的概率為Puv∈[0,1]，對t+1時刻，任何一個當(dāng)t時刻處在激活狀態(tài)的節(jié)點u有且僅有一次機會去激活它所有處在未激活狀態(tài)的鄰居節(jié)點v。如果節(jié)點v被成功激活，v將在t+2時刻繼續(xù)嘗試去激活其鄰居中處于未激活狀態(tài)的節(jié)點，否則節(jié)點v保持未激活狀態(tài)。重復(fù)以上過程直到網(wǎng)絡(luò)中沒有新的節(jié)點繼續(xù)被激活。這一激活過程最初開始于少數(shù)處于激活狀態(tài)的種子節(jié)點，影響力的傳播范圍與成功激活概率Puv有關(guān)。為了保證該過程實驗結(jié)果的準確性，將大量模擬過程傳播結(jié)果的平均值作為種子節(jié)點最終影響力。

3.2.2 網(wǎng)絡(luò)破壞性實驗

鑒于許多真實的網(wǎng)絡(luò)有著嚴重的異質(zhì)性，會對網(wǎng)絡(luò)抗毀性產(chǎn)生極大的影響，本文運用選擇性攻擊的打擊策略進行網(wǎng)絡(luò)抗毀性實驗，根據(jù)影響力節(jié)點識別算法識別出節(jié)點集中節(jié)點的前后順序進行節(jié)點移除，通過觀察網(wǎng)絡(luò)的破壞性來衡量影響力節(jié)點識別算法的有效性。網(wǎng)絡(luò)的破壞性[30]通過網(wǎng)絡(luò)巨型連通分量的規(guī)模與網(wǎng)絡(luò)的節(jié)點規(guī)模的比值來計算，即：

其中，g為網(wǎng)絡(luò)中的巨型連通分量的規(guī)模；n為網(wǎng)絡(luò)節(jié)點的規(guī)模。移除某節(jié)點，α值越小，說明網(wǎng)絡(luò)巨型連通分量破壞越大，則該節(jié)點越重要，相應(yīng)的算法更有效。

4 基于局部集體影響自適應(yīng)排序算法

CI算法容易實現(xiàn)，有良好的擴展性，是影響最大化領(lǐng)域最先進的算法之一。其對網(wǎng)絡(luò)破壞的有效性，眾多實驗大都從系統(tǒng)科學(xué)角度進行證實[7]。由于CI算法考慮了影響力節(jié)點與l層鄰居節(jié)點的相互作用，展示出基于拓撲結(jié)構(gòu)中心性等算法不可企及的穩(wěn)定性，同時揭示出在網(wǎng)絡(luò)上扮演主要經(jīng)紀人角色的低度節(jié)點的強大影響力。不可否認，此思想的引入對于復(fù)雜網(wǎng)絡(luò)中影響力節(jié)點的識別研究，尤其對低度影響力節(jié)點的識別有不可估量的意義。然而，從社會網(wǎng)絡(luò)分析角度來看，該算法在獨立級聯(lián)模型等傳播模型上的實驗效果還有待提高，并且每輪只從新計算網(wǎng)絡(luò)節(jié)點中取出一個CI指標(biāo)值最大的影響力節(jié)點，該過程的時間復(fù)雜度為O(NlbN)，則取出k個影響力節(jié)點的最終時間復(fù)雜度為O(kNlbN)。這對于大規(guī)模網(wǎng)絡(luò)，效率優(yōu)勢并不十分明顯?；诖?，本文提出了傳播精度高且時間復(fù)雜度較低的基于局部集體影響自適應(yīng)排序算法LCIR-AR，很好地解決了基于網(wǎng)絡(luò)結(jié)構(gòu)中心性算法影響范圍不穩(wěn)定的問題。

4.1 局部集體影響指標(biāo)

考慮到網(wǎng)絡(luò)中節(jié)點間的相互作用，引入了CI指標(biāo)，并創(chuàng)新性地提出了局部集體影響指標(biāo)（LCII），其設(shè)計思想是對于由給定網(wǎng)絡(luò)G中的任意節(jié)點i及其鄰居形成的局部網(wǎng)絡(luò)環(huán)境，統(tǒng)計該環(huán)境中CI值大于節(jié)點i的CI值的節(jié)點個數(shù)，形式化定義為：

其中，N(i)表示節(jié)點i鄰居節(jié)點的集合。

例如，如果節(jié)點i的LCII值為5，則表明節(jié)點i周圍有5個鄰居節(jié)點的CI值高于節(jié)點i。根據(jù)LCII指標(biāo)的定義，可能會出現(xiàn)互為鄰居的兩個節(jié)點的LCII值相等的情況，如兩個相鄰的節(jié)點同時擁有最大的CI值，這兩節(jié)點的LCII值則同時為0。

4.2 LCIR算法

局部集體影響排序算法（LCIR）的基本思想是選擇出LCII(i)=0的節(jié)點，這樣不但保證選出的影響力節(jié)點在其鄰域局部網(wǎng)絡(luò)中為CI值最大的節(jié)點，而且有效避免了影響傳播的重疊。該算法的基本流程如下：首先，以網(wǎng)絡(luò)中任意節(jié)點i為根節(jié)點，廣度遍歷或者深度遍歷l層所有鄰居節(jié)點，其中l(wèi)為距離節(jié)點i的最短路徑。然后，計算節(jié)點i的CI值及其LCII值，并將LCII值為0的節(jié)點添加到影響力節(jié)點集。最后，根據(jù)節(jié)點CI值對影響力節(jié)點集進行排序，選擇出top-k的影響力節(jié)點。具體描述如算法1所示。

算法1LCIR算法

一般地，LCIR算法可以保證選擇出的節(jié)點為高CI值且相對分散的多個影響力節(jié)點，從而實現(xiàn)在網(wǎng)絡(luò)中更加廣泛的傳播范圍。真實世界的網(wǎng)絡(luò)通常是十分龐大和稀疏的，點數(shù)目和邊數(shù)目的關(guān)系為m=O(n)。就其時間復(fù)雜度而言，利用廣度搜索找出距離某節(jié)點i的最短路徑為l的鄰居節(jié)點，并計算其CI值的時間復(fù)雜度為O(×(-1)l-1)，即O(1)。其中為網(wǎng)絡(luò)節(jié)點的平均度。對于網(wǎng)絡(luò)中每個節(jié)點都執(zhí)行同樣的操作，這部分的時間復(fù)雜度為O(N)。計算各節(jié)點LCII值以及找出LCII=0的節(jié)點的時間復(fù)雜度為O(N)。最后，對所選節(jié)點集合S根據(jù)CI值排序的時間復(fù)雜度為O(KlbK)(K=|S|)，則該算法的最終時間復(fù)雜度為O(N+N+KlbK)=O(N)，相對CI算法有了一定程度的降低。

用一個簡單的樣本網(wǎng)絡(luò)來說明LCIR算法和CI算法的差異，如圖1，（a）和（b）中灰色節(jié)點分別表示通過CI算法和LCIR算法選取的影響力節(jié)點及其鄰居節(jié)點。假定要選取的影響力節(jié)點個數(shù)k=2，CI算法中取l=2，則完成該任務(wù)需要兩輪。第一輪，計算所有節(jié)點的CI值，選擇出CI值最大的節(jié)點14；第二輪，把節(jié)點14從網(wǎng)絡(luò)中移除，重新計算當(dāng)前所有節(jié)點的CI值，選出當(dāng)前CI值最大的節(jié)點15。如果使用LCIR算法，同樣令l=2，計算出所有節(jié)點的LCCI值，選擇LCII值為0且按CI值排序后的top-2節(jié)點為1和14。在IC模型中令激活概率p=0.25，迭代次數(shù)為10 000時，模擬出節(jié)點1、節(jié)點14、節(jié)點15分別單獨可以激活該網(wǎng)絡(luò)中6、6、9個節(jié)點?？紤]到兩個影響力節(jié)點的共同作用效果，CI算法選出的節(jié)點14和節(jié)點15可以激活網(wǎng)絡(luò)中11個節(jié)點，而LCIR算法選取的節(jié)點1和節(jié)點14可以激活網(wǎng)絡(luò)中12個節(jié)點，效果略好于CI算法，但從激活節(jié)點的分布來看，該算法有效避免了影響力傳播重疊的現(xiàn)象。同時LCIR算法只需執(zhí)行一輪就可以選出兩個影響力節(jié)點，執(zhí)行效率比CI算法也有所提高。最后，圖中節(jié)點1、節(jié)點14、節(jié)點15的度分別為9、17、13，節(jié)點1是節(jié)點14和節(jié)點15的l=2層的鄰居節(jié)點，扮演了重要的經(jīng)紀人角色。在IC模型中，如上分析，低度節(jié)點1的激活能力卻和節(jié)點14的激活能力相當(dāng)，進一步肯定了LCIR算法在發(fā)現(xiàn)具有強大影響力的扮演經(jīng)紀人角色的低度節(jié)點上的優(yōu)勢。

Fig.1 Comparison of LCIR algorithm and CI algorithm in a simple sample network圖1 LCIR算法和CI算法在簡單樣本網(wǎng)絡(luò)中的差異

然而，LCIR算法也有一定的局限性，其所選取影響力節(jié)點的數(shù)目與網(wǎng)絡(luò)的異質(zhì)性有關(guān)，在某些經(jīng)典的網(wǎng)絡(luò)（如樹型網(wǎng)絡(luò)），可能選取的影響力節(jié)點集合較小，難以在實際應(yīng)用中發(fā)揮作用。

4.3LCIR-AR算法

針對LCIR算法的不足，對其進行改進，引入影響力節(jié)點候選集的思路以及自適應(yīng)重新計算的方法，提出基于局部集體影響的自適應(yīng)排序算法（LCIRAR）。算法框架如圖2所示，虛線框中流程表示LCIR原始算法流程，實線框中流程則為LCIR-AR算法流程，圖中顯示出兩者的聯(lián)系。

LCIR-AR算法的基本流程為：第一步，利用LCIR算法選出未進行排序的影響力節(jié)點加入影響力節(jié)點候選集。第二步，在網(wǎng)絡(luò)G中移除這些已經(jīng)被加入影響力節(jié)點候選集的節(jié)點，然后繼續(xù)利用LCIR算法在被修改的網(wǎng)絡(luò)中識別影響力節(jié)點加入影響力節(jié)點候選集。重復(fù)以上步驟直到節(jié)點候選集的規(guī)模達到h=k/λ時，算法終止。其中，λ∈(0,1]為該算法中引入的控制參數(shù)，這個參數(shù)可以在一定范圍控制影響力節(jié)點選取的精度和執(zhí)行效率。具體描述如算法2。其中，利用LCIR算法選擇規(guī)模為k的影響力節(jié)點集需要的時間復(fù)雜度為O(cN)，參數(shù)c(c?k)為執(zhí)行輪數(shù)，對最終結(jié)果集根據(jù)CI值排序的時間復(fù)雜度為O(hlbh)，因此該算法的時間復(fù)雜度為O(cN+hlbh)。不難發(fā)現(xiàn)，c的大小由λ決定，一般來講，λ越大，c值越小，相比于其他執(zhí)行k輪的算法，該算法的效率優(yōu)勢就越明顯，當(dāng)λ=1時，該算法退化為LCIR算法。為了同時保障LCIR-AR算法的精度，本文λ取0.3。

算法2LCIR-AR算法

Fig.2 Algorithm framework圖2 算法框架

5 實驗與結(jié)果分析

本文選取4個真實網(wǎng)絡(luò)數(shù)據(jù)集進行實驗。實驗的硬件環(huán)境為2.50 GHz Intel?CoreTMi5-3210 CPU，4 GB的內(nèi)存。操作系統(tǒng)為ubantu 12.04。開發(fā)環(huán)境及語言為python 2.7。數(shù)據(jù)集為：（1）Political blogs[30]，美國政治博客之間的超鏈接網(wǎng)絡(luò)；（2）USAairports[31]，2010年在美國機場之間的定向航班網(wǎng)絡(luò)；（3）Yeast[32]，蛋白質(zhì)交互網(wǎng)絡(luò)；（4）Facebook[33]，F(xiàn)acebook 社交網(wǎng)絡(luò)。各數(shù)據(jù)集的基本拓撲特征信息如表1，依次為節(jié)點數(shù)（n）、邊數(shù)（m）、平均度（ ）、最大度（dmax）、聚類系數(shù)（C）、節(jié)點度分布的異質(zhì)性系數(shù)（H）[34]及網(wǎng)絡(luò)類型。其中H=/2。

Table 1 Basic topological features of 4 real datasets表1 4個真實數(shù)據(jù)集的基本拓撲特征

本文使用IC模型和網(wǎng)絡(luò)的破壞性來模擬現(xiàn)實世界中傳播的影響，并選擇 CC[4]、K-核[12]、Degree-Discount[10]、NewGreedy[10]、PageRank[15-16]及 CI[7]共 6 個標(biāo)志性算法進行對比。其中NewGreedy、PageRank是運行時間和影響傳播的最佳傳播算法，Degree-Discount是最先進的基于拓撲的算法，CI算法為系統(tǒng)科學(xué)角度移除最少數(shù)量節(jié)點使網(wǎng)絡(luò)癱瘓的算法。根據(jù)網(wǎng)絡(luò)數(shù)據(jù)集的規(guī)模，設(shè)置Political blogs、USA airports、Yeast的影響力節(jié)點集規(guī)模k=30，F(xiàn)acebook的影響力節(jié)點集規(guī)模k=50。

在IC模型中，考慮到當(dāng)傳播概率P>0.1時，影響擴散的差異幾乎消失，大的傳播概率對不同的算法并不敏感，因此不被采用。為了測試概率P的敏感性，表2描繪了7種算法在Political blogs、USAairports、Yeast、Facebook數(shù)據(jù)集上，分別對應(yīng)于P∈[0.015,0.032],[0.005,0.022],[0.005,0.022],[0.010,0.027]，所選影響力節(jié)點集平均影響范圍的實驗結(jié)果。對于該節(jié)點集的影響范圍隨概率P的變化效果如圖3所示。其中，影響范圍為10 000次實驗的平均值。

Table 2 Average influence range of 7 algorithms in 4 real data sets表2 7種算法在4個真實數(shù)據(jù)集的平均影響范圍

分析圖3可知，LCIR-AR算法在影響范圍的精度指標(biāo)上普遍超過PageRank、K-核、NewGreedy、Degree-Discount、CC等算法，充分說明了該算法的有效性。如在圖3（a）中，LCIR-AR算法在精度上平均分別優(yōu)于 PageRank、K-核、NewGreedy、DegreeDiscount、CC算法2.73%、5.46%、2.54%、7.55%、2.54%，圖3（b）中，分別高達8.07%、14.40%、9.90%、8.90%、12.86%。其次，DegreeDiscount算法在4個數(shù)據(jù)集上的表現(xiàn)差異顯示出其傳播的不穩(wěn)定性。如在圖3（a）和（c）中，DegreeDiscount算法的表現(xiàn)僅次于LCIR-AR算法，圖3（b）中當(dāng)概率P∈(0.08,0.22)時表現(xiàn)次于LCIR-AR和PageRank算法，在圖3（d）中表現(xiàn)出中流水平。再者，相比于CI算法，4個數(shù)據(jù)集上LCIR-AR算法傳播能力的影響范圍分別提高35.95%、60.33%、15.78%和11.58%，肯定了該算法在解決CI算法傳播重疊問題上的可行性。最后，不難看出當(dāng)P=0.02，在圖3的4個數(shù)據(jù)集中各算法都有較好表現(xiàn)。為了使分析結(jié)果更加清晰，給出P=0.02時各算法在不同top-k下的影響范圍如圖4，其中（a）、（b）、（c）、（d）分別對應(yīng)Political blogs、USAairports、Yeast、Facebook數(shù)據(jù)集。

Fig.3 Influence scope of 7 algorithms under different propagation probabilityP圖3 7種算法在不同傳播概率P下的影響范圍

由圖4（a）和（b）的實驗結(jié)果可以看出，LCIR-AR算法在top-10的影響力節(jié)點集的影響范圍雖然次于個別對比算法，但隨著k的增大，其算法性能漸增，所選節(jié)點集的影響范圍的增長率遠超過其他算法，當(dāng)k超過15時，在兩個數(shù)據(jù)集上都取得了絕對領(lǐng)先的優(yōu)勢。在圖4（c）和（d）中，LCIR-AR算法的實驗效果一直穩(wěn)定地高于其他對比算法，且PangRank算法在圖4（c）Yeast數(shù)據(jù)集中顯示出極大的波動?？傮w而言，LCIR-AR算法不是針對單個影響力節(jié)點而設(shè)計的，而是針對一組影響力節(jié)點而設(shè)計的。實驗結(jié)果顯示在一定范圍內(nèi)，隨著k值的增長，LCIR-AR算法所選節(jié)點集的影響范圍增長明顯，證明了其在本領(lǐng)域具有一定的競爭力。

IC模型是從網(wǎng)絡(luò)科學(xué)的角度評估各算法的有效性，以下是從系統(tǒng)科學(xué)衡量節(jié)點影響力大小的角度通過網(wǎng)絡(luò)破壞性實驗來比較LCIR-AR和CI算法的性能。如圖 5，（a）、（b）、（c）、（d）分別表示 Political blogs、USA airports、Yeast、Facebook數(shù)據(jù)集的實驗結(jié)果，網(wǎng)絡(luò)破壞性指標(biāo)顯示了LCIR-AR算法選取出的影響力節(jié)點比CI算法更有破壞力。綜合時間復(fù)雜度進行考慮，總體來說，LCIR-AR算法在精度和時間復(fù)雜度方面取得了良好的權(quán)衡，在一組影響力識別研究領(lǐng)域具有一定的先進性。

6 結(jié)束語

復(fù)雜網(wǎng)絡(luò)中識別一組影響力節(jié)點，即求解影響最大化問題是領(lǐng)域內(nèi)研究的熱點與挑戰(zhàn)。本文考慮到節(jié)點間的相互作用，引入集體影響指標(biāo)，并在其基礎(chǔ)上創(chuàng)新性地提出了LCII指標(biāo)及LCIR-AR算法。不同類型的真實數(shù)據(jù)集上的實驗結(jié)果，有效證明了本文算法的競爭力，不僅所選節(jié)點的影響力的傳播更加穩(wěn)定，而且有效避免了重疊傳播的現(xiàn)象，同時實現(xiàn)了算法精度和時間復(fù)雜度的良好平衡。

Fig.4 Influence scope of 7 algorithms in different top-k圖4 7種算法在不同top-k下的影響范圍

Fig.5 Network destructive experiment圖5 網(wǎng)絡(luò)破壞性實驗

近年來，在實際生活應(yīng)用場景中對一組影響力節(jié)點的信息挖掘顯現(xiàn)出明顯的需求，如何把目前新型的影響力節(jié)點識別算法應(yīng)用到實際場景以及為一些新型網(wǎng)絡(luò)如空間、時間和多層網(wǎng)絡(luò)等設(shè)計更加高效可行的方法，將是下一步的研究任務(wù)。

:

[1]Klemm K,Serrano M á,Eguíluz V M,et al.A measure of individual role in collective dynamics[J].Scientific Reports,2012,2:292.

[2]Castellano C,Pastor-Satorras R.Competing activation mechanisms in epidemics on networks[J].Scientific Reports,2012,2:371.

[3]Wang Junyi,Hou Xiaoni,Li Kezan,et al.A novel weight neighborhood centrality algorithm for identifying influential spreaders in complex networks[J].Physica A:Statistical Mechanics and ItsApplications,2017,475:88-105.

[4]Lv Linyuan,Chen Duanbing,Ren Xiaolong,et al.Vital nodes identification in complex networks[J].Physics Reports,2016,650:1-63.

[5]Zhao Yuxin,Li Shenghong,Jin Feng.Identification of influential nodes in social networks with community structure based on label propagation[J].Neurocomputing,2016,210:34-44.

[6]Ma Qian.Research on node influence measurement andknodes influence maximization problem in social networks[D].Jinan:Shandong University,2017.

[7]Morone F,Makse H A.Influence maximization in complex networks through optimal percolation[J].Nature,2015,527(7579):544.

[8]Li Zhihui,Zhang Zhaogong,Li Jianzhong.Research on algorithms for selecting minimum seed set on location-aware social networks[J].Chinese Journal of Computers,2017,40(10):2305-2319.

[9]Holme P,Kim B J,Yoon C N,et al.Attack vulnerability of complex networks[J].Physical Review E,2002,65(5):056109.

[10]Chen Wei,Wang Yajun,Yang Siyu.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,Jun 28-Jul 1,2009.New York:ACM,2009:199-208.

[11]Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2012,6(11):888-893.

[12]Dorogovtsev S N,GoltsevAV,Mendes J F.k-core organization of complex networks[J].Physical Review Letters,2006,96(4):040601.

[13]Zeng An,Zhang C J.Ranking spreaders by decomposing complex networks[J].Physics Letters A,2013,377(14):1031-1035.

[14]Pei Sen,Muchnik L,Jr J S A,et al.Searching for superspreaders of information in real-world social media[J].Scientific Reports,2014,4:5547.

[15]Sehgal U,Kaur K,Kumar P.The anatomy of a large-scale hyper textual Web search engine[C]//Proceedings of the 2nd International Conference on Computer and Electrical Engineering,Dubai,Dec 28-30,2009.Washington:IEEE Computer Society,2009:491-495.

[16]Langville A N,Meyer C D.Google’s PageRank and Beyond:the science of search engine rankings[M].Princeton:Princeton University Press,2011.

[17]Lempel R,Moran S.The stochastic approach for link-structure analysis(SALSA)and the TKC effect[J].Computer Networks,2000,33(1):387-401.

[18]Lempel R,Moran S.SALSA:the stochastic approach for link-structure analysis[J].ACM Transactions on Information Systems,2001,19(2):131-160.

[19]Chen Duanbing,Gao Hui,Lv Linyuan,et al.Identifying influential nodes in large-scale directed networks:the role of clustering[J].PLOS One,2013,8(10):e77455.

[20]Zhang Jianxiong,Chen Duanbing,Dong Qiang,et al.Identifying a set of influential spreaders in complex networks[J].Scientific Reports,2016,6:27823.

[21]Kempe D,Kleinberg J,Tardos é.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27,2003.New York:ACM,2003:137-146.

[22]Xie Shengnan,Liu Yong,Zhu Jinghua,et al.Research on topic-based local influence maximization algorithm in social network[J].Journal of Frontiers of Computer Science and Technology,2016,10(5):646-656.

[23]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,Aug 12-15,2007.New York:ACM,2007:420-429.

[24]Goyal A,Lu Wei,Lakshmanan L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of the 20th International Conference on World Wide Web,Hyderabad,Mar 28-Apr 1,2011.New York:ACM,2011:47-48.

[25]Hu Qingcheng,Zhang Yong,Xu Xinhui,et al.A new approach for influence maximization in complex networks[J].Acta Physica Sinica,2015,64(19):19-30.

[26]Liu Dong,Jing Yun,Zhao Jing,et al.A fast and efficient algorithm for mining top-knodes in complex networks[J].Scientific Reports,2017,7:43330.

[27]Goldenberg J,Libai B,Muller E.Talk of the network:a complex systems look at the underlying process of word-ofmouth[J].Marketing Letters,2001,12(3):211-223.

[28]Leskovec J,Krause A,Guestrin C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Jose,Aug 12-15,2007.New York:ACM,2007:420-429.

[29]Guo Jing.Analysis and mining research on influence propagation in social network[D].Beijing:Beijing University of Posts and Telecommunications,2014.

[30]Adamic L A,Glance N.The political blogosphere and the 2004 US election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery,Chicago,Aug 21-25,2005.New York:ACM,2005:36-43.

[31]Liu Yang,Ji Xinsheng,Liu Caixia.Detecting local community structure based on the identification of boundary nodes in complex networks[J].Journal of Electronics&Information Technology,2014,36(12):2809-2815.

[32]Von M C,Krause R,Snel B,et al.Comparative assessment of large-scale data sets of protein-protein interactions[J].Nature,2002,417(6887):399-403.

[33]McAuley J,Leskovec J.Learning to discover social circles in ego networks[C]//Proceedings of the 25th International Conference on Neural Information Processing Systems,Lake Tahoe,Dec 3-6,2012.Red Hook:Curran Associates,2012:539-547.

[34]Leskovec J,Adamic L A,Huberman B A.The dynamics of viral marketing[J].ACM Transactions on the Web,2007,1(1):5.

附中文參考文獻：

[6]馬茜.社會網(wǎng)絡(luò)中的節(jié)點影響力度量和k-節(jié)點集的影響力最大化問題研究[D].濟南:山東大學(xué),2017.

[8]李智慧,張兆功,李建中.位置敏感的社交網(wǎng)中最小種集選取算法研究[J].計算機學(xué)報,2017,40(10):2305-2319.

[22]謝勝男,劉勇,朱敬華,等.社會網(wǎng)中基于主題的局部影響最大化算法研究[J].計算機科學(xué)與探索,2016,10(5):646-656.

[25]胡慶成,張勇,許信輝,等.一種新的復(fù)雜網(wǎng)絡(luò)影響力最大化發(fā)現(xiàn)方法[J].物理學(xué)報,2015,64(19):19-30.

[29]郭靜.社交網(wǎng)絡(luò)影響力傳播的分析與挖掘研究[D].北京:北京郵電大學(xué),2014.

[31]劉陽,季新生,劉彩霞.一種基于邊界節(jié)點識別的復(fù)雜網(wǎng)絡(luò)局部社區(qū)發(fā)現(xiàn)算法[J].電子與信息學(xué)報,2014,36(12):2809-2815.