基于最小點覆蓋和反饋點集的社交網絡影響最大化算法

許宇光 潘驚治 謝惠揚

?

基于最小點覆蓋和反饋點集的社交網絡影響最大化算法

許宇光①潘驚治①謝惠揚*②

①(北京大學信息科學技術學院 北京 100871)②(北京林業大學理學院 北京 100083)

社交網絡中的影響最大化問題是指在特定的傳播模型下，如何尋找個最具影響力的節點使得在該模型下社交網絡中被影響的節點最多，信息傳播的范圍最廣。該問題是一個優化問題，并且已經被證明是NP-難的。考慮到圖的最小點覆蓋和反饋點集中的頂點對圖的連通性影響較大，該文提出一種基于最小點覆蓋和反饋點集的社交網絡影響最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)，并給出了具體的仿真實驗和分析。實驗結果表明，與最新的算法比較，該算法得到的節點集在多種模型下都具有優異的傳播效果，例如在獨立級聯模型和加權級聯模型中超過當前最好的算法，并且還具有更快的收斂速度。

社交網絡；影響最大化；傳播模型；最小點覆蓋；反饋點集

1 引言

社交網絡是指由個體及個體之間的關系所組成的一個復雜網絡，它與交通網絡，通訊網絡和生物網絡等其他復雜網絡相比，包含了更加海量和多元化的信息。自從社交網絡出現以來[1,2]，它便在社會個體的信息傳播、思想引導和相互影響中發揮著重大作用。近年來，隨著大規模在線社交網絡(如人人，Facebook, Twitter和微博等)的迅速發展，從個人到個人和從個人到群體的相互作用中探索社會影響引起了人們的廣泛興趣，這是因為社會影響可以作為一種微妙的力量控制社交網絡的動態性。為此，關于在大規模社會網絡中挖掘對信息和思想的傳播有影響的個體集的研究受到了大量學者的青睞。其中，一個關鍵問題是影響最大化問題，即如何選擇個初始節點，使得它們在社交網絡中的影響最大化。

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

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

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

2 傳播模型

在研究社交網絡時，社交網絡通常被抽象成一個有向(無向)圖，圖中的節點代表參與社會活動的人，邊代表人與人之間的聯系。對于給定的社會網絡，在網絡中尋找影響力節點集，需要借助于相應的傳播模型。線性閾值模型、獨立級聯模型和加權級聯模型是3個常用的傳播模型。在這些模型中，節點有活躍和不活躍兩種狀態可以選擇。其中個體處于活躍狀態時，表示該個體接受了這個信息；處于不活躍狀態時，表示該個體沒有接受這個信息。隨著不活躍節點的活躍鄰居數目的增加，節點也越傾向于變為活躍狀態。

線性閾值模型(Linear Threshold Model, LTM)在線性閾值模型中，一個節點是否受到影響從不活躍狀態變為活躍狀態是由其鄰居的共同影響力決定的。對于節點的鄰居節點，將對的影響記為，則有。在該模型中，如果節點受活躍鄰居的影響總和超過某個閾值，則由不活躍狀態變為活躍狀態。即滿足公式時，節點被激活(即由不活躍狀態變為活躍狀態)，其中()表示的活躍鄰居節點集。可以看出，越大，則節點越不容易被激活。因此可以反映出節點被激活的傾向性[23]。

獨立級聯模型(Independent Cascade Model, ICM) 在獨立級聯模型中，節點只有在剛被激活時才可以嘗試去激活其鄰居。假設是一個在時刻剛被激活的節點，則對于的每個不活躍鄰居,可以以概率激活。若激活成功，則節點在時刻變為活躍節點；若不成功，仍然保持不活躍狀態。無論是否成功激活其鄰居，在以后的時刻都不能再嘗試激活其他節點。如果在時刻不活躍節點有多個鄰居都剛被激活，則其鄰居節點對其的激活順序對于最后結果沒有影響。概率不依賴于之前所有對的激活嘗試。傳播過程以這種方式不斷進行直到沒有剛被激活的節點時停止[10]。

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

3 MVCFVS算法

由于社交網絡通常被抽象成圖來研究，所以本文的算法在理論上把圖作為研究對象，最后在真實的社交網絡數據集上進行實驗來驗證。

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

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

樹最小點覆蓋算法如表1所示。

表1 樹最小點覆蓋算法

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

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

本文為給出MVCFVS算法，需要先找到圖的反饋點集，于是本文提出了一個簡單的圖的反饋點集算法：

圖反饋點集算法如表2所示。

表2 圖反饋點集算法

定理2 對于任意圖，算法2都得到的一個反饋點集。

證明 首先，對于任意連通圖，經過步驟1后所得之圖都是連通圖，因為每次刪去的都是1-點。其次，若一個圖含有圈，那么經過步驟1后一定不是空圖。所以，當算法結束時，即對應的是空圖，所以對應的的每個分支都是樹，從而，結論成立。 證畢

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

MVCFVS算法如表3所示。

表3　MVCFVS算法

因為反饋點集中的每個頂點都屬于一個圈中，故有理由認為他們的全局影響力比較大。另外，最小點覆蓋中的頂點的局部影響力比較大，從而可以認為由此算法篩選出來的個頂點的影響力比較大。下一節將給出具體的實驗。

4 實驗

為了驗證算法的有效性，我們在真實的社交網絡數據上進行了實驗，用基于最小點覆蓋和反饋點集的影響最大化算法(MVCFVS)在這些真實社交網絡數據上選出種子節點，并通過不同的傳播模型模擬他們的實際影響傳播效果，然后和其他幾種節點選擇方法的影響傳播效果比較，評價各自的優缺點，最后分析有這樣的表現的原因，總結本算法的使用條件。

本節主要分為兩個部分：第1部分簡要介紹實驗中用到的數據集和用于作對比的其他節點選擇算法；第2部分從不同的方面來分析實驗結果，得出結論。

4.1 數據集和算法介紹

為了顯示算法的實驗效果，實驗中用到的來自真實社交網絡中的數據集有如下3個：

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

Email-Enron[27]該數據是美國聯邦能源監管委員會在調查安然公司破產案的過程中發布到網上的安然公司的郵件通信網絡。其中，節點代表電子郵件的地址，邊代表郵件地址之間的通信，如果兩個地址之間至少發過一封郵件，那么這兩個地址之間存在一條邊。該網絡是一個無向簡單網絡，覆蓋約五十萬封電子郵件數據集內的所有電子郵件通信，共包含36692個節點，183831條邊。

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

為了和其他節點選擇算法作對比，選擇了如下幾個節點選擇方法：

隨機選擇(Random) 一種簡單的節點選擇方法，這種方法完全隨機地選出個初始節點。

局部中心度算法(Local Centrality, LC) 節點的鄰居節點集為out1(), out1()中所有節點的鄰居節點集的總集合為out2(), out2()中所有節點的鄰居節點集的總集合為out3()；設,,分別為的相應層次鄰居節點集out1(), out2(), out3()的影響度。對于無符號網絡，影響度定義為鄰居節點集的元素個數。節點的潛在影響力值PI定義為：，其中定義為對所有未激活鄰居節點的影響力之和：

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

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

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

4.2 實驗結果

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

圖1比較了在CA-HepTh網絡上4.1節中的6個節點選擇方法在各個傳播模型上的表現。其中，橫坐標表示初始活躍節點(種子節點)集合的大小，即參數的大小，的取值范圍從0到50，縱坐標表示最終的影響效果，即最終活躍節點數目。

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

圖1(b)是6個不同算法(包括DDIC算法)選出的種子節點在獨立級聯模型下的傳播效果()，可以看出，本算法(MVCFVS)是表現最好的。

圖1(c)是5個不同算法選出的種子節點在加權級聯模型下的傳播效果(,是節點的度)，本算法(MVCFVS)和按照度選擇方法(Degree)結果相似。

總的來說，MVCFVS算法在CA-HepTh網絡上表現不錯，特別是對于獨立級聯模型和加權級聯模型，它能夠通過較小的種子節點集合去影響更多的節點，和按照度選擇方法(Degree)效果相似是因為本算法在進行節點選擇時用到了最大度的思想，且由于CA-HepTh網絡本身的局部中心性，導致本算法和Degree方法選出的種子節點有較大的重合。

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

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

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

總的來說，MVCFVS算法在Email-Enron網絡上3種模型下的表現比其他算法都好，特別是對于獨立級聯模型和加權級聯模型，它收斂的速度最快，和Degree算法和MDD算法比較起來，本算法能夠通過較小的種子節點集合去影響更多的節點。

圖3比較了在Facebook-Combined網絡上6個節點選擇方法在各個傳播模型上的表現。

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

圖3(b)是6個不同算法選出的種子節點在獨立級聯模型下的傳播效果()，可以看出，本文算法(MVCFVS)和Degree方法、MDD方法接近。

圖3(c)是5個不同算法選出的種子節點在加權級聯模型下的傳播效果(,是節點的度)，可以看出，本文算法(MVCFVS)和Degree方

圖1 CA-HepTh網絡上各個算法在3個模型下的實驗對比

圖2 Email-Enron網絡上各個算法在3個模型下的實驗對比

圖3 Facebook-Combined網絡上各個算法在3個模型下的實驗對比

法、MDD方法接近。

總的來說，在這3種模型下，MVCFVS算法在Facebook-Combined網絡上表現和Degree算法、MDD算法相似，但比其他文獻的算法好。這是因為Facebook-Combined網絡是一個ego網絡，大多數節點會團結在某個節點周圍，使得本文算法的影響力函數和Degree算法、MDD算法效果相似，選出的節點集合也相似，最終的傳播效果也相似。

5 結束語

本文提出了一種求解社交網絡影響最大化的算法MVCFVS。通過和不同的節點選擇算法在不同的數據集上實驗比較發現，算法MVCFVS比較適用于獨立級聯模型和加權級聯模型，并且收斂速度很快，在取較小值時，就能影響非常多的節點。在規模較大且不是那么集中的網絡中采用本算法選取種子節點，效果會更好。當然，閾值越大，最終活躍節點數越少；影響概率越大，最終活躍節點數越多。并且概率對于傳播模型的影響非常顯著。

另一方面，FC算法在求解反饋點集時只考慮了頂點度的影響，并沒有考慮圖的整體結構，故得到的反饋點集可能會有一定的局限性，即反饋點集中包含的頂點可能會多一些，從而影響了算法FC選出的個頂點的傳播效果。為此，我們需要對FC算法在求解反饋點集這一步進行更深入的研究，這將是我們后續探索的工作。

[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年生，博士生，研究方向為計算機軟件與理論.

潘驚治： 女，1992年生，碩士生，研究方向為社交網絡.

謝惠揚： 女，1963年生，教授，研究方向為應用數學.

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；網絡出版：2016-03-09

謝惠揚 xhyang@bjfu.edu.cn

國家自然科學基金(61370193)