基于滲流模型的影響力最大化算法

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

（淮陰工學(xué)院 計算機(jī)與軟件工程學(xué)院，江蘇 淮安 223003）

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

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

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

1 問題描述

1.1 影響力最大化問題

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

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

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

1.3 影響力函數(shù)

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

2 算法思想與步驟

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

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

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

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

3) 根據(jù)plist(i)對G'進(jìn)行滲流模擬，形成 滲流后網(wǎng)絡(luò)GP，并且獲得GP 的最大連通 子圖GP'；

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

7) 求F(x)的導(dǎo)函數(shù)dF(x)；

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

k′=pc×n

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

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

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

2) 采用當(dāng)前傳播概率p對網(wǎng)絡(luò)G'進(jìn)行R次滲流；

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

4)函數(shù)num(x)用于計算網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù)，所以此步驟是將GP'的節(jié)點(diǎn)個數(shù)存入到C中；

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

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

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

7)求函數(shù)F(x)的導(dǎo)函數(shù)dF(x)；

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

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

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

3 實驗結(jié)果及分析

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

表1 數(shù)據(jù)集屬性Table 1 The attributes of datasets

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

3.1 滲流實驗

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

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

3.2 相變值

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

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

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

3.3 影響力模擬

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

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

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

3.4 平均影響力分析

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

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

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

4 結(jié)束語

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