顏 慶，張 鵬

(山東大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250101)

1 引言

隨著電子設(shè)備的不斷普及以及社交媒體的日趨強(qiáng)大，人們之間的聯(lián)系越來越密切。如何通過社會網(wǎng)絡(luò)中人們之間建立起來的關(guān)系來進(jìn)行信息的傳播，逐漸得到研究者們的關(guān)注。由最初營銷領(lǐng)域的“口碑效應(yīng)”和“病毒式營銷策略”[1～5]的推廣方式，人們發(fā)現(xiàn)可以在人群中選取具有代表性的節(jié)點子集，由它們可以引起更大的級聯(lián)影響，逐步產(chǎn)生出了影響力最大化問題。影響力最大化問題被引入社會網(wǎng)絡(luò)研究領(lǐng)域后，成為近年來的一大研究熱點。自2001年Domingos P等人[4]第一次將影響力最大化問題抽象成一個算法問題以來，各種傳播模型和求解問題的算法也相繼提出，近幾年備受研究者們的關(guān)注，發(fā)表的論文數(shù)量也越來越多。雖然影響力最大化問題的研究已經(jīng)有了十多年的時間，但是迄今為止關(guān)于它的綜述文章卻很少。因此，非常有必要對影響力最大化問題的背景、理論基礎(chǔ)、傳播模型、研究現(xiàn)狀、存在的問題以及未來的研究方向等方面作個較全面、系統(tǒng)的總結(jié)和評述，以期能對后來的研究者提供指導(dǎo)，從而能更有效地解決更多的實際問題。

2 理論基礎(chǔ)

2.1 社會網(wǎng)絡(luò)

社會網(wǎng)絡(luò)表達(dá)的是社會行動者及其之間關(guān)系的集合，社會行動者可以是個人、群體、城市等等。在其形式化的表達(dá)中，用一張關(guān)系圖來表示一個社會網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每個節(jié)點對應(yīng)于一個社會行動者，每條邊對應(yīng)于一對社會行動者之間的關(guān)系(合作、朋友、敵對等)，如圖1所示。近年來，隨著許多大型社交網(wǎng)絡(luò)如Facebook、Twitter、新浪微博、人人網(wǎng)等的興起，社會網(wǎng)絡(luò)也越來越成為研究的熱點。這些社會網(wǎng)絡(luò)上的影響力最大化問題研究對廣告發(fā)布、市場營銷、消息傳遞等多個方面都有十分重要的意義。

Figure 1 Example of social network圖1 社會網(wǎng)絡(luò)示例圖

2.2 影響力傳播模型

將社會網(wǎng)絡(luò)抽象成一張圖G(V,E)，其中V表示圖中的節(jié)點集合，E表示節(jié)點之間邊的集合。圖中的每個節(jié)點具有兩種狀態(tài)：活躍狀態(tài)(Active,接受了某種觀念或購買了某種產(chǎn)品等)和不活躍狀態(tài)(Inactive,還沒有接受或購買)。處于活躍狀態(tài)的節(jié)點對處于不活躍狀態(tài)的節(jié)點存在影響，存在一定的可能性來激活不活躍的節(jié)點。如果某個節(jié)點周圍有越來越多的節(jié)點變?yōu)榛钴S狀態(tài)，則它被激活的可能性就越大。隨著時間的推移，會有越來越多的節(jié)點由不活躍變?yōu)榛钴S狀態(tài)。整個激活過程是不可逆的，一個節(jié)點可以由不活躍狀態(tài)轉(zhuǎn)變?yōu)榛钴S狀態(tài)，反之則不可以。目前在研究影響力最大化問題時，有兩種基本的模型描述：獨立級聯(lián)IC(Independent Cascade)模型[2,6,7]和線性閾值LT(Linear Threshold)模型[7～9]。

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

獨立級聯(lián)模型是基于概率論中的交互粒子系統(tǒng)(Interacting Particles Systems)[10,11]的一種信息傳播模型。給定初始集合A、相鄰節(jié)點之間u對v激活成功的概率pu,v，傳播過程如下：(1)在離散時刻t，如果v的鄰居節(jié)點u處于活躍狀態(tài)，則u有pu,v大小的概率激活v。如果節(jié)點v周圍有多個活躍的鄰居節(jié)點，則這些鄰居節(jié)點以任意的次序來激活節(jié)點v。(2)如果v變成活躍狀態(tài)，又會對它周圍的鄰居節(jié)點產(chǎn)生影響。(3)每個節(jié)點采用同樣的策略，按照時刻遞增進(jìn)行信息傳播，直到?jīng)]有新的激活行為為止。如圖2a所示，我們用Gephi生成的關(guān)系圖(150個節(jié)點，510條邊)，黑色節(jié)點表示的是用high-degree方法[7]選取的初始集合(10個)。圖2b中灰色節(jié)點表示的是通過IC傳播模型，模擬一次后最后激活的節(jié)點集合。

2.2.2 線性閾值模型

線性閾值模型主要是對每個節(jié)點分配一個特異性閾值，是一種價值積累模型。給定一個圖G(V,E)，記N(v)為節(jié)點v的鄰居節(jié)點集合。給定初始傳播節(jié)點集合A、所有節(jié)點的特異性閾值θv(θv∈[0,1])，節(jié)點之間的影響力權(quán)值buv(∑u∈N(v)buv≤1)。傳播過程如下：(1)對一個節(jié)點v，設(shè)其周圍已激活的鄰居節(jié)點集合為A(v)，如果∑u∈A(v)buv≥θv，則節(jié)點v變成活躍狀態(tài)。(2)節(jié)點v變?yōu)榛钴S狀態(tài)后又會對它周圍的節(jié)點產(chǎn)生影響。(3)按照時刻遞增，重復(fù)以上過程，直至不再有新的節(jié)點被激活。

Figure 2 Initial figure and the diffusion result of IC model圖2 初始關(guān)系圖和IC模型的傳播結(jié)果

3 研究現(xiàn)狀

近十年來，已經(jīng)有很多新的傳播模型和求解影響力最大化的算法被提出，它們分別采用了來自數(shù)學(xué)、計算機(jī)科學(xué)、數(shù)據(jù)挖掘等多個領(lǐng)域的理論和技術(shù)。下面將主要介紹幾種具有代表性的影響力傳播模型和求解影響力最大化問題的算法。

3.1 傳播模型研究情況

影響力傳播模型在影響力最大化問題中扮演著最基本的角色，影響力最大化問題算法的設(shè)計都是建立在傳播模型基礎(chǔ)之上的。除了第2.2節(jié)介紹的基本傳播模型(IC模型和LT模型)外，還有幾種新的傳播模型：

2003年，Kempe D等人[7]提出了一般的級聯(lián)模型和一般的閾值模型來求解網(wǎng)絡(luò)中更一般的問題。2005年，Kempe D等人[12]又提出了一個考慮節(jié)點間影響衰減的遞減級聯(lián)傳播模型(Decreasing Cascade Model)，在該模型中，如果節(jié)點v已經(jīng)被很多節(jié)點嘗試激活未成功，則新被激活的鄰居節(jié)點u對節(jié)點v的影響將會減少。

2006年，Kimura M和Saito K[13]在IC模型的基礎(chǔ)上提出了一種基于最短路徑的影響力級聯(lián)模型(SPM)，該模型下一個節(jié)點v只有在t =d(A,v)時刻才有機(jī)會被激活，其中d(A,v)表示從集合A到v的最短路長度。2007年，Kimura M等人[14]又提出了一種基于邊滲透和圖論的方法，來有效地計算邊際收益，并將該方法應(yīng)用到貪心算法中來解決影響力最大化問題。

2007年， Even-Dar E等人[15]提出使用概率選民模型(Voter Model)來解決影響力最大化問題，這與之前大多研究使用的IC和LT模型不同，它把問題轉(zhuǎn)化為概率決策求解。作者基于選民模型用各種啟發(fā)式算法來選擇初始節(jié)點，實驗表明，在這些算法中，選取度數(shù)最大的算法是最佳解決方案。

2009年，冀進(jìn)朝等人[16]提出了一種完全級聯(lián)傳播模型。在該模型中活躍節(jié)點u影響節(jié)點v的概率是節(jié)點v的鄰居中已經(jīng)試圖激活v但未激活成功節(jié)點集的一個函數(shù)，該概率表示為：pv(u,S)=pv(u)-k*(|S|/|V|)*pv(u)，其中S表示v的鄰居中已經(jīng)嘗試激活v但未激活成功的節(jié)點集，k是從{-1,0,1}中隨機(jī)選擇的一個值。該模型中活躍節(jié)點是以動態(tài)變化的概率激活其鄰居節(jié)點的。

2010年，ChenWei和WangChi等人[17]提出了一種新的模型―MIA(MaximumInfluenceArborescence)模型，該模型是用圖中每個節(jié)點的局部樹狀結(jié)構(gòu)來近似影響力傳播。首先通過Dijkstra最短路徑算法計算網(wǎng)絡(luò)中每對節(jié)點的最大影響路徑(MIP)，忽略掉概率小于θ的MIPs，然后為每個節(jié)點計算MIIA(v,θ)(Maximum Influence In Arborescence)，這代表了每個節(jié)點的局部影響力。實驗表明，該模型容易處理大規(guī)模的網(wǎng)絡(luò)，并且結(jié)果相比之下算法的運行速度顯著優(yōu)越。

2011年，He Xin-ran等人[18]提出了一種有競爭力的線性閾值CLT模型，是對LT模型的一種擴(kuò)展，該模型下每條邊具有正和負(fù)兩個權(quán)值。作者在CLT模型下，提出了影響力阻塞最大化問題(Influence Blocking Maximization Problem)，來研究一個對象如何阻塞它的競爭對象的信息傳遞。

此外，研究中提出的影響力傳播模型還有很多，如考慮傳播過程中動態(tài)變化的TCC(Time-dependent Comprehensive Cascade)模型和DVT(Dynamic Variable Threshold)模型[19]、處理社會媒體話題傳播的SIR(Susceptible, Infective, and Recovered)模型[20]以及競爭模型[21,22]等等。不同影響力傳播模型的提出，針對的是社會網(wǎng)絡(luò)中的某一個特性或某一個問題。隨著影響力傳播模型的發(fā)展，我們能夠處理社會網(wǎng)絡(luò)中越來越多的實際問題，帶來更多的實際意義。

3.2 影響力最大化算法研究情況

2001年，Domingos P和Richardson M等人[4]受病毒式營銷策略的影響，第一次把影響力最大化問題抽象為一個算法問題進(jìn)行研究，即在網(wǎng)絡(luò)中尋找到某些具有影響力的成員，讓他們接受某種產(chǎn)品，由他們向網(wǎng)絡(luò)中的其他成員進(jìn)行推薦，最后能夠引起更多接受這種產(chǎn)品的級聯(lián)效應(yīng)。作者對該問題進(jìn)行了確切定義，給出了評價指標(biāo)，后面相關(guān)研究基本上都是基于此定義的。

2003年，Kempe D和Kleinberg J等人[7]將該問題提煉成為在傳播模型基礎(chǔ)上如何選擇k個節(jié)點使得在網(wǎng)絡(luò)傳播后影響力最大化的離散優(yōu)化問題。作者證明了在獨立級聯(lián)模型和線性閾值模型上，影響力結(jié)果函數(shù)是滿足次模特性(Submodularity)的。次模特性指的是增加一個節(jié)點到某個集合得到的邊際收益要大于或等于增加相同的節(jié)點到該集合的超集所得到的邊際收益。同時，證明了該優(yōu)化問題在IC模型和LT模型上都是NP-hard問題。作者提出了在這兩種傳播模型下影響力最大化的貪心近似算法KKT。通過實驗對比表明，該貪心算法的結(jié)果優(yōu)于若干直觀的啟發(fā)式算法結(jié)果，并證明了該貪心算法的近似性能比至少是1-1/e。

2007年，Leskovec J等人[23]提出了KKT算法的改進(jìn)方法CELF(Cost-Effective Lazy Forward)算法，一種新的選擇初始節(jié)點優(yōu)化方法。CELF算法利用了影響力最大化目標(biāo)的次模特性，使得每一輪大量節(jié)點的影響力傳播增量不需要重新評估，從而大大減少了計算節(jié)點影響力傳播工作的次數(shù)。實驗結(jié)果表明，使用CELF算法選擇初始節(jié)點比貪心算法運算時間要快700倍，但是結(jié)果非常接近于貪心算法。2011年，Goyal A等人[24]進(jìn)一步優(yōu)化了CELF算法，提出了CELF++算法。相比CELF算法來說，CELF++算法將效率提高了35%～55%。

2007年，Estevez P A等人[25]提出了一種改進(jìn)的貪心算法——集合覆蓋貪心算法SCG(Set Cover Greedy)。SCG算法考慮了鄰居節(jié)點重疊的現(xiàn)象，避免了在貪心選擇影響力最大節(jié)點時會有鄰居節(jié)點重疊的情況。該算法首先初始時將所有節(jié)點設(shè)為“uncover”；然后，每次選中“uncover”度數(shù)最高的節(jié)點，當(dāng)節(jié)點被選中時則它周圍的鄰居節(jié)點會被標(biāo)記為“covered”，依次迭代下去，直至選出k個節(jié)點為止。實驗表明，SCG算法相比于貪心算法來說計算時間要降低很多。

2007年，Bharathi S等人[21]研究了節(jié)點間存在競爭的情況，建立了比較容易處理的傳播模型，并討論了先發(fā)策略(First Mover)(即先于競爭者來進(jìn)行信息的傳遞)來嘗試使存在競爭時影響傳遞到最大，并給出了當(dāng)圖是樹時求解影響力最大化問題的一種FPTAS(Full Polynomial-Time Approximation Scheme)方法。

2009年，Chen Wei等人[26]從兩個方面提高了影響力最大化的效率問題。首先提出了一種改進(jìn)的貪心算法(NewGreedyIC)，該算法首先將圖G中沒有傳播成功的邊去除掉，得到新的圖G′，在新的圖上依照貪心策略依次選擇初始節(jié)點。實驗表明，該改進(jìn)的貪心算法能夠大大減少運算時間。此外，作者還提出了一種改進(jìn)的啟發(fā)式算法——Degree-Discount算法來進(jìn)行初始節(jié)點的選擇。實驗表明，Degree-Discount算法相比基于degree和distance的啟發(fā)式算法影響力傳播的范圍更大。

2010年，Chen Wei等人[27]提出一種在有向無環(huán)圖(DAGs)上快速計算影響力的方法。該方法的計算時間與圖的規(guī)模大小呈線性關(guān)系，并根據(jù)該方法提出了針對LT模型的可擴(kuò)展的影響力最大化算法。該算法可以應(yīng)用到含有百萬級別節(jié)點的大規(guī)模網(wǎng)絡(luò)上，比貪心算法要快幾個數(shù)量級。

2012年，Li Jin-shuang等人[28]提出了一種用社區(qū)挖掘的方法來求解影響力最大化問題的算法。該算法首先用改進(jìn)的k-means算法將給定的網(wǎng)絡(luò)劃分成k個社區(qū)，同一個社區(qū)里的節(jié)點具有較高的相似性，不同社區(qū)里的節(jié)點相似性較低，然后在每個社區(qū)里選擇處于中心的節(jié)點。實驗表明，通過社區(qū)挖掘算法選擇的中心節(jié)點具有很高的影響力。

2013年，Zhu Yu-qing等人[27]首次將半定規(guī)劃應(yīng)用到求解影響力最大化問題上。他們考慮了現(xiàn)實網(wǎng)絡(luò)中信息傳遞對時間的敏感特性，提出了一種新的傳播模型，將影響力最大化問題轉(zhuǎn)變成求解：maxS?V∑a∈S,b∈V-Sp(a,b)，并且針對兩種情況設(shè)計了兩種使用半定規(guī)劃求解算法。當(dāng)節(jié)點集合S大小沒有限制時，設(shè)計的近似算法近似性能比可以達(dá)到0.857；當(dāng)初始節(jié)點集合S大小限制在某個范圍內(nèi)時，設(shè)計的算法近似性能比也能夠達(dá)到1-1/e。

另外，影響力最大化的求解算法還有很多很多，例如混合式啟發(fā)算法TBH(Threshold Based Heuristic)[30]和HPG(Hybrid Potential-influce Greedy)[31]，通過對網(wǎng)絡(luò)結(jié)構(gòu)稀疏化[32,33]來減少算法復(fù)雜度，考慮網(wǎng)絡(luò)的社區(qū)性[34,35]來求解影響力最大化問題，基于shapley值[36]的求解算法等等。此外，還有很多的研究對影響力最大化問題進(jìn)行了延伸，如Lappas J等人[37]提到的k-Effectors問題，Li Cheng-te等人[38]提出的k-Mediators問題等等?？傊?，影響力最大化問題正在向多方面多領(lǐng)域發(fā)展。

4 影響力最大化問題存在的問題及展望

影響力最大化問題存在的問題及展望:

(1)研究影響力最大化問題時建立的傳播模型很重要，現(xiàn)實中不同的社會網(wǎng)絡(luò)都有著各自不同的特點，如何針對具體的社會網(wǎng)絡(luò)，來建立適合它的影響力傳播模型，值得研究者們注意。

(2)現(xiàn)實的許多社會網(wǎng)絡(luò)中的激活概率是很難確定的，大多數(shù)情況下都是系統(tǒng)隨機(jī)設(shè)定的，是否可以根據(jù)網(wǎng)絡(luò)的實際情況和特點來準(zhǔn)確地確定，還有待研究。其次，實際情況中，由于節(jié)點之間交互的動態(tài)性，激活概率也是在隨時發(fā)生變化的，這樣的情況下如何處理，還有待進(jìn)一步研究。

(3)現(xiàn)有的很多研究都是基于貪心算法來進(jìn)行改進(jìn)的，雖然貪心算法的近似性比較好，但是實際計算起來還是相當(dāng)費時的。我們是否可以找到更好的算法，在保證近似性能的基礎(chǔ)上，能夠大幅地減少計算時間。

(4)大多數(shù)解決影響力最大化問題的算法設(shè)計和分析都是依靠次模特性來使近似性達(dá)到1-1/e，是否可以找到新的技術(shù)和方法來提高近似性，還有待研究。

(5)目前對于影響力最大化問題的研究基本上都是基于靜態(tài)網(wǎng)絡(luò)的，而現(xiàn)實中的社會網(wǎng)絡(luò)是時時在發(fā)生變化的，以后可以針對動態(tài)社會網(wǎng)絡(luò)中影響力最大化問題來進(jìn)行研究，比如采用在線的方法進(jìn)行研究。

(6)現(xiàn)實世界中的復(fù)雜網(wǎng)絡(luò)有很多，如社會系統(tǒng)中的科學(xué)家協(xié)作網(wǎng)、生態(tài)系統(tǒng)中的神經(jīng)元網(wǎng)等等，能否將影響力最大化問題應(yīng)用到這些復(fù)雜網(wǎng)絡(luò)中，來解決復(fù)雜網(wǎng)絡(luò)中的相關(guān)問題。

(7)社會網(wǎng)絡(luò)具有許多獨特的特點，如節(jié)點的同質(zhì)性。處于同一社區(qū)內(nèi)的節(jié)點聯(lián)系更加緊密，不同社區(qū)之間的聯(lián)系相對比較疏遠(yuǎn)。社區(qū)內(nèi)部消息傳播得更快更多，社區(qū)之間信息傳遞得相對較慢，可以針對社會網(wǎng)絡(luò)的某種特性來進(jìn)行影響力最大化問題的研究。

5 結(jié)束語

影響力最大化問題是近年來社會網(wǎng)絡(luò)中的一個研究熱點，其應(yīng)用前景也十分廣闊。社會網(wǎng)絡(luò)中的影響力傳播模型及其算法研究不斷深入，這對社會網(wǎng)絡(luò)的理論創(chuàng)新和實際應(yīng)用，都具有非常重要的意義。同時，對影響力最大化問題的理論及其應(yīng)用進(jìn)行深入研究，也會在很大程度上拓展相關(guān)技術(shù)和領(lǐng)域的發(fā)展，從而能更加有效地解決更多的實際問題。

[1] Brown J, Reinegen P. Social ties and word-of-mouth referral behavior[J]. Journal of Consumer Research,1987,14(3):350-362.

[2] Goldenberg J, Libai B, Muller E. Talk of the network:A complex systems look at the underlying process of word-of-mouth[J]. Marketing Letters,2001,12(3):211-223.

[3] Goldenberg J, Libai B, Muller E. Using complex systems analysis to advance marketing theory development:Modeling heterogeneity effects on new product growth through stochastic cellular automata[J]. Academy of Marketing Science Review,2001,9(3):1-18.

[4] Domingos P，Richardson M.Mining the network value of customers[C]∥Proc of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001:57-66.

[5] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C]∥Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2002:61-70．

[6] Gruhl D, Guha R, Liben-Nowell D, et al. Information diffusion through blogspace[C]∥Proc of the 13th International Conference on World Wide Web,2004:491-501.

[7] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C]∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:137-146.

[8] Watts D. A simple model of global cascades on random networks[C]∥Proc of the National Academy of Sciences,2002:5766-5771.

[9] Granovetter M. Threshold models of collective behavior[J]. The American Journal of Sociology,1978,83(6):1420-1443.

[10] Durrett R. Lecture notes on particle systems and percolation[M]. California:Wadsworth Publishing,1988.

[11] Liggett T M.Interacting particle systems[M].Berlin:Springer,1985.

[12] Kempe D, Kleinberg J, Tardos E. Influential nodes in a diffusion model for social networks[C]∥Proc of the 32nd International Conference on Automata, Languages and Programming,2005:1127-1138.

[13] Kimura M,Saito K.Tractable models for information diffusion in social networks[C]∥Proc of the 10th European Conference on Principles and Programming,2005:1127-1138.

[14] Kimura M,Saito K,Nakano R.Extracting influential nodes for information diffusion on a social network[C]∥Proc of the AAAI’07,2007:1371-1376.

[15] Even-Dar E, Asaf S. A note on maximizing the spread of influence in social networks[C]∥Proc of the 3rd International Conference on Internet and Network Economics,2007:281-286.

[16] Ji Jin-chao, Han Xiao, Wang Zhe. Community influence maximizing based on comprehensive cascade diffuse model[J]. Journal of Jilin University(Science Edition),2009,47(5):1032-1034.(in Chinese)

[17] Chen Wei,Wang Chi,Wang Ya-jun.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]∥Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:1029-1038.

[18] He Xin-ran, Song Guo-jie, Chen Wei, et al. Influence blocking maximization in social networks under the competitive linear threshold model[C]∥Proc of the 2012 SIAM International Conference on Data Mining,2012:1.

[19] Hao Fei,Zhu Chun-sheng,Chen Min,et al.Influence strength aware diffusion models for dynamic influence maximization in social networks[C]∥Proc of the 4th International Conference on Cyber,Physical and Social Computing,2011:317-322.

[20] Woo J, Son J, Chen H. An SIR model for violent topic diffusion in social media[C]∥Proc of the 2011 IEEE International Conference on Intelligence and Security Informatics,2011:15-19.

[21] Bharathi S,Kempe D,Salek M.Competitive influence maximization in social networks[C]∥Proc of the 3rd International Conference on Internet and Network Economics,2007:306-311.

[22] Dubey P, Garg R, De Meyer B. Competing for customers in a social network:The quasi-linear case[C]∥Proc of Internet and Network Economics,2006:162-173.

[23] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]∥Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007:420-429.

[24] Goyal A, Wei Lu, Lakshmanan L V S. CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]∥Proc of the 20th International Conference Companion on World Wide Web, 2011:47-48.

[25] Estevez P A, Vera P A, Saito K. Selecting the most influential nodes in social networks[C]∥Proc of the International Joint Conference on Neural Networks, 2007:2397-2402.

[26] Chen Wei, Wang Ya-jun, Yang Si-yu. Effieient influence maximization in social networks[C]∥Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009:199-208.

[27] Chen Wei, Yuan Yi-fei, Zhang Li. Scalable influence maximization in social networks under the linear threshold model[C]∥Proc of the 10th IEEE International Conference on Data Mining, 2010:88-97.

[28] Li Jin-shuang, Yu Yang-yang. Scalable influence maximization in social networks using the community discovery algorithm[C]∥Proc of the 6th International Conference on Genetic and Evolutionary Computing,2012:284-287.

[29] Zhu Yu-qing, Wu Wei-li, Bi Yuan-jun, et al. Better approximation algorithms for influence maximization in online social networks[J]. Journal of Combinatorial Optimization,2013,doi:10.1007/s 10878-013-9635-7.

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

[31] Tian Jia-tang, Wang Yi-tong, Feng Xiao-jun. A new hybrid algorithm for influence maximization in social networks[J]. Chinese Journal of Computers,2011,34(10):1956-1965.(in Chinese)

[32] Michael M, Francesco B, Carlos C. Sparsification of influence networks[C]∥Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2011:529-537.

[33] Manuel G, Jure L, Andreas K. Inferring networks of diffusion and influence[C]∥Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2010:1019-1028.

[34] Galstyan A, Musoyan V, Cohen P. Maximizing influence propagation in networks with community structure[J]. Physical Review E, 2009, 79(5):56-102.

[35] Wang Yu, Cong Gao, Song Guo-jie, et al. Community-based greedy algorithm for mining top-kinfluential nodes in mobile social networks[C]∥Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:1039-1048.

[36] Rama S N, Narahari Y. Determining the top-knodes in social networks using the shapley value[C]∥Proc of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, 2008:1509-1512.

[37] Lappas T, Terzi E, Dimitrios G, et al. Finding effectors in social networks[C]∥Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:1059-1068.

[38] Li Cheng-te, Lin Shou-de, Shan Man-kwan. Finding influential mediators in social networks[C]∥Proc of the Conference Companion on World Wide Web, 2011:75-76.

附中文參考文獻(xiàn)：

[16] 冀進(jìn)朝,韓笑,王喆. 基于完全級聯(lián)傳播模型的社區(qū)影響最大化[J]. 吉林大學(xué)學(xué)報(理學(xué)版), 2009, 47(5):1032-1034.

[30] 陳浩,王軼彤. 基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J]. 計算機(jī)研究與發(fā)展,2012,49(10):2181-2188.

[31] 田家堂,王軼彤,馮小軍. 一種新型的社會網(wǎng)絡(luò)影響最大化算法[J]. 計算機(jī)學(xué)報,2011,34(10):1956-1965.