邊緣覆蓋去重的社交網絡影響力最大化算法*

胡 敏，孫欣然，黃宏程,2+

1.重慶郵電大學 通信與信息工程學院，重慶 400065

2.重慶大學 計算機學院，重慶 400044

邊緣覆蓋去重的社交網絡影響力最大化算法*

胡 敏1，孫欣然1，黃宏程1,2+

1.重慶郵電大學 通信與信息工程學院，重慶 400065

2.重慶大學 計算機學院，重慶 400044

社交網絡；影響力最大化；邊緣貢獻；啟發式算法

1 引言

人們因共同學習、生活、工作，形成了不同圈中的復雜社交關系，人與人在現實生活中的交往形成了線下的社交網絡，這便是復雜社交網絡的開端。隨著互聯網的普及和高速發展，人們獲取信息的方式和途徑從以前的報刊、雜志、電視等擴展到了互聯網之中，他們復雜的社會交往關系也從現實社會延伸到虛擬網絡之中，形成了線上的社交網絡。

Domingos等人[1]在2001年提出節點影響力最大化問題，之后該問題便得到了極大的關注。隨著社交網絡的興起，網絡監管與輿論引導控制變得越來越重要。此外，互聯網社交網絡中的用戶數激增，商家逐漸趨向于在社交網絡這個巨大的平臺上發布廣告信息，進行商品的推廣營銷。從根本上說，輿論引導和商品推廣是特定價值信息在社交網絡平臺上的最大范圍擴散，其中一個關鍵問題是如何選取網絡中這些信息傳播影響力最大的節點集，也就是影響力最大化問題，這也一直是研究的熱點和難點。

Kempe等人[2]提出爬山貪心算法Basic-greedy，這是針對節點影響力最大化問題最初始的解決方案。由于貪心算法的時間復雜度過高，不適用于大規模網絡。針對該問題，研究者對算法進行了改進優化[3-6]，提出了CELF（cost-effective lazy forward）、CELF++、New-greedy、Mix-greedy等算法。這些改進算法雖提高了時間效率，但對于大規模網絡仍然不能適用。為了研究大規模網絡中的節點影響力最大化問題，啟發式算法應運而生。啟發式算法通常具有運行時間短的特點，但算法準確度相對較差，傳播范圍相對較小。階段式算法是貪心算法與啟發式算法的綜合型算法[7-9]，通常在算法初始選取階段采用啟發式思想評估節點影響力，后續采用貪心算法細化選取。

社交網絡中通常節點數量多，關系連邊復雜，屬于大規模復雜網絡，貪心算法難以滿足目前大規模社交網絡的要求，因此本文采用啟發式算法的思想。針對啟發式算法中傳播影響范圍相對較小的問題，本文考慮節點全局結構信息和鄰近結構信息兩方面來評估節點影響力，發現并解決了邊緣節點影響范圍重合問題，提出了基于邊緣覆蓋去重的啟發式算法（edge cover algorithm，ECA）。

本文組織結構如下：第2章介紹了相關工作；第3章研究了基于邊緣覆蓋去重的影響力最大化算法；第4章給出了實驗結果及分析；第5章對本文工作進行總結。

2 相關工作

2.1 傳播模型

在尋找特定網絡中的影響力節點集時，需要借助相應的傳播模型。一般將社會網絡抽象為有向圖G(V,E)，將用戶抽象為節點，V表示網絡中所有節點的集合；將用戶之間的連接關系抽象為連邊，E表示網絡中所有連邊的集合。目前常用的傳播模型有線性閾值模型（linear threshold model，LT）[10]和獨立級聯模型（independent cascade model，IC）[11]。在這兩種模型中，網絡中的節點存在活躍或非活躍兩種狀態且只處于其中之一，節點可以從非活躍狀態轉變為活躍狀態，反之則不成立。本文選取獨立級聯模型作為傳播模型，并對其進行詳細介紹。

IC模型假設一個活躍節點嘗試激活其每個鄰居節點的機會有且只有一次，若激活失敗，則對其失去影響力，且每一次激活行為的激活概率相對獨立。假設A為初始活躍節點集，活躍節點的傳播規則如下：

（1）非活躍節點v的鄰居節點u在傳播的t時刻嘗試激活節點v，且u激活v的概率為pu,v。

（2）若v被激活，則v的v+1時刻轉換為活躍節點；反之，v的狀態不發生改變。

（3）不斷重復上述過程，當網絡中的活躍節點都沒有影響力時，傳播結束。

2.2 啟發式算法研究

基于Random、Degree、Centrality的算法[2]是啟發式算法最基本的算法。常見的權威算法包括陳衛等人提出的Degree-discount、基于最大影響力子樹的PMIA（prefix excluding maximum influence arborescence）啟發式[12]、基于有向無環圖的LDAG（labeled directed acyclic graph）啟發式[13]以及Jung等人提出的綜合效果最優的IRIE（influence ranking influence estimation）啟發式[14]等。很多人針對這些算法進行了改進，并且取得了更優的效果。2010年，Kitsak等人[15]提出了k-core算法來評估節點的傳播影響力，并且提出了基于覆蓋的最大核算法和最大度算法。2011年，Goyal等人[16]分析了LDAG算法的不足，針對LDAG算法中存在的影響力路徑忽略的問題進行改進，提出了基于節點影響力的簡單路徑SIMPATH啟發式算法。2015年，曹玖新等人[17]提出了一種基于 k-core的影響力最大化算法（core covering algorithm，CCA），算法結合k-core算法和度中心性求出每個節點的影響力，對節點的影響半徑（d=1和d=2）進行了討論。

相比于貪心算法，啟發式算法的求解時間具有較大優勢，但其算法準確度較差，因此提高算法準確度是啟發式算法研究的長期目標。

在以上提到的影響力最大化啟發式算法研究中忽略了影響范圍重合問題。一些考慮影響范圍重合的覆蓋類算法研究也并沒有考慮邊緣貢獻的問題。針對這一問題，本文在考慮邊緣貢獻的條件下研究了影響力最大化算法。

3 基于邊緣覆蓋去重的影響力最大化算法

本文采用啟發式算法的思想，在IC模型的基礎上，提出了基于邊緣覆蓋去重的啟發式算法ECA。該算法考慮節點全局結構信息和鄰近結構信息兩方面來評估節點影響力，并通過去除已選節點影響范圍內的所有節點的方式來屏蔽已選節點對未標記范圍內邊緣節點的影響，以此來除去節點之間的影響重合范圍。下面首先介紹構成ECA算法的評估單個節點影響力、去除邊緣節點影響力范圍重合兩部分，然后整體描述算法的總流程，最后進行實例分析。

3.1 單個影響力節點選取

利用節點影響力最大化算法選取的節點稱為種子節點。根據實際需求或成本等的不同，不同應用場景中需要選取的節點數也存在差異。若需要選取網絡中的k個種子節點，ECA算法利用以下方式來選取網絡中最具信息傳播影響力的節點集。

3.1.1 根據k-core算法批量選取

k-core算法通過對網絡層次結構的層層分解，評估出節點在整個網絡的全局性核心程度，即k-core算法是把網絡中節點度小于ks的節點去除的過程。

本文利用節點的k-core數ks值來評估節點的全局結構影響力。從k-core算法可以看出，該算法雖然可以在一定程度上評估出節點在網絡中的影響力大小，但仍然不夠細分，無法挑選出唯一的影響力最大節點。因此本文在進行節點信息傳播影響力評估時，在k-core的基礎上進一步考慮節點鄰近結構信息。

3.1.2 根據節點鄰近結構信息細化選取

結合獨立級聯模型的特點，評估節點鄰近結構影響力Iv-near時，ECA算法考慮了節點v對其鄰居的貢獻程度以及節點v的集聚系數。v的每一條連邊對其鄰居節點的貢獻度體現了v對其每個鄰居節點的影響程度大小，取鄰居節點度的倒數即1/di為貢獻值；節點集聚系數（clustering coefficient）Cv描述了節點的鄰居節點連接的緊密性，v的集聚系數越大，v的鄰居節點之間存在的邊數ev越大，則當以v為初始傳播節點時，信息成功傳播給其鄰居節點的可能性越大。因此定義節點v的鄰近結構影響力如下：

式中，α是權值，根據實驗結果調整得出具體值且α＞0.5；Nv是v的鄰居節點集，根據圖論知識可以推出；dv(dv-1)/2是v的鄰居節點組成的全連通圖具有的連邊數量。通過式（1）計算Iv-near值，選取Iv-near值最大的節點為種子節點。

3.2 去除邊緣節點影響范圍重合

節點影響范圍定義為：利用節點（集）作為信息初始傳播節點，信息傳播結束后已激活的節點總數。節點影響范圍重合是指：通過指定的方法評估出來的具有較大影響力節點的影響區域部分重疊的情況。

影響范圍重合出現的原因是種子節點之間存在共鄰節點，且任意兩個節點i、j影響力重合范圍（overlapped range，OR）滿足：

由于在獨立級聯傳播模型中，每條邊具有傳播概率獨立的特性，基于獨立級聯模型的影響力最大化算法在選取種子節點時需要考慮將節點可能影響范圍最大化。節點影響力重合問題使節點信息傳播影響力不能得到最大的發揮。針對上述問題，覆蓋類算法如最大度覆蓋、最大核覆蓋以及CCA算法均利用標記已選取節點的影響區域的方法來解決。但由于此類算法在選取節點后，并沒有考慮已標記區域對未標記區域邊緣節點的影響，從而導致后續選取的節點仍然存在邊緣影響范圍的重合問題。為了更好地闡述邊緣節點影響范圍重合問題，現做出以下定義。

定義1（邊緣貢獻）邊緣貢獻是指在覆蓋類影響力最大化算法中，由于已標記區域與未標記區域節點存在連邊，從而對這些節點的傳播影響力評估產生貢獻。

圖1表示節點X、Y與已標記區域的連接結構。從圖中可以看出，覆蓋類算法選取種子節點后將其鄰居節點標記為節點影響范圍，而已標記區域與未標記區域的邊緣節點X仍存在連邊，即已標記區域對節點X存在邊緣貢獻，這就導致了選取后續種子節點時節點影響力評估存在過量估計。在X、Y的節點影響力比較中對邊緣節點X更有利，從而導致邊緣節點影響范圍重合且重合范圍滿足：

Fig.1 Sketch map of edge node圖1 邊緣節點示意圖

下面通過一個具體的網絡W直觀分析現有覆蓋類影響力算法存在的邊緣節點影響范圍重合問題。圖2展示了W的網絡拓撲。

Fig.2 Network topology structure ofW圖2 網絡W的網絡拓撲結構

若需要的種子節點數為2，即k=2，利用CCA算法（d=1）的節點影響力評估方法可以得到以下結果。

不同核數的節點集合分別是：

不同度數的節點集合分別是：

綜合節點核數與度數選取出的備選種子節點為{1,3,6}。從這里可以看出，最大核覆蓋、最大度覆蓋、CCA算法的節點影響力評估方式均無法將節點影響力進一步細分。為了后面問題分析更為直觀，這里將節點1選為種子節點，則按照現存覆蓋類算法的標記方式，將節點1的鄰居節點標記。繼續根據節點原有核、度屬性選取標記區域以外的節點，則下一個種子節點為6，選取結束。

從上述算法種子節點第二輪選取過程中可以看出，由于已標記區域（圖3中的紅色節點）中節點3、5與未標記區域邊緣節點6存在連邊，則已標記區域對節點6產生邊緣貢獻，導致節點1與節點6的影響范圍重合且重合范圍OR1,6滿足：

Fig.3 Edge node influence range overlap圖3 邊緣節點影響范圍重合

針對上述邊緣節點影響范圍重合問題，本文通過去除已標記區域節點及連邊，并在下一次循環選取種子節點之前更新網絡拓撲結構，最后根據當前網絡結構重新計算節點影響力值，以新的節點影響力值大小為標準選取種子節點，以此來達到屏蔽已標記區域對未標記區域邊緣產生影響的目的。具體實現流程如下。

對于網絡G=(V,E)，當選取第一個種子節點u后，刪除種子節點u和鄰居節點及其它們所有連邊，即：

式中，V′loop+1是刪除u及u的鄰居節點后的網絡節點集；Eloop+1是選取下一個種子節點前網絡的邊集；Eu、分別是u和其鄰居的邊集。

已標記區域刪除后，在下一次循環開始前網絡更新為：

式中，Visolated是網絡中的孤立節點集；Vloop+1是選取下一個種子節點前網絡的節點集。

由于刪除已標記區域而出現的孤立節點信息傳播影響力極小，不具有被選取為種子節點的可能。因此利用式（10）檢測網絡中存在的孤立節點集，并將其從當前網絡中刪除，最后形成全新的連通網絡并進入下一次循環。通過上述去重方法，可有效避免邊緣貢獻帶來的節點影響力評估誤差，從而解決邊緣節點影響力范圍重合問題。

3.3 ECA算法總流程

綜上所述，結合單個影響力節點選取和去重方案，ECA算法整體詳細步驟為：

（1）根據k-core算法選取ks值最大的節點。若出現多個節點ks值相同的情況，則到第（2）步；若結果唯一，則選為種子節點，到第（3）步。

（2）選取Iv-near值最大的節點。若出現多個節點Iv-near值相同的情況，則任意選取其中之一，到第（3）步；若結果唯一，則選為種子節點，到第（3）步。

（3）將選取的種子節點及其鄰居節點從網絡中刪除，同時也刪除它們的所有連邊。

（4）更新網絡拓撲結構。

（5）檢測網絡中是否存在孤立節點，若存在則刪除孤立節點，更新網絡結構；若不存在，則到第（6）步。

（6）回到步驟（1）繼續選取節點，直到選取k個種子節點為止。

根據上述原理，算法偽代碼如下。

算法1 ECA

假設網絡G=(V,E)有n個節點，m1條邊，要選取k個種子節點，ECA算法的復雜度分析如下：首次進行種子節點選取時，利用k-core算法，復雜度為O(m1)；在選取種子節點后，刪除相關節點及連邊后更新網絡，此時網絡中有m2條邊，再次利用k-core算法，選取下一種子節點，此時復雜度為O(m1+m2)；以此類推，選取第k個種子節點時，網絡中的邊為mk，復雜度為O(mk-1+mk)。一共需要選取k個節點，因此ECA算法的復雜度為O[m1+(m1+m2)+…+(mk-1+mk)]，即O[2(m1+m2+…+mk)-mk]。相比于CCA算法的復雜度O(km)，該算法的復雜度略高，處于同一個數量級，但其準確度優于CCA算法。相比于貪心算法的復雜度O(kmn)，該算法的復雜度明顯優于貪心算法。

4 仿真驗證

4.1 實驗數據集

為了驗證ECA算法的合理性，本文利用IC模型作為傳播模型，美國安然公司E-mail網絡、DBLP網絡結構數據作為算法的仿真網絡。E-mail網絡是公司員工郵件交流形成的社交網絡。DBLP（Digital Bibliography Library Project）網絡是論文作者合作網絡。ca-HepPh（High Energy Physics-Phenomenology）網絡是高能物理現象科學合作作者提交論文的協作網絡。3個網絡均屬于無向網絡，且具有明顯的無標度特性。網絡基本數據如表1所示。

Table 1 Network basic data表1 網絡基本數據

4.2 衡量指標

通常情況下，準確度是在給定的傳播模型基礎上，算法選定的種子節點在傳播結束后最終能夠影響到的節點數量，即節點影響范圍。在社交網絡的商品推廣等應用領域中，商品信息的傳播范圍一定程度上代表了推廣工作的成功程度，算法準確度越高，節點影響范圍越大，則影響到的社交用戶越多。因此，準確度是評價影響力最大化算法的重要指標。本文考察種子節點數k從1增加到30傳播范圍的變化情況，并與其他相關算法進行比較分析。另外，為了更加顯著地體現出每種算法效果的差異性，定義：

式中，wk是兩種算法在種子節點數為k時的影響范圍差異；RECA是ECA算法的節點傳播影響范圍；RA是算法A的節點傳播影響范圍；A分別是度啟發式（2003年）、k-core啟發式（2010年）、最大度覆蓋（2010年）、最大核覆蓋（2010年）以及CCA算法（2015年）；waverage是差異百分比平均值。每種算法選取1到30個節點分別在IC模型中運行50次，影響范圍結果取平均值。

4.3 結果分析

4.3.1 DBLP網絡上的結果分析

圖4～圖8分別展示了傳播概率 p取0.01到0.10之間5種不同值時各種算法的影響范圍情況，橫軸代表種子節點數k，縱軸代表節點影響范圍。從圖中可以看出：ECA算法在傳播概率大于等于0.03時，效果優于其他算法；隨著種子節點數增大，不同算法的差別更加明顯；隨著傳播概率的增大，ECA算法的優勢更加顯著。下面針對不同傳播概率下的算法結果走勢進行具體分析。

當傳播概率為0.01時，由于概率極小，除k-core算法外，其他最大化算法之間的效果差異較小。這種情況下，Degree算法表現出了微弱的優勢，這是因為當傳播概率極小時，單個節點可能影響到的范圍非常有限，節點局部影響力發揮相對重要的作用。此時節點的度數基本決定了影響范圍的大小。另外，在種子節點數越大時，k-core算法的表現越差，這是由于k-core算法注重節點全局影響力，并且根據kcore算法選取出的核數最大的節點集通常聯系較為緊密，從而節點影響范圍存在大面積重合，導致算法結果較差。

Fig.4 Influence range ofp=0.01in DBLP network圖4 DBLP網絡中p=0.01時不同算法影響范圍

Fig.6 Influence range ofp=0.05in DBLP network圖6 DBLP網絡中p=0.05時不同算法影響范圍

Fig.8 Influence range ofp=0.10in DBLP network圖8 DBLP網絡中p=0.10時不同算法影響范圍

Fig.5 Influence range ofp=0.03in DBLP network圖5 DBLP網絡中p=0.03時不同算法影響范圍

Fig.7 Influence range ofp=0.07in DBLP network圖7 DBLP網絡中p=0.07時不同算法影響范圍

當傳播概率為0.03時，雖然各大算法的差距并不算特別明顯，但可以看出，Degree算法的效果有了較大幅度下降，基于覆蓋類算法ECA、CCA、最大度覆蓋、最大核覆蓋的效果開始提升。這是因為隨著傳播概率的增大，節點影響力不再局限于節點局部度數，全局結構信息開始發揮作用。在種子節點數大于24時，ECA算法具有明顯的優勢。

當傳播概率為0.05時，算法之間出現了較為明顯的差距，特別是基于k-core的啟發式算法效果已經無法和其他算法相提并論，這也體現了節點影響力最大化算法中去除重合范圍的重要性。ECA、CCA算法略領先于其他算法，兩者差距不明顯。

當傳播概率為0.07時，ECA、CCA算法的優勢已經相當明顯。特別是當種子節點數越大時，ECA算法優勢極其明顯。相對的，Degree算法效果急劇下降，在除了k-core算法的幾種算法中，結果最為不理想，說明了隨著傳播概率的增大，節點影響力范圍從鄰居節點逐步擴大，因此僅僅考慮節點度數不能恰當評估節點影響力。

當傳播概率為0.10時，ECA和CCA算法已經和其他算法存在較大差距。種子節點數較少時，CCA算法表現優異，但當種子節點數增多時，ECA算法表現更為優異且與CCA有明顯差距。

表2展示了DBLP網絡中ECA算法與其他算法的影響范圍平均差異百分比。從表2中可以看出，度啟發式算法隨著傳播概率的增大算法效果下降趨勢最為明顯，k-core啟發式算法效果最差，CCA算法在5種對比算法中最優，而本文算法ECA比CCA算法更有優勢。整體來說，ECA算法在傳播概率大于0.03時優勢明顯，并且隨著k值增加，ECA算法的優化效果更加顯著。這是因為ECA算法在去除影響范圍重合時考慮了未標記區域邊緣節點影響范圍的重合問題。因此，相比其他算法而言，選取的節點數越多，ECA算法在去重方面更具有優勢，最后的優化結果也更為明顯。

Table 2 Mean difference of influence range of ECA algorithm and other algorithms in DBLP network表2 DBLP網絡中ECA算法與其他算法影響范圍平均差異

Fig.9 Influence range ofp=0.01in E-mail network圖9 E-mail網絡中p=0.01時不同算法影響范圍

4.3.2 E-mail網絡上的結果分析

圖9～圖13分別展示了傳播概率取0.01到0.10之間5種不同值時各種算法的影響范圍情況。從圖中可以看出：ECA算法在傳播概率大于等于0.05時，效果優于其他算法；隨著種子節點數k增大，ECA算法的優勢更加顯著。

從前面DBLP網絡的結果分析可知，當傳播概率為0.01時，由于傳播概率極小，信息很難在網絡中擴散，導致各種算法的影響范圍較為接近。

傳播概率為0.03時，Degree算法具有相當的優勢，除了k-core算法，其他算法的差距較小。從E-mail網絡和DBLP網絡的基本數據可以看出，DBLP網絡的平均集聚系數是E-mail網絡的2.3倍左右。經過仿真運算，在DBLP網絡中，節點核數最大為23，相同核數的節點數量為322；在E-mail網絡中，節點核數最大為11，共有66個節點。從這些數據可以看出，E-mail網絡結構更為疏松，因此度中心性在節點信息傳播影響力中發揮了非常重要的作用，這也是Degree算法在E-mail網絡比DBLP網絡表現更為優越的原因。

Fig.10 Influence range ofp=0.03in E-mail network圖10 E-mail網絡中p=0.03時不同算法影響范圍

Fig.11 Influence range ofp=0.05in E-mail network圖11 E-mail網絡中p=0.05時不同算法影響范圍

Fig.12 Influence range ofp=0.07in E-mail network圖12 E-mail網絡中p=0.07時不同算法影響范圍

Fig.13 Influence range ofp=0.10in E-mail network圖13 E-mail網絡中p=0.10時不同算法影響范圍

隨著傳播概率增大到0.05，以Degree算法為代表的通過局部影響力來評估節點影響力的方法結果開始變差，基于影響力覆蓋的算法開始發揮優勢，ECA、CCA算法目前效果較優。

傳播概率為0.07時，ECA算法仍然存在優勢，而Degree算法效果持續下降，但k-core算法和其他算法的差距卻逐漸縮小，比起DBLP網絡中k-core算法極差的表現，在E-mail網絡中其效果較好。出現這種現象的原因是對于拓撲結構越疏松的網絡，利用k-core算法選取的節點影響力重合范圍越小，因此算法效果比平均集聚系數大的網絡較優。

當傳播概率為0.10時，ECA較其他算法存在一定優勢，效果優化程度由大到小為ECA＞CCA＞最大度覆蓋＞最大核覆蓋＞Degree＞k-core。

表3展示了E-mail網絡中ECA算法與其他算法的影響范圍平均差異百分比，從表中可以更為清晰地看出，ECA算法在基于k-core的最大化算法中具有較大的優勢，而Degree啟發式的效果隨著傳播概率增大明顯變差。

Table 3 Mean difference of influence range of ECA algorithm and other algorithms in E-mail network表3 E-mail網絡中ECA算法與其他算法影響范圍平均差異

4.3.3 ca-HepPh網絡上的結果分析

圖14～圖18分別展示了傳播概率取0.01到0.10之間的5種不同值時各種算法的影響范圍情況。從圖中可以看出：ECA算法在傳播概率大于等于0.01時，效果優于其他算法；隨著種子節點數k和傳播概率的增大，ECA算法優勢更加明顯。下面是針對不同傳播概率下的算法結果的具體分析。

從前面兩個網絡的結果分析可知，當傳播概率取0.01時，傳播概率極小，信息在網絡中進行傳播較為困難，因此各種算法之間的效果差異較小。

當傳播概率為0.03時，各個算法的差距不大，隨著種子節點數量的增加，ECA算法的優勢越來越明顯。

在傳播概率大于0.05時，基于影響力覆蓋的ECA算法與CCA算法優勢明顯，并且隨著種子節點數量的增加及傳播概率的增大，ECA算法優勢更為明顯。而僅考慮局部影響力評估節點影響力的Degree算法等效果較差。

表4展示了ca-HepPh網絡中ECA算法與其他算法的影響范圍平均差異百分比。整體來說，ECA算法在傳播概率大于0.03時優勢明顯，并且隨著k值增加，ECA算法的優勢更加顯著。

Fig.14 Influence range ofp=0.01in ca-HepPh network圖14 ca-HepPh網絡中p=0.01時不同算法影響范圍

Fig.16 Influence range ofp=0.05in ca-HepPh network圖16 ca-HepPh網絡中p=0.05時不同算法影響范圍

Fig.18 Influence range ofp=0.10in ca-HepPh network圖18 ca-HepPh網絡中p=0.10時不同算法影響范圍

Fig.15 Influence range ofp=0.03in ca-HepPh network圖15 ca-HepPh網絡中p=0.03時不同算法影響范圍

Fig.17 Influence range ofp=0.07in ca-HepPh network圖17 ca-HepPh網絡中p=0.07時不同算法影響范圍

Table 4 Mean difference of influence range of ECA algorithm and other algorithms in ca-HepPh network表4 ca-HepPh網絡中ECA算法與其他算法影響范圍平均差異

在同等的硬件壞境下，DBLP網絡和E-mail網絡中Degree啟發式和最大度覆蓋的運行時間平均在2 s以下，k-core啟發式、最大核覆蓋以及CCA算法的運行時間在37 s左右，ECA算法為80 s左右。在數據規模較大的ca-HepPh網絡中，Degree啟發式和最大度覆蓋的運行時間在100 s以下，k-core啟發式、最大核覆蓋以及CCA算法的運行時間在4 000 s左右，ECA算法為7 000 s左右。Degree啟發式算法運行時間較短，但其效果最差。相較于其他算法中效果最好的是CCA算法，ECA算法運行時間略長，但是ECA算法的準確度優于其他算法，其運行時間在可被接受的范圍內，可以看出ECA算法整體效果較優。

通過在3種網絡中的影響范圍結果比較可以看出，種子節點越多、網絡規模越大時，ECA算法的效果越好。此外，p從0.01到0.10，DBLP網絡中節點影響力最大范圍依次為56，80，118，214，281；E-mail網絡中節點影響力最大范圍依次為58，119，203，325，487。在相同的傳播概率條件下，兩者差距極其明顯，E-mail網絡的最大范圍比DBLP網絡更大。由此可以得出結論，在相同初始條件下，集聚系數越大的網絡信息傳播范圍越小。

5 結束語

影響力最大化問題是社會網絡信息傳播研究中的關鍵問題之一，目的是發現網絡中最具有傳播影響力的節點，在廣告發布、輿情控制、市場營銷等許多重要場景中都有廣泛的應用。本文提出了基于IC模型的節點影響力最大化算法ECA，結合k-core算法及節點鄰近結構信息來評估節點影響力，并通過去除已選節點影響范圍的方式來屏蔽已選區域對邊緣節點的影響，以此來除去節點之間的影響重合范圍。仿真結果證明ECA算法能夠增大節點信息傳播影響范圍，比其他算法效果更優。

在后續研究工作中，考慮將網絡結構基本數據分析與節點影響力最大化問題聯系起來，根據網絡實際情況和初始傳播節點數量需求不同，實現算法中節點影響力評估方法的自適應調整，從而在影響傳播范圍以及運行時間優化方面提高影響力最大化算法的性能，進而拓展影響力最大化算法應用領域。

[1]Domingos P,Richardson M.Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco,USA,Aug 26-29,2001.New York ACM,2001: 57-66.

[2]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.

[3]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,USA,Aug 12-15,2007.New York:ACM,2007:420-429.

[4]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 World Wide Web Conference,Hyderabad,India,Mar 28-Apr 1, 2011.New York:ACM,2011:47-48.

[5]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.

[6]Liu Xiaodong.Research on efficient processing techniques of influence maximization in large-scale socialnetworks[D]. Changsha:National University of Defense Technology,2013.

[7]Tian Jiatang,Wang Yitong,Feng Xiaojun.A new hybrid algorithm for influence maximization in social networks[J]. Chinese Journal of Computers,2011,34(10):1956-1965.

[8]Chen Hao,Wang Yitong.Threshold-based heuristic algorithm for influence maximization[J].Journal of Computer Research and Development,2012,49(10):2181-2188.

[9]Guo Jingfeng,Lv Jiaguo.Influence maximization based on information preference[J].Journal of Computer Research and Development,2015,52(2):533-541.

[10]Guo Jing,Cao Yanan,Zhou Chuan,et al.Influence weights learning under linear threshold model in social networks[J]. Journal of Electronics and Information Technology,2014, 36(8):1804-1809.

[11]Zhang Bolei,Qian Zhuzhong,Wang Qinhui,et al.Maximize information coverage algorithm for target marke[J]. Chinese Journal of Computers,2014,37(4):894-904.

[12]Chen Wei,Wang Chi,Wang Yajun.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,Jul 25-28,2010.New York:ACM,2010: 1029-1038.

[13]Chen Wei,Yuan Yifei,Zhang Li.Scalable influence maximization in social networks under the linear threshold model[C]//Proceedings of the 10th International Conference on Data Mining,Sydney,Dec 13-17,2010.Washington:IEEE Computer Society,2010:88-97.

[14]Jung K,Heo W,Chen Wei.IRIE:a scalable influence maximization algorithm for independent cascade model and its extensions[J].arXiv:1111.4795,2011.

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

[16]Goyal A,Lu Wei,Lakshmanan L V S.SIMPATH:an efficient algorithm for influence maximization under the linear threshold model[C]//Proceedings of the 11th International Conference on Data Mining,Vancouver,Canada,Dec 11-14, 2011.Washington:IEEE Computer Society,2011:211-220.

[17]Cao Jiuxin,Dong Dan,Xu Shun,et al.A k-core based algorithm for influence maximization in social networks[J].Chinese Journal of Computers,2015,38(2):238-248.

附中文參考文獻：

[6]劉曉東.大規模社會網絡中影響最大化問題高效處理技術研究[D].長沙:國防科學技術大學,2013.

[7]田家堂,王軼彤,馮小軍.一種新型的社會網絡影響最大化算法[J].計算機學報,2011,34(10):1956-1965.

[8]陳浩,王軼彤.基于閾值的社交網絡影響力最大化算法[J].計算機研究與發展,2012,49(10):2181-2188.

[9]郭景峰,呂加國.基于信息偏好的影響最大化算法研究[J].計算機研究與發展,2015,52(2):533-541.

[10]郭靜,曹亞男,周川,等.基于線性閾值模型的影響力傳播權重學習[J].電子與信息學報,2014,36(8):1804-1809.

[11]張伯雷,錢柱中,王欽輝,等.面向目標市場的信息最大覆蓋算法[J].計算機學報,2014,37(4):894-904.

[17]曹玖新,董丹,徐順,等.一種基于k-核的社會網絡影響最大化算法[J].計算機學報,2015,38(2):238-248.

HU Min was born in 1971.She received the M.S.degree from Chongqing University of Posts and Telecommunications in 2002.Now she is an associate professor and M.S.supervisor at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications.Her research interests include wireless communication,communication network system and protocol etc.

胡敏（1971—），女，重慶人，2002年于重慶郵電大學獲得碩士學位，現為重慶郵電大學通信與信息工程學院副教授、碩士生導師，主要研究領域為無線通信通信，網體系與協議等。

SUN Xinran was born in 1991.She is an M.S.candidate at School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications.Her research interest is communication network.

孫欣然（1991—），女，河北石家莊人，重慶郵電大學通信與信息工程學院碩士研究生，主要研究領域為通信網絡。

HUANG Hongcheng was born in 1979.He received the M.S.degree in communication and information engineering from Chongqing University of Posts and Telecommunications in 2006.Now he is an associate professor at School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,and the member of CCF.His research interests include ad hoc network and delay tolerant network,etc.

黃宏程（1979—），男，河南南陽人，2006年于重慶郵電大學通信與信息工程專業獲得碩士學位，現為重慶郵電大學通信與信息工程學院副教授，CCF會員，主要研究領域為無線自組織網絡，容遲網絡等。

Edge-CoverAlgorithm for Influence Maximization in Social Network*

HU Min1,SUN Xinran1,HUANG Hongcheng1,2+
1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications, Chongqing 400065,China
2.College of Computer Science,Chongqing University,Chongqing 400044,China

+Corresponding author:E-mail:huanghc@cqupt.edu.cn

HU Min,SUN Xinran,HUANG Hongcheng.Edge-cover algorithm for influence maximization in social network.Journal of Frontiers of Computer Science and Technology,2017,11(5)：720-731.

Influence maximization is a problem of obtaining a subset of nodes in social network to maximize the influence spread.Aiming at the problem of the poor accuracy of heuristic algorithm,existing works consider the overlapped range,and ignore the problem of edge contributions.This paper focuses on how to select a seed set that has the maximum influence based on edge contributions.The algorithm evaluates the influence of information spread by calculating the global influence and adjacent influence.Then it removes the selected node influence range and updates the network to eliminate the interference of edge contributions to node influence evaluation.Finally,this paper proposes an edge-cover algorithm for influence maximization based on independent cascade model.The experimental results show that the proposed algorithm has a greater impact on the spread of range.

social network;influence maximization;edge contributions;heuristic algorithm

10.3778/j.issn.1673-9418.1605063

A

：TP391.9

*The National Natural Science Foundation of China under Grant No.61401051(國家自然科學基金);the Foundation and Frontier Research Project of Chongqing Science and Technology Commission under Grant No.cstc2014jcyjA40039(重慶市科委基礎和前沿研究項目);the Science and Technology Research Project of Chongqing Municipal Education Committee under Grant No.KJ1400402 (重慶市教委科學技術研究項目).

Received 2016-05,Accepted 2016-07.

CNKI網絡優先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.012.html

摘 要：影響力最大化問題是在社交網絡中尋找具有最大影響范圍的節點集。針對啟發式算法準確度相對較差的問題，現有的研究考慮了影響范圍重合，但忽略了邊緣貢獻導致的節點影響力過量評估。重點研究了在考慮邊緣貢獻的情況下，如何選取影響范圍最大的節點集合。采用啟發式算法的思想，首先計算節點全局和鄰近影響力來評估節點信息傳播影響力，通過去除已選節點影響范圍并更新網絡的方式，消除邊緣貢獻對節點影響力評估的干擾，在獨立級聯模型基礎上提出了基于邊緣去重的節點影響力最大化算法。仿真結果表明所提出算法相比其他算法，能夠有效增大節點信息傳播影響范圍。