基于最小點(diǎn)覆蓋和反饋點(diǎn)集的社交網(wǎng)絡(luò)影響最大化算法

許宇光 潘驚治 謝惠揚(yáng)

?

基于最小點(diǎn)覆蓋和反饋點(diǎn)集的社交網(wǎng)絡(luò)影響最大化算法

許宇光①潘驚治①謝惠揚(yáng)*②

①(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)②(北京林業(yè)大學(xué)理學(xué)院 北京 100083)

社交網(wǎng)絡(luò)中的影響最大化問題是指在特定的傳播模型下，如何尋找個(gè)最具影響力的節(jié)點(diǎn)使得在該模型下社交網(wǎng)絡(luò)中被影響的節(jié)點(diǎn)最多，信息傳播的范圍最廣。該問題是一個(gè)優(yōu)化問題，并且已經(jīng)被證明是NP-難的?？紤]到圖的最小點(diǎn)覆蓋和反饋點(diǎn)集中的頂點(diǎn)對(duì)圖的連通性影響較大，該文提出一種基于最小點(diǎn)覆蓋和反饋點(diǎn)集的社交網(wǎng)絡(luò)影響最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)，并給出了具體的仿真實(shí)驗(yàn)和分析。實(shí)驗(yàn)結(jié)果表明，與最新的算法比較，該算法得到的節(jié)點(diǎn)集在多種模型下都具有優(yōu)異的傳播效果，例如在獨(dú)立級(jí)聯(lián)模型和加權(quán)級(jí)聯(lián)模型中超過當(dāng)前最好的算法，并且還具有更快的收斂速度。

社交網(wǎng)絡(luò)；影響最大化；傳播模型；最小點(diǎn)覆蓋；反饋點(diǎn)集

1 引言

社交網(wǎng)絡(luò)是指由個(gè)體及個(gè)體之間的關(guān)系所組成的一個(gè)復(fù)雜網(wǎng)絡(luò)，它與交通網(wǎng)絡(luò)，通訊網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等其他復(fù)雜網(wǎng)絡(luò)相比，包含了更加海量和多元化的信息。自從社交網(wǎng)絡(luò)出現(xiàn)以來[1,2]，它便在社會(huì)個(gè)體的信息傳播、思想引導(dǎo)和相互影響中發(fā)揮著重大作用。近年來，隨著大規(guī)模在線社交網(wǎng)絡(luò)(如人人，F(xiàn)acebook, Twitter和微博等)的迅速發(fā)展，從個(gè)人到個(gè)人和從個(gè)人到群體的相互作用中探索社會(huì)影響引起了人們的廣泛興趣，這是因?yàn)樯鐣?huì)影響可以作為一種微妙的力量控制社交網(wǎng)絡(luò)的動(dòng)態(tài)性。為此，關(guān)于在大規(guī)模社會(huì)網(wǎng)絡(luò)中挖掘?qū)π畔⒑退枷氲膫鞑ビ杏绊懙膫€(gè)體集的研究受到了大量學(xué)者的青睞。其中，一個(gè)關(guān)鍵問題是影響最大化問題，即如何選擇個(gè)初始節(jié)點(diǎn)，使得它們?cè)谏缃痪W(wǎng)絡(luò)中的影響最大化。

關(guān)于影響力最大化算法的研究，目前主要有基于貪心思想的方法和啟發(fā)式方法。其中，基于貪心思想的方法選出的節(jié)點(diǎn)傳播效果較好，但是選擇節(jié)點(diǎn)時(shí)算法效率較低，因此這類方法目前主要的研究方向是如何降低算法的運(yùn)行時(shí)間，提高算法效率。文獻(xiàn)[7,8]首次將影響最大化問題引入到社交網(wǎng)絡(luò)中，他們考慮了個(gè)體之間的社會(huì)關(guān)系并提出了一種概率信息傳播模型。隨后，文獻(xiàn)[9,10]首次將影響最大化問題描述成離散優(yōu)化問題，并在兩個(gè)不同的模型下，即線性值模型和獨(dú)立級(jí)聯(lián)模型，研究了此問題。他們證明了影響最大化問題在上述兩個(gè)模型下是NP-難的。同時(shí)，他們提出了一種貪心算法，并證明了所提算法在這兩種模型下的性能比為。 考慮到貪心算法效率不高的問題，文獻(xiàn)[11]提出了“Lazy-forward”的優(yōu)化策略來選擇初始節(jié)點(diǎn)。2014年，文獻(xiàn)[12]在研究基于線性閾值模型下的影響最大化問題時(shí)，為線性閾值的傳播方程推導(dǎo)出了理論上界[13]。2014年，文獻(xiàn)[14]提出貪心算法本質(zhì)上是一種自一致性排序，即自身的排序和影響范圍的增益相一致。

通常啟發(fā)式方法選出的節(jié)點(diǎn)傳播效果不如基于貪心思想的方法，但啟發(fā)式方法算法效率較高，因此這類方法目前主要的研究方向是如何在保持其效率較高優(yōu)勢(shì)的前提下，改善選出節(jié)點(diǎn)的傳播效果。文獻(xiàn)[15]基于度提出了“Degree Discount”方法。文獻(xiàn)[16]根據(jù)模擬退火法啟發(fā)式求解影響最大化問題。文獻(xiàn)[16-18]首次將潛伏限制加到線型闕值模型下的影響最大化問題中，并稱其為快速信息傳播問題(fast information propagation problem)。他們證明了該問題是NP-難的，并給出了兩個(gè)啟發(fā)式的算法來求解該問題。近年來，文獻(xiàn)[19]提出了概括影響力公式的問題。文獻(xiàn)[20]研究了社區(qū)結(jié)構(gòu)和影響最大化問題的關(guān)系。文獻(xiàn)[21]提出一種基于-核的社會(huì)網(wǎng)絡(luò)影響最大化算法。文獻(xiàn)[22]提出一種在獨(dú)立級(jí)聯(lián)模型下估計(jì)節(jié)點(diǎn)級(jí)聯(lián)影響力的方法。

基于上述考慮以及圖最小點(diǎn)覆蓋和反饋點(diǎn)集中頂點(diǎn)的重要性，本文提出了一種基于最小覆蓋集和反饋點(diǎn)集的近似求解影響最大化的算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)。該算法同時(shí)考慮了最小點(diǎn)覆蓋和反饋點(diǎn)集中頂點(diǎn)的影響力，具有很好的效果。實(shí)驗(yàn)結(jié)果表明，所提算法可以較快地找到具有較好影響范圍的節(jié)點(diǎn)集。本文第2節(jié)介紹3種常用的傳播模型；第3節(jié)介紹與本算法相關(guān)的概念，詳細(xì)描述本文的算法，并對(duì)本算法的時(shí)間復(fù)雜度進(jìn)行分析；第4節(jié)介紹實(shí)驗(yàn)設(shè)計(jì)及實(shí)驗(yàn)結(jié)果分析；第5節(jié)對(duì)本文成果進(jìn)行了概括并探討未來的工作。

2 傳播模型

在研究社交網(wǎng)絡(luò)時(shí)，社交網(wǎng)絡(luò)通常被抽象成一個(gè)有向(無向)圖，圖中的節(jié)點(diǎn)代表參與社會(huì)活動(dòng)的人，邊代表人與人之間的聯(lián)系。對(duì)于給定的社會(huì)網(wǎng)絡(luò)，在網(wǎng)絡(luò)中尋找影響力節(jié)點(diǎn)集，需要借助于相應(yīng)的傳播模型。線性閾值模型、獨(dú)立級(jí)聯(lián)模型和加權(quán)級(jí)聯(lián)模型是3個(gè)常用的傳播模型。在這些模型中，節(jié)點(diǎn)有活躍和不活躍兩種狀態(tài)可以選擇。其中個(gè)體處于活躍狀態(tài)時(shí)，表示該個(gè)體接受了這個(gè)信息；處于不活躍狀態(tài)時(shí)，表示該個(gè)體沒有接受這個(gè)信息。隨著不活躍節(jié)點(diǎn)的活躍鄰居數(shù)目的增加，節(jié)點(diǎn)也越傾向于變?yōu)榛钴S狀態(tài)。

線性閾值模型(Linear Threshold Model, LTM)在線性閾值模型中，一個(gè)節(jié)點(diǎn)是否受到影響從不活躍狀態(tài)變?yōu)榛钴S狀態(tài)是由其鄰居的共同影響力決定的。對(duì)于節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，將對(duì)的影響記為，則有。在該模型中，如果節(jié)點(diǎn)受活躍鄰居的影響總和超過某個(gè)閾值，則由不活躍狀態(tài)變?yōu)榛钴S狀態(tài)。即滿足公式時(shí)，節(jié)點(diǎn)被激活(即由不活躍狀態(tài)變?yōu)榛钴S狀態(tài))，其中()表示的活躍鄰居節(jié)點(diǎn)集?？梢钥闯?，越大，則節(jié)點(diǎn)越不容易被激活。因此可以反映出節(jié)點(diǎn)被激活的傾向性[23]。

獨(dú)立級(jí)聯(lián)模型(Independent Cascade Model, ICM) 在獨(dú)立級(jí)聯(lián)模型中，節(jié)點(diǎn)只有在剛被激活時(shí)才可以嘗試去激活其鄰居。假設(shè)是一個(gè)在時(shí)刻剛被激活的節(jié)點(diǎn)，則對(duì)于的每個(gè)不活躍鄰居,可以以概率激活。若激活成功，則節(jié)點(diǎn)在時(shí)刻變?yōu)榛钴S節(jié)點(diǎn)；若不成功，仍然保持不活躍狀態(tài)。無論是否成功激活其鄰居，在以后的時(shí)刻都不能再嘗試激活其他節(jié)點(diǎn)。如果在時(shí)刻不活躍節(jié)點(diǎn)有多個(gè)鄰居都剛被激活，則其鄰居節(jié)點(diǎn)對(duì)其的激活順序?qū)τ谧詈蠼Y(jié)果沒有影響。概率不依賴于之前所有對(duì)的激活嘗試。傳播過程以這種方式不斷進(jìn)行直到?jīng)]有剛被激活的節(jié)點(diǎn)時(shí)停止[10]。

加權(quán)級(jí)聯(lián)模型(Weighted Cascade Model, WCM) 加權(quán)級(jí)聯(lián)模型可以看作是獨(dú)立級(jí)聯(lián)模型的一個(gè)特例。在該模型中，節(jié)點(diǎn)激活其不活躍鄰居節(jié)點(diǎn)的概率與節(jié)點(diǎn)的度有關(guān)，。故當(dāng)一個(gè)節(jié)點(diǎn)有很多鄰居時(shí)，每個(gè)鄰居對(duì)其的影響就會(huì)被平均到一個(gè)非常小的值，這在某種程度上可以反映出真實(shí)世界中的人際關(guān)系。例如，如果一個(gè)人只有一個(gè)朋友，那么這個(gè)朋友對(duì)他的建議就非常具有影響力，而如果他有很多朋友，那么其中一個(gè)朋友的建議對(duì)他作何決定的影響并不大[10]。

3 MVCFVS算法

由于社交網(wǎng)絡(luò)通常被抽象成圖來研究，所以本文的算法在理論上把圖作為研究對(duì)象，最后在真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)來驗(yàn)證。

本文所言之圖皆指無向有限連通簡(jiǎn)單圖(無環(huán)無重邊)。對(duì)于任意圖，用()和()分別表示圖的頂點(diǎn)集和邊集。圖的一個(gè)點(diǎn)覆蓋是指()的一個(gè)頂點(diǎn)子集，使得()中的每條邊至少有一個(gè)端點(diǎn)在中。如果不存在任何覆蓋滿足，那么稱是的最小點(diǎn)覆蓋。求一個(gè)圖的最小點(diǎn)覆蓋并非易事，該問題是NP-完全的[24]。

對(duì)于一個(gè)圖，令是中的一個(gè)頂點(diǎn)。我們用N()表示中與相鄰的所有頂點(diǎn)構(gòu)成的集合。頂點(diǎn)的度，記作，定義成N()含有頂點(diǎn)的個(gè)數(shù)，即=|N()|。若=，那么稱是的一個(gè)-點(diǎn)。和分別表示圖的最大度和最小度。若中任意兩個(gè)頂點(diǎn)之間都存在一條路，那么稱為是連通的；否則，稱為不連通。如果是不連通的，那么至少含有兩個(gè)連通分支，用表示的連通分支的個(gè)數(shù)。不含圈的圖稱為無圈圖，連通的無圈圖稱為樹。

樹最小點(diǎn)覆蓋算法如表1所示。

表1 樹最小點(diǎn)覆蓋算法

定理1 對(duì)于任意樹，算法1都得到的最小覆蓋集。

證明 首先，我們證明存在一個(gè)最小點(diǎn)覆蓋不含1-點(diǎn)。否則若的某個(gè)最小點(diǎn)覆蓋含有1-點(diǎn)，那么將1-點(diǎn)從中刪去，然后將與其相鄰的頂點(diǎn)加入中，從而得到一個(gè)新的最小點(diǎn)覆蓋。令是的一個(gè)不含1-點(diǎn)的最小點(diǎn)覆蓋，那么即是按算法1得到的。因?yàn)?，每個(gè)1-點(diǎn)關(guān)聯(lián)的邊如要被覆蓋，那么與該1-點(diǎn)相鄰的頂點(diǎn)必定在最小覆蓋中。故包含算法1所選出的所有的頂點(diǎn)。另一方面，容易驗(yàn)證算法1選出的頂點(diǎn)集是的一個(gè)覆蓋，所以，結(jié)論成立。 證畢

本文為給出MVCFVS算法，需要先找到圖的反饋點(diǎn)集，于是本文提出了一個(gè)簡(jiǎn)單的圖的反饋點(diǎn)集算法：

圖反饋點(diǎn)集算法如表2所示。

表2 圖反饋點(diǎn)集算法

定理2 對(duì)于任意圖，算法2都得到的一個(gè)反饋點(diǎn)集。

證明 首先，對(duì)于任意連通圖，經(jīng)過步驟1后所得之圖都是連通圖，因?yàn)槊看蝿h去的都是1-點(diǎn)。其次，若一個(gè)圖含有圈，那么經(jīng)過步驟1后一定不是空?qǐng)D。所以，當(dāng)算法結(jié)束時(shí)，即對(duì)應(yīng)的是空?qǐng)D，所以對(duì)應(yīng)的的每個(gè)分支都是樹，從而，結(jié)論成立。 證畢

下面將應(yīng)用上述兩個(gè)算法給出本文求解影響最大化的算法MVCFVS。我們的思想是：對(duì)于一個(gè)圖，首先利用算法2求出的一個(gè)反饋點(diǎn)集；其次，對(duì)于的每個(gè)樹分支T，利用算法1求出樹分支的最小點(diǎn)覆蓋集C。第三，令含有個(gè)樹分支，對(duì)于中的頂點(diǎn)，我們將按下述定義的影響力函數(shù)()，從大到小選出最有影響力的個(gè)頂點(diǎn)。

MVCFVS算法如表3所示。

表3　MVCFVS算法

因?yàn)榉答侟c(diǎn)集中的每個(gè)頂點(diǎn)都屬于一個(gè)圈中，故有理由認(rèn)為他們的全局影響力比較大。另外，最小點(diǎn)覆蓋中的頂點(diǎn)的局部影響力比較大，從而可以認(rèn)為由此算法篩選出來的個(gè)頂點(diǎn)的影響力比較大。下一節(jié)將給出具體的實(shí)驗(yàn)。

4 實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，我們?cè)谡鎸?shí)的社交網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)，用基于最小點(diǎn)覆蓋和反饋點(diǎn)集的影響最大化算法(MVCFVS)在這些真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)上選出種子節(jié)點(diǎn)，并通過不同的傳播模型模擬他們的實(shí)際影響傳播效果，然后和其他幾種節(jié)點(diǎn)選擇方法的影響傳播效果比較，評(píng)價(jià)各自的優(yōu)缺點(diǎn)，最后分析有這樣的表現(xiàn)的原因，總結(jié)本算法的使用條件。

本節(jié)主要分為兩個(gè)部分：第1部分簡(jiǎn)要介紹實(shí)驗(yàn)中用到的數(shù)據(jù)集和用于作對(duì)比的其他節(jié)點(diǎn)選擇算法；第2部分從不同的方面來分析實(shí)驗(yàn)結(jié)果，得出結(jié)論。

4.1 數(shù)據(jù)集和算法介紹

為了顯示算法的實(shí)驗(yàn)效果，實(shí)驗(yàn)中用到的來自真實(shí)社交網(wǎng)絡(luò)中的數(shù)據(jù)集有如下3個(gè)：

CA-HepTh[26]該數(shù)據(jù)來自于arXiv，涵蓋了提交到該網(wǎng)站的高能物理(High Energy Physics- Theory)分類下的作者之間的科學(xué)合作。如果作者和作者合作了一篇文章，那么節(jié)點(diǎn)和節(jié)點(diǎn)之間存在一條無向邊；如果一篇文章是由個(gè)作者共同合作完成的，那么這個(gè)節(jié)點(diǎn)之間構(gòu)成了一個(gè)個(gè)節(jié)點(diǎn)的完全圖。該數(shù)據(jù)涵蓋了從1993年1月至2003年4月期間(124個(gè)月)的論文，共包含9877個(gè)節(jié)點(diǎn)，25998條邊。

Email-Enron[27]該數(shù)據(jù)是美國(guó)聯(lián)邦能源監(jiān)管委員會(huì)在調(diào)查安然公司破產(chǎn)案的過程中發(fā)布到網(wǎng)上的安然公司的郵件通信網(wǎng)絡(luò)。其中，節(jié)點(diǎn)代表電子郵件的地址，邊代表郵件地址之間的通信，如果兩個(gè)地址之間至少發(fā)過一封郵件，那么這兩個(gè)地址之間存在一條邊。該網(wǎng)絡(luò)是一個(gè)無向簡(jiǎn)單網(wǎng)絡(luò)，覆蓋約五十萬封電子郵件數(shù)據(jù)集內(nèi)的所有電子郵件通信，共包含36692個(gè)節(jié)點(diǎn)，183831條邊。

Facebook-Combined(FC)[28]該數(shù)據(jù)來自Facebook的“社交圈”(或“朋友列表”)，是一個(gè)ego網(wǎng)絡(luò)(所謂ego網(wǎng)絡(luò)，指的是網(wǎng)絡(luò)的節(jié)點(diǎn)是由唯一的一個(gè)中心節(jié)點(diǎn)(ego)，以及這個(gè)節(jié)點(diǎn)的鄰居(alters)組成的，它的邊只包括了ego和alter之間，以及alter與alter之間的邊)。共包含4039個(gè)節(jié)點(diǎn)，88234條邊。

為了和其他節(jié)點(diǎn)選擇算法作對(duì)比，選擇了如下幾個(gè)節(jié)點(diǎn)選擇方法：

隨機(jī)選擇(Random) 一種簡(jiǎn)單的節(jié)點(diǎn)選擇方法，這種方法完全隨機(jī)地選出個(gè)初始節(jié)點(diǎn)。

局部中心度算法(Local Centrality, LC) 節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集為out1(), out1()中所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集的總集合為out2(), out2()中所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集的總集合為out3()；設(shè),,分別為的相應(yīng)層次鄰居節(jié)點(diǎn)集out1(), out2(), out3()的影響度。對(duì)于無符號(hào)網(wǎng)絡(luò)，影響度定義為鄰居節(jié)點(diǎn)集的元素個(gè)數(shù)。節(jié)點(diǎn)的潛在影響力值PI定義為：，其中定義為對(duì)所有未激活鄰居節(jié)點(diǎn)的影響力之和：

混合度分解算法(MDD) 在計(jì)算k-核的過程中考慮了剩余度(residual degree)和排出度(exhausted degree)，該算法中的可調(diào)參數(shù)在實(shí)驗(yàn)中被設(shè)置為0.7。

基于度的啟發(fā)式算法(DegreeDiscountIC, DDIC) 該算法是在傳統(tǒng)基于度的啟發(fā)式算法基礎(chǔ)上改進(jìn)后適用于獨(dú)立級(jí)聯(lián)模型的算法。在Degree Discount 中，如果某個(gè)節(jié)點(diǎn)已經(jīng)被選入種子集合中，則該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)(不在種子集合中的節(jié)點(diǎn))的度相應(yīng)地減1。而DegreeDiscountIC算法使用了不同的折扣方法，當(dāng)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)已經(jīng)被選入種子節(jié)點(diǎn)中，那么將以概率被影響，這樣的話就沒必要將選入種子節(jié)點(diǎn)中。當(dāng)比較小的時(shí)候，忽略的多跳鄰居節(jié)點(diǎn)對(duì)其的間接影響，只關(guān)注直接影響。，其中，表示節(jié)點(diǎn)的度，初始為0，對(duì)于的鄰居節(jié)點(diǎn)中未加入種子節(jié)點(diǎn)集合的節(jié)點(diǎn)每加1,也加1。

基于最小點(diǎn)覆蓋和反饋點(diǎn)集的影響最大化算法(MVCFVS) 使用第3節(jié)中介紹的算法3選擇初始活躍節(jié)點(diǎn)集合，該算法先找到網(wǎng)絡(luò)的反饋點(diǎn)集，再在的每個(gè)分支上找最小點(diǎn)覆蓋集合，最后在候選集根據(jù)影響力函數(shù)選出個(gè)節(jié)點(diǎn)。

4.2 實(shí)驗(yàn)結(jié)果

將以上6種節(jié)點(diǎn)選擇方法選出的節(jié)點(diǎn)作為初始的活躍節(jié)點(diǎn)，分別按照線性閾值模型、獨(dú)立級(jí)聯(lián)模型、加權(quán)級(jí)聯(lián)模型的傳播方式進(jìn)行影響力傳播，對(duì)最終的傳播效果進(jìn)行比較。由于基于度的啟發(fā)式算法(DegreeDiscountIC)是適用于獨(dú)立級(jí)聯(lián)模型的節(jié)點(diǎn)選擇算法，所以我們只在獨(dú)立級(jí)聯(lián)模型下加入了這種算法(DDIC)作比較。為了保證算法的有效性，在初始活躍節(jié)點(diǎn)集上進(jìn)行10000次模擬，取這10000次結(jié)果的平均值作為傳播模型的最終結(jié)果。其結(jié)果如下：

圖1比較了在CA-HepTh網(wǎng)絡(luò)上4.1節(jié)中的6個(gè)節(jié)點(diǎn)選擇方法在各個(gè)傳播模型上的表現(xiàn)。其中，橫坐標(biāo)表示初始活躍節(jié)點(diǎn)(種子節(jié)點(diǎn))集合的大小，即參數(shù)的大小，的取值范圍從0到50，縱坐標(biāo)表示最終的影響效果，即最終活躍節(jié)點(diǎn)數(shù)目。

圖1(a)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在線性閾值模型下的傳播效果()，可以看出，本文算法(MVCFVS)雖不如Degree方法和LC方法，但和他們接近，且比Rand方法和MDD方法好得多。

圖1(b)是6個(gè)不同算法(包括DDIC算法)選出的種子節(jié)點(diǎn)在獨(dú)立級(jí)聯(lián)模型下的傳播效果()，可以看出，本算法(MVCFVS)是表現(xiàn)最好的。

圖1(c)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在加權(quán)級(jí)聯(lián)模型下的傳播效果(,是節(jié)點(diǎn)的度)，本算法(MVCFVS)和按照度選擇方法(Degree)結(jié)果相似。

總的來說，MVCFVS算法在CA-HepTh網(wǎng)絡(luò)上表現(xiàn)不錯(cuò)，特別是對(duì)于獨(dú)立級(jí)聯(lián)模型和加權(quán)級(jí)聯(lián)模型，它能夠通過較小的種子節(jié)點(diǎn)集合去影響更多的節(jié)點(diǎn)，和按照度選擇方法(Degree)效果相似是因?yàn)楸舅惴ㄔ谶M(jìn)行節(jié)點(diǎn)選擇時(shí)用到了最大度的思想，且由于CA-HepTh網(wǎng)絡(luò)本身的局部中心性，導(dǎo)致本算法和Degree方法選出的種子節(jié)點(diǎn)有較大的重合。

圖2比較了在Email-Enron網(wǎng)絡(luò)上6個(gè)節(jié)點(diǎn)選擇方法在各個(gè)傳播模型上的表現(xiàn)。圖2(a)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在線性閾值模型下的傳播效果()，可以看出，本文算法(MVCFVS)在時(shí)不如Degree方法和MDD方法，但是在時(shí)和他們接近，且比Rand方法和MDD方法好得多。通過仔細(xì)比較這些方法選出的不同節(jié)點(diǎn)，發(fā)現(xiàn)造成這種結(jié)果是因?yàn)镈egree方法和MDD方法一開始就將度最大的節(jié)點(diǎn)選入了種子節(jié)點(diǎn)集合，使得他們能夠在早期快速影響較多的節(jié)點(diǎn)，而本算法是在稍晚些時(shí)候才將這些度居榜首的節(jié)點(diǎn)選入種子節(jié)點(diǎn)集合；后期隨著Degree方法和MDD方法的缺陷逐漸顯現(xiàn)，本算法的表現(xiàn)越來越好，開始追上Degree方法，趕超MDD方法。

圖2(b)是6個(gè)不同算法選出的種子節(jié)點(diǎn)在獨(dú)立級(jí)聯(lián)模型下的傳播效果()，可以看出，本算法(MVCFVS)是最先收斂的，即在較小時(shí)比起Degree方法和MDD方法本算法能影響更多的節(jié)點(diǎn)。

圖2(c)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在加權(quán)級(jí)聯(lián)模型下的傳播效果(,是節(jié)點(diǎn)的度)，可以看出，本文算法(MVCFVS)也是最先收斂的，即在較小時(shí)比起Degree方法和MDD方法本文算法能影響更多的節(jié)點(diǎn)。

總的來說，MVCFVS算法在Email-Enron網(wǎng)絡(luò)上3種模型下的表現(xiàn)比其他算法都好，特別是對(duì)于獨(dú)立級(jí)聯(lián)模型和加權(quán)級(jí)聯(lián)模型，它收斂的速度最快，和Degree算法和MDD算法比較起來，本算法能夠通過較小的種子節(jié)點(diǎn)集合去影響更多的節(jié)點(diǎn)。

圖3比較了在Facebook-Combined網(wǎng)絡(luò)上6個(gè)節(jié)點(diǎn)選擇方法在各個(gè)傳播模型上的表現(xiàn)。

圖3(a)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在線性閾值模型下的傳播效果()，可以看出，本文算法(MVCFVS), Degree方法和MDD方法接近。

圖3(b)是6個(gè)不同算法選出的種子節(jié)點(diǎn)在獨(dú)立級(jí)聯(lián)模型下的傳播效果()，可以看出，本文算法(MVCFVS)和Degree方法、MDD方法接近。

圖3(c)是5個(gè)不同算法選出的種子節(jié)點(diǎn)在加權(quán)級(jí)聯(lián)模型下的傳播效果(,是節(jié)點(diǎn)的度)，可以看出，本文算法(MVCFVS)和Degree方

圖1 CA-HepTh網(wǎng)絡(luò)上各個(gè)算法在3個(gè)模型下的實(shí)驗(yàn)對(duì)比

圖2 Email-Enron網(wǎng)絡(luò)上各個(gè)算法在3個(gè)模型下的實(shí)驗(yàn)對(duì)比

圖3 Facebook-Combined網(wǎng)絡(luò)上各個(gè)算法在3個(gè)模型下的實(shí)驗(yàn)對(duì)比

法、MDD方法接近。

總的來說，在這3種模型下，MVCFVS算法在Facebook-Combined網(wǎng)絡(luò)上表現(xiàn)和Degree算法、MDD算法相似，但比其他文獻(xiàn)的算法好。這是因?yàn)镕acebook-Combined網(wǎng)絡(luò)是一個(gè)ego網(wǎng)絡(luò)，大多數(shù)節(jié)點(diǎn)會(huì)團(tuán)結(jié)在某個(gè)節(jié)點(diǎn)周圍，使得本文算法的影響力函數(shù)和Degree算法、MDD算法效果相似，選出的節(jié)點(diǎn)集合也相似，最終的傳播效果也相似。

5 結(jié)束語(yǔ)

本文提出了一種求解社交網(wǎng)絡(luò)影響最大化的算法MVCFVS。通過和不同的節(jié)點(diǎn)選擇算法在不同的數(shù)據(jù)集上實(shí)驗(yàn)比較發(fā)現(xiàn)，算法MVCFVS比較適用于獨(dú)立級(jí)聯(lián)模型和加權(quán)級(jí)聯(lián)模型，并且收斂速度很快，在取較小值時(shí)，就能影響非常多的節(jié)點(diǎn)。在規(guī)模較大且不是那么集中的網(wǎng)絡(luò)中采用本算法選取種子節(jié)點(diǎn)，效果會(huì)更好。當(dāng)然，閾值越大，最終活躍節(jié)點(diǎn)數(shù)越少；影響概率越大，最終活躍節(jié)點(diǎn)數(shù)越多。并且概率對(duì)于傳播模型的影響非常顯著。

另一方面，F(xiàn)C算法在求解反饋點(diǎn)集時(shí)只考慮了頂點(diǎn)度的影響，并沒有考慮圖的整體結(jié)構(gòu)，故得到的反饋點(diǎn)集可能會(huì)有一定的局限性，即反饋點(diǎn)集中包含的頂點(diǎn)可能會(huì)多一些，從而影響了算法FC選出的個(gè)頂點(diǎn)的傳播效果。為此，我們需要對(duì)FC算法在求解反饋點(diǎn)集這一步進(jìn)行更深入的研究，這將是我們后續(xù)探索的工作。

[1] WATTS D J and STROGATZ S H. Collective dynamics of 'small-world' networks[J]., 1998, 393(6684): 440-442.

[2] BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512.

[3] SAITO K, NAKANA R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[J]., 2008, 5179: 67-75.

[4] TANG J, SUN J, and YANG Z. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2009: 807-816.

[5] GOYAL A, BONCHI F, and LASKHMANAN L. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search & Data Mining, New York, USA, 2010: 241-250.

[6] WANG C, TANG J, SUN J,. Dynamic social influence analysis through time-dependent factor graphs[C]. Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, Washington, DC, USA, 2011: 239-246.

[7] DOMIGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, 2001: 57-66.

[8] RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Alberta, Canada, 2002: 61-70.

[9] KEMPE D, KLEINBERG J, and TARDOS E. Influential nodes in a diffusion model for social networks[J].,, 2005, 32: 1127-1138.

[10] KEMPE D, KLEINBERG J, and TARDOS E. Maximizing the spread of influence in a social network[C]. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003: 137-146.

[11] LESKOVEC J, KRAUSE A, GUESTRIN C,. Cost- effective outbreak detection in networks[C]. Proceedings of the Kdd 07 ACM SIGKDD International Conference on Knowledge Discovery and Data, Pittsburgh, PA, USA, 2007: 420-429.

[12] ZHOU C and GUO L. A note on influence maximization in social networks from local to global and beyond[C]. Proceedings of the 1th International Conference on Data Science (ICDS), Beijing, China, 2014: 27-28.

[13] ZHOU C, ZHANG P, GUO J,. An upper bound based greedy algorithm for mining top-k influential nodes in social networks [C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data, Seoul, Korea, 2014: 421-422.

[14] CHENG S, SHEN H, HUANG J,. IMRank: influence maximization via finding self-consistent ranking[C]. Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR '14), New York, NY , USA, 2014: 475-484.

[15] CHEN W, WANG Y, and YANG S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 199-208.

[16] JIANG Q, SONG G, CONG G,. Simulated annealing based influence maximization in social networks[C]. Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 127-132.

[17] ZOU F, ZHANG Z, and WU W. Latency-bounded minimum influential node selection in social networks[C]. Proceedings of the Wireless Algorithms, Systems, and Applications, 4th International Conference, Boston, MA, USA, 2009: 519-526.

[18] ZOU F, WILLSON J, ZHANG Z,. Fast information propagation in social networks[J].&, 2010, 2(1): 125-141.

[19] COHEN E, DELLING D, PAJOR T,. Sketch-based influence maximization and computation: scaling up with guarantees[C]. Proceedings of Conference on Information and Knowledge Management, CIKM, Shanghai, China, 2014: 629-638.

[20] JIANG F, JIN S, WU Y,. A uniform framework for community detection via influence maximization in social networks[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Beijing, China, 2014: 27-32.

[21] CAO J, DAN D, XU S,. A-core based algorithm for influence maximization in social networks[J]., 2015, 38(2): 238-248.

[22] LUCIER B, OREN J, and SINGER Y. Singer influence at scale: distributed computation of complex contagion in networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015: 735-744.

[23] GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth [J].2001, 12(3): 211-223.

[24] KARP R M. Reducibility among Combinatorial Problems, Complexity of Computer Computations[M]. New York, USA, Plenum Press, 1972: 85-103.

[25] SCHULZ A. Correctness-proof of a greedy-algorithm for minimum vertex cover of a tree[OL]. http.//cs.stakexchange. com, 2013.

[26] LESKOVEC J, KLEINBERG J, and FALOUTSOS C. Graph evolution: densification and shrink diameters[J]., 2007, 1(1): 1-41.

[27] LESKOVEC J, LANG K, DASGUPTA A,. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]., 2009, 6(1): 29-123.

[28] MCAULEY J and LESKOVEC J. Learning to discover social circles in ego networks[C]. Proceedings of the 26th Annal Conference on Information Processing Systems, Lake Tahoe, NeVada, USA, 2012: 539-547.

許宇光： 男，1984年生，博士生，研究方向?yàn)橛?jì)算機(jī)軟件與理論.

潘驚治： 女，1992年生，碩士生，研究方向?yàn)樯缃痪W(wǎng)絡(luò).

謝惠揚(yáng)： 女，1963年生，教授，研究方向?yàn)閼?yīng)用數(shù)學(xué).

Minimum Vertex Covering and Feedback Vertex Set-based Algorithmfor Influence Maximization in Social Network

XU Yuguang①PAN Jingzhi①XIE Huiyang②

①(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)②(College of Science, Beijing Forestry University, Beijing 100083, China)

Influence maximization is an optimization issue of finding a subset of nodes under a given diffusion model, which can maximize the spread of influence. This optimization issue has been proved to be NP-hard. Leveraging the fact that vertices in minimum vertex covering and feedback vertex set are of great importance for the connectivity of a graph, a heuristic algorithm for influence maximization based on Minimum Vertex Covering and Feedback Vertex Set (MVCFVS). Extensive experiments on various diffusion models against state of the art algorithms are carried out. Specifically, the proposed algorithm performs excellent on Independent Cascade Model (ICM) and Weighted Cascade Model (WCM), which exhibits its great advantages in terms of influence range and convergent speed.

Social network; Influence maximization; Diffusion models; Minimum vertex covering; Feedback vertex set

The National Natural Science Foundation of China (61370193)

TP393

A

1009-5896(2016)04-0795-08

10.11999/JEIT160019

2016-01-15；改回日期：2016-02-26；網(wǎng)絡(luò)出版：2016-03-09

謝惠揚(yáng) xhyang@bjfu.edu.cn

國(guó)家自然科學(xué)基金(61370193)