花勇，陳伯倫，朱國暢，袁燕，金鷹

（淮陰工學院 計算機與軟件工程學院，江蘇 淮安 223003）

隨著社交網絡中信息量的快速增長，信息傳播速度的不斷加快，其信息傳播構建了一種分布式傳播機制[1]以及節(jié)點的合作機制[2]，即信息在用戶之間的擴散會受到用戶影響力的影響[3]。因此，開展影響力分析研究顯得十分重要。影響力最大化問題是影響力分析的重要課題之一。2015年，Morone 和Makse 在Nature 上對社交網絡中影響力最大化問題進行了深入探討[4]。影響力最大化問題解決的是如何衡量網絡中節(jié)點重要性的問題，其經典應用之一是病毒營銷[5-8]，也就是通過口口相傳效應進行產品的銷售[9-10]。

影響力最大化問題最早由Kempe 等[11]率先提出。Kempe 等使用獨立級聯(lián)模型與線性閾值模型對社交網絡中影響力的傳播進行建模，并且證明在社交網絡中尋找具有最佳影響力的種子節(jié)點集合是NP-Hard 問題。而且他們提出使用簡單的貪婪算法尋找具有最佳影響力的種子節(jié)點集合，獲得了(1-1/e)的近似保證。影響力最大化問題中的關鍵問題是如何衡量節(jié)點傳播影響力的能力，也就是節(jié)點所具有的影響力。在最初的影響力最大化問題研究中，一些基于網絡拓撲結構的中心性方法被提出，例如度中心性和點介數中心性。在隨后的影響力最大化問題研究中，多數算法使用次模性質[12-15]，即通過大量迭代來計算邊際收益，從而近似求得問題的最優(yōu)解，但是存在算法時間復雜度較高的問題。Chen 等[16]提出了度折損啟發(fā)式算法，即優(yōu)先選擇度大的節(jié)點作為種子節(jié)點，一旦某節(jié)點被選取為種子節(jié)點，那么其鄰居節(jié)點被選為種子節(jié)點的概率將大大降低。Lee 等[17]利用多數節(jié)點平均只能影響到2 階鄰居節(jié)點的現象，提出了2-hop 貪婪算法，即利用節(jié)點在2 階鄰居范圍內的影響力更新節(jié)點的邊際收益。Chen 等[16]提出MIA(maximum influence arborescence)最大影響力樹算法，利用MIIA(maximum influence in-arborescence)影響力最大入樹和MIOA(maximum out-arborescence)影響力最大出樹構建節(jié)點的影響力傳播路徑，通過節(jié)點的影響力最大化路徑計算得分并選取種子節(jié)點，相較于原始的貪婪算法取得了較低的時間復雜度，但因為MIA 需要對每個節(jié)點建立樹，所以空間復雜度相較于其他算法較高。JUNK 等[18]提出IRIE(influence ranking influence estimation)算法，即算法整體被分為兩部分，影響力排名使用一種算法，影響力模擬再使用一種算法。在最近影響力最大化問題的研究中，許多優(yōu)秀的算法被提出，其中Kitsak 等[19]提出最具影響力的節(jié)點往往不是具有較大連接的節(jié)點，而是處于網絡核心位置的節(jié)點，通過k-shell 分解[20]分析網絡中節(jié)點核數與節(jié)點影響力的關系，為影響力最大化問題提供了新的解決思路。Gao 等[21]根據節(jié)點的影響力與其局部結構的關系，提出了一種局部結構中心性的方法，利用節(jié)點以及其鄰居的拓撲結構和中心性來衡量節(jié)點的影響力，此算法在評估節(jié)點影響力方面更加準確。王等[22]提出的多種群隨機差分粒子群優(yōu)化算法和劉等[23]提出的改進螢火蟲算法也可很好的應用到影響力最大化問題當中。

在上述的影響力最大化算法中，研究人員只關注所選種子節(jié)點影響力是否最佳，旨在研究更加優(yōu)秀的算法近似求得影響力最優(yōu)的種子節(jié)點集合，而忽略了種子節(jié)點集合的大小和網絡固有的傳播影響力能力的關系。本文從網絡傳播影響力能力的角度出發(fā)研究影響力最大化問題，從而得出網絡所適合的種子節(jié)點集合的大小。本文提出種子節(jié)點集合大小并不是越大越好，而是每個網絡都存在一個種子節(jié)點個數的上限，一旦超過這個上限，隨著種子節(jié)點個數大小的增加，種子節(jié)點集合的影響力是趨于飽和的。為研究網絡傳播影響力的固有能力，本文使用滲流[24-26]的思想，即對網絡進行滲流模擬，得出網絡由大量零散的團塊趨向于形成一個主團塊的相變值，從而得出網絡所適合的種子節(jié)點集合的大小，即提出一種基于滲流模型的影響力最大化種子節(jié)點集合大小選取算法來獲得最優(yōu)的種子節(jié)點集合大小，并對算法結果進行了分析。

1 問題描述

1.1 影響力最大化問題

本文主要研究無向網絡傳播影響力的能力，定義無向網絡G=(V,E)，其中V為無向網絡G中的節(jié)點集合，E為無向網絡G中邊的集合。定義n=|V|為網絡G的節(jié)點個數，m=|E|為網絡G邊的個數。影響力最大化問題就是在網絡G中尋找大小為k的種子節(jié)點集合，使得這k個種子節(jié)點在網絡G中傳播的影響力是最大的，我們定義種子節(jié)點集合為S。在影響力最大化問題中，我們面臨著兩個尤為重要的問題，即影響力是如何定義的，以及影響力在網絡中是如何傳播的。獨立級聯(lián)模型(independent cascade model)是經典的模擬影響力傳播的模型，在之前多數影響力最大化問題的研究中，研究人員都使用獨立級聯(lián)模型作為影響力傳播模型。而節(jié)點或者節(jié)點集合的影響力，我們使用影響力函數進行求解。

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

獨立級聯(lián)模型[27-28]是經典的用于模擬影響力傳播的算法，模型描述如下：在網絡G中，節(jié)點集合V中的節(jié)點v存在兩種狀態(tài)，即一種是激活狀態(tài)另一種是未激活狀態(tài)。假設t時刻，節(jié)點v已經處于激活狀態(tài)，那么節(jié)點v會嘗試以概率p去激活其鄰居節(jié)點u，如果激活成功，那么節(jié)點u會從t+1 時刻開始，一直處于激活狀態(tài)。如果激活失敗，那么從t+1 時刻開始，節(jié)點u再也不能被節(jié)點v嘗試激活。我們定義影響力傳播模型的初始時刻為t=0 時刻，定義集合A0中的節(jié)點處于激活狀態(tài)，那么集合At為t時刻被激活的節(jié)點集合。如果存在某一時刻c+1，集合Ac+1為空集，那么獨立級聯(lián)模型終止運行。當獨立級聯(lián)模型終止時，我們可以獲得在此過程中激活的節(jié)點集合Atotal=

1.3 影響力函數

定義影響力函數為I(x)：將有限集合映射到非負整數域上的函數。在網絡中使用獨立級聯(lián)模型模擬影響力傳播的過程當中，種子集合S為初始時刻已經激活的節(jié)點集合，在影響力傳播過程的每個離散時刻都會因集合S激活一些未激活的節(jié)點，在影響力傳播過程結束時我們可以得到在此過程中激活的節(jié)點集合Atotal，即集合Atotal是被種子節(jié)點集合S影響的節(jié)點集合。我們令種子節(jié)點集合S的影響力為I(S)，其值為|Atotal|，即種子節(jié)點集合S的影響力是在影響力傳播過程中被集合S影響到的節(jié)點的個數。

2 算法思想與步驟

本文主要研究影響力最大化問題中種子節(jié)點集合大小選取的問題。在之前的研究中，研究人員一般選取5～50 個節(jié)點作為種子節(jié)點，并觀察算法選取出的種子節(jié)點集合的影響力，旨在通過改進算法得到更優(yōu)的種子節(jié)點集合。而本文從網絡傳播影響力的固有能力的角度出發(fā)，發(fā)現網絡在選取種子節(jié)點時，并非越多越好，而是一定數量的種子節(jié)點就能達到最優(yōu)的影響力，即在網絡中存在一個最優(yōu)大小的種子節(jié)點集合，即我們所說的網絡傳播影響力的固有能力。為了研究網絡傳播影響力的固有能力，本文借助滲流模型對網絡進行模擬分析，提出一種基于滲流模型的影響力最大化算法，即在不同的傳播概率p下對網絡進行滲流模擬，通過建立傳播概率p與滲流模擬后網絡的最大連通子圖大小的函數關系，最終求得當前網絡所適合的種子節(jié)點集合的大小。具體算法步驟如下：

算法基于滲流模型的影響力最大化種子節(jié)點集合大小選取算法

輸入上三角鄰接矩陣G'，傳播概率數組plist，網絡中節(jié)點的數量n，矩陣C，模擬次數R;

輸出最優(yōu)種子節(jié)點集合大小k'

3) 根據plist(i)對G'進行滲流模擬，形成 滲流后網絡GP，并且獲得GP 的最大連通 子圖GP'；

6) 對plist和C進行多項式擬合，求得擬合 函數F(x)；

7) 求F(x)的導函數dF(x)；

8) 通過函數dF(x)求得相變值pc；

k′=pc×n

9) 最優(yōu)種子集合大小

本文提出一種基于滲流模型的影響力最大化種子節(jié)點集合大小選取算法。算法的輸入為：無向網絡G的上三角鄰接矩陣G'，傳播概率數組plist，網絡中節(jié)點的數量n，矩陣C和模擬次數R。因為本文主要研究無向網絡，在對網絡進行滲流模擬時，為了保持邊的一致性，所以使用網絡G的上三角鄰接矩陣G'。plist是大小為 1 ×1 000 的一維數組，其中數組元素為0.001～1 的數字，且相鄰元素相差0.001。C是大小為 1 00×1 000 的矩陣。因為在網絡G上進行滲流的結果具有隨機性，所以我們在傳播概率p∈plist的情況下進行R次滲流。算法的輸出為最優(yōu)種子節(jié)點集合大小k'。具體的算法步驟描述如下：

1) 函數len(x) 用來計算數組的長度，所以len(plist)的值等于1 000，此步驟具體是：在傳播概率p∈plist的情況下，對網絡G'進行滲流；

2) 采用當前傳播概率p對網絡G'進行R次滲流；

3)滲流模型的定義如下：在網絡G'中，網絡每條邊具有統(tǒng)一的傳播概率值p。我們對每條邊產生獨立的隨機值pr，如果prp，那么此邊處于非占有狀態(tài)，也就是此邊從網絡中刪除。通過改變統(tǒng)一的傳播概率值p，那么存在一個值pc，當p>pc時，GP 中的節(jié)點傾向于緊密的連接在一起，形成一個主團塊。當p

4)函數num(x)用于計算網絡中節(jié)點的個數，所以此步驟是將GP'的節(jié)點個數存入到C中；

5)函數avg(x)用于計算矩陣每列的平均值，所以此步驟是對傳播概率p下R個num(GP')求平均值，并且存入到C'中，也就是說，每個傳播概率p，我們都會對G'進行R次滲流模擬，從而產生R個num(GP')，最后將其求平均，即得到每個傳播概率p所對應GP'的平均大小；

6)采用多項式擬合的方法對plist和C'進行擬合。多項式擬合是使用多項展開式去近似數據點的函數關系，并使用最小二乘法來得到多項展開式的系數，最終求得數據點函數關系的方法。多項式擬合公式為

式中：a0到al為使用最小二乘法求取的系數；l為多項式的階數。本文式(1)中的x為plist中的元素，C'中的元素為F(x)的函數值，通過多項式擬合函數求得F(x)的系數，從而求得plist和C'的擬合函數F(x)；

7)求函數F(x)的導函數dF(x)；

8)相變值pc在pm的左鄰域中，其中dF(pm)的值為函數dF(x) 的最大值，dF(pc) 的值為靠近dF(pm)最近的最小值，相變值pc為函數F(x)變化速率開始加快的起點位置；

9)求取最優(yōu)種子集合大小。

圖1 滲流實驗例圖Fig.1 The example of percolation experiment

3 實驗結果及分析

本文提出的一種基于滲流模型的影響力最大化種子節(jié)點集合大小選取算法在4 個公共數據集上進行實驗，數據集分別為KarateClub[29]、Football[30]、HighSchool[31]和SocDolphins[32]。因本文主要研究無向網絡，所以必要時對數據集進行了無向化處理。KarateClub 數據集是1970 年美國大學生空手道俱樂部34 名成員之間朋友關系的社交網絡。Football 是2000 年美式足球秋季常規(guī)賽大學之間的比賽網絡。HighSchool 是2013 年12 月法國馬賽高中學生友誼聯(lián)系的社交網絡。Soc-Dophins 是寬吻海豚之間的社交網絡。其中數據集KarateClub、HighSchool 和SocDophins 中的邊表示成員之間擁有相對頻繁的聯(lián)系，Football 數據集中的邊表示球隊之間會有比賽安排。不同數據集的拓撲屬性如表1 中所示，其中節(jié)點數為網絡中節(jié)點的總數，邊數為網絡中邊的總數，最大度數為網絡中邊數的最大值，平均度為度的平均值。同配系數是描述大度節(jié)點之間相連接的能力，其值越靠近1 說明其同配性越好；聚類系數是描述節(jié)點之間連接成團的能力，其值越大說明網絡中的節(jié)點更有可能產生連接；網絡密度描述了網絡實際存在邊數與網絡可容納邊數的比值，也就是節(jié)點之間相互連邊的密集程度，其值越大說明網絡越密集。

表1 數據集屬性Table 1 The attributes of datasets

在現有影響力最大化問題的研究中，大多數研究人員主要關注如何在網絡中選取具有最佳影響力的種子節(jié)點集合，也就是通過研究創(chuàng)造出更先進的影響力最大化算法來近似選取種子節(jié)點集合，并不關注種子節(jié)點集合大小的問題，即網絡傳播影響力的固有能力的問題。本文主要研究網絡傳播影響力的能力，提出網絡傳播影響力的能力是有限的，也就是在網絡中選擇種子節(jié)點的時候并不是越多越好，每個網絡存在一個最優(yōu)的種子集合大小，一旦種子集合大小超過了最優(yōu)值，其多出的種子節(jié)點所帶來的影響力幾乎不能起到積極的作用，反而會增加實驗的成本。因為本文主要研究種子節(jié)點集合的大小，所以需要獲得種子節(jié)點的算法作為載體來求得種子節(jié)點，本文使用4 種經典的算法來選取種子節(jié)點，4 種算法分別為：貪婪算法、度中心性、點介數中心性和基于k核過濾核覆蓋算法。使用上述方法分別選出4 個數據集具有最佳影響力的10 種子節(jié)點，并對其影響力做出分析。

3.1 滲流實驗

我們提出網絡傳播影響力的固有能力與相變值pc有關，所以在網絡G上進行滲流實驗。通過改變傳播概率p，對網絡G進行多次滲流實驗，建立傳播概率p與滲流后網絡GP 的最大連通子圖GP'平均大小s的函數關系。在具體實驗中，設定傳播概率p為0.001～1 的數，且為0.001 的倍數，也就是說傳播概率p有1 000種情況。然后根據不同的傳播概率p對網絡進行滲流實驗，并且每個傳播概率p進行R次獨立的滲流實驗，因為滲流實驗具有隨機性，本文中通過設置較高的R值來獲取足夠的實驗結果，本文設置R=1 000。滲流實驗后，計算得到滲流后網絡GP 的最大連通子圖GP'的平均大小s，通過多項式擬合的方法對p和s進行擬合，形成p和s的擬合函數F(x)。滲流模擬實驗具體結果如圖2 所示。在圖2 中，p表示網絡的傳播概率，s表示每個傳播概率p下R次滲流模擬后所得的最大連通子圖大小均值。圖2 中藍色部分是由1 000 個點構成的散點圖，每個點對應了一個傳播概率p以及一個最大連通子圖大小均值s。圖中紅色曲線是對p和s進行擬合得到的擬合函數F(x) 的曲線。由圖2 發(fā)現隨著p值的增大，曲線逐漸平緩，在p值較小的時候，s的增長速率較大。即p值較小時，GP 由零散的小團塊組成，當p值越來越大時，GP 趨向由主團塊組成。

圖2 滲流實驗Fig.2 The percolation experiment

3.2 相變值

為了計算網絡G的相變值pc，需要計算函數F(x)的變化速率。在圖3 中，p為傳播概率，r為函數F(x)的變化速率，即函數dF(x)的值。我們可以得到函數dF(x) 的最大值dF(pm)，點pm為圖3 中綠色的點，也就是函數F(x)變化最快的時候。所有找的相變點pc，在pm的左鄰域中，也就是圖3 中紅色的點，其中dF(pc)為距離dF(pm)最近的最小值，也就是函數dF(x)變化增長到最快時的起點位置。當網絡的傳播概率p小于相變值pc時，變化速率r還處于較低水平，GP 由零散的小團塊組成，當傳播概率p大于pc時，GP 趨向由主團塊組成，GP 逐漸呈現出以最大連通子圖為主的圖結構。本文提出相變值pc反應了網絡G傳播影響力的固有能力，也就是相變值反應網絡G中邊被激活的能力，即在影響力傳播模型下，被激活邊占總邊數的比例。因此可以得到網絡G最優(yōu)的種子節(jié)點集合的大小k'。

因此可以計算出4 個數據集的相變值與最優(yōu)的種子節(jié)點集合的大小，其中KarateClub、Football、HighSchool 和SocDolphins 的相變值分別為0.034、0.059、0.022 和0.029。KarateClub、Football、HighSchool 和SocDolphins 的最優(yōu)的種子節(jié)點集合的大小分別為2、7、3 和2。

圖3 擬合函數變化速率Fig.3 The changing rate of fitting function

3.3 影響力模擬

本文使用4 種影響力最大化算法來選取種子節(jié)點集合，4 種算法分別是：簡單貪婪算法[11]、度中心性、點介數中心性[33]以及基于k核過濾核覆蓋算法[34]。其中，簡單貪婪算法通過迭代的方式逐節(jié)點計算I(S∪{v})，并在每輪迭代中將使函數值最大的節(jié)點v加入到種子節(jié)點集合S中，直到選滿k個種子節(jié)點，迭代結束。度中心性和點介數中心性則選擇度最大的k個節(jié)點作為種子節(jié)點?；趉核過濾核覆蓋算法則是通過預先計算出最優(yōu)的核數kopt，通過k核分解出最小核數為kopt的子圖，在子圖中選擇核數最大的節(jié)點作為種子節(jié)點。

在影響力模擬實驗中，我們使用獨立級聯(lián)模型作為影響力模擬算法以及使用I(x) 計算影響力，并且使用上述4 種算法選取影響力最大的10 個種子節(jié)點，分別對1～10 大小種子節(jié)點集合進行影響力模擬。4 個數據集種子節(jié)點集合影響力實驗結果如圖4 所示。在圖4 中，k為種子節(jié)點個數，I(k)為種子節(jié)點集合的影響力。圖4(a)為KarateClub 數據集種子節(jié)點集合影響力的實驗結果，在圖中我們可以發(fā)現4 種算法選出的種子節(jié)點集合在大小為3 時，影響力大小幾乎趨于平衡，說明當前數據集適合3 個以下種子節(jié)點作為種子節(jié)點集合。圖4(b)為Football 數據集種子節(jié)點集合影響力的實驗結果，4 種算法的影響力呈逐漸上升趨勢，并且在種子節(jié)點個數為6 時，增長趨勢逐漸變緩。圖4(c)為HighSchool數據集種子節(jié)點集合影響力的實驗結果，4 種算法的影響力呈逐漸上升趨勢，圖像在種子節(jié)點個數k分別為6 時上升趨勢逐漸放緩。圖4(d)為SocDolphins 數據集種子節(jié)點集合影響力的實驗結果，4 種算法的影響力波動較大，總體呈上升趨勢，但我們可以觀察到當k=5 開始，影響力已經開始小于種子節(jié)點的個數。

圖4 影響力模擬Fig.4 The influence simulation

3.4 平均影響力分析

在圖5 中，k為種子節(jié)點個數，縱坐標為當前種子節(jié)點集合單個節(jié)點的平均影響力。從圖5(a)中可以發(fā)現，當k=2 時單個種子節(jié)點的平均影響力是最高的，1 個種子節(jié)點平均影響力1.5 個節(jié)點左右。當k>4 時，單個種子節(jié)點的影響力不足于1 個節(jié)點。所以KarateClub 數據集適合選擇2 個種子節(jié)點作為種子節(jié)點集合較合適。從圖5(b)中可以發(fā)現，當k為1～3 時，種子節(jié)點的平均影響力最大，1 個種子節(jié)點平均影響2 個節(jié)點，當k>6 時，發(fā)現種子節(jié)點的平均影響力已經不足1.5 個，所以我們認為Football 數據集適合選取7 個種子節(jié)點作為種子節(jié)點集合比較合適。從圖5(c)中可以發(fā)現，當k=1 時單個種子節(jié)點的平均影響力是最高的，1 個種子節(jié)點平均影響力為2 個節(jié)點左右，當k>3 時，我們發(fā)現種子節(jié)點的平均影響力已經不足1.5 個，所以我們認為HighSchool 數據集適合選取3 個種子節(jié)點作為種子節(jié)點集合比較合適。從圖5(d)中可以發(fā)現，1 個種子節(jié)點平均影響力最高為1 個節(jié)點左右。點介數算法選取的種子節(jié)點在k>1 時就出現了平均影響力的下降，貪婪算法和度中心性算法選出的種子節(jié)點的影響力分別在k為4 和3 時出現下降，因此Soc-Dolphins 數據集適合選擇2 個種子節(jié)點作為種子節(jié)點集合比較合適。

圖5 平均影響力Fig.5 The average influence

通過實驗可以看出，一個網絡的種子節(jié)點集合大小并不是越大越好，而是存在一個上限，當種子節(jié)點集合的大小超出了這個上限，多出的種子節(jié)點并不能帶來很好的邊際收益。根據我們所提出的算法計算出的最優(yōu)種子節(jié)點集合大小k'，基本反映了一個網絡傳播影響力能力的上限，因此為種子節(jié)點個數的選取提供了很好的參考，并且可以用于一些選取最優(yōu)種子節(jié)點集合算法中，減少額外的時間開支。

4 結束語

本文主要對無向網絡傳播影響力的固有能力進行研究，通過對網絡進行滲流模擬得到網絡的相變值，發(fā)現相變值可以反應網絡傳播影響力的能力，并提出一種基于滲流模型的影響力最大化算法來選取網絡所適合的種子節(jié)點集合的大小。在算法中，我們建立傳播概率與滲流模擬后網絡最大連通子圖大小的關系，得到網絡相變值pc。當傳播概率p大于pc時，滲流后網絡傾向于由一個主團塊組成，當傳播概率p等于pc時，網絡由多個大型團塊組成。算法通過相變值與種子節(jié)點集合大小的換算，得到當前網絡最優(yōu)的種子節(jié)點集合大小。實驗結果表明該臨界點對影響力最大化種子節(jié)點集合的大小選取起著重要的指導性作用。