社會網絡中的影響力最大化問題*

顏 慶，張 鵬

(山東大學計算機科學與技術學院，山東 濟南 250101)

1 引言

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

2 理論基礎

2.1 社會網絡

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

Figure 1 Example of social network圖1 社會網絡示例圖

2.2 影響力傳播模型

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

2.2.1 獨立級聯模型

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

2.2.2 線性閾值模型

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

Figure 2 Initial figure and the diffusion result of IC model圖2 初始關系圖和IC模型的傳播結果

3 研究現狀

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

3.1 傳播模型研究情況

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)現實的許多社會網絡中的激活概率是很難確定的，大多數情況下都是系統隨機設定的，是否可以根據網絡的實際情況和特點來準確地確定，還有待研究。其次，實際情況中，由于節點之間交互的動態性，激活概率也是在隨時發生變化的，這樣的情況下如何處理，還有待進一步研究。

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

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

(5)目前對于影響力最大化問題的研究基本上都是基于靜態網絡的，而現實中的社會網絡是時時在發生變化的，以后可以針對動態社會網絡中影響力最大化問題來進行研究，比如采用在線的方法進行研究。

(6)現實世界中的復雜網絡有很多，如社會系統中的科學家協作網、生態系統中的神經元網等等，能否將影響力最大化問題應用到這些復雜網絡中，來解決復雜網絡中的相關問題。

(7)社會網絡具有許多獨特的特點，如節點的同質性。處于同一社區內的節點聯系更加緊密，不同社區之間的聯系相對比較疏遠。社區內部消息傳播得更快更多，社區之間信息傳遞得相對較慢，可以針對社會網絡的某種特性來進行影響力最大化問題的研究。

5 結束語

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

[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.

附中文參考文獻：

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

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

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