社交網絡影響力傳播研究

陳衛

（微軟亞洲研究院 北京 100080）

摘要：隨著互聯網和大數據的研究應用日益廣泛，對社交網絡影響力傳播的研究成為數據挖掘和社交網絡分析中的熱點。從影響力傳播模型、影響力傳播學習和影響力傳播優化3個方面總結了近些年計算機科學領域對影響力傳播研究的主要成果，展示了影響力傳播研究中對隨機模型、數據挖掘、算法優化和博弈論等技術的綜合運用。最后，簡要討論了影響力傳播研究和應用中存在的問題、挑戰及今后的研究方向。

關鍵詞：社交網絡；社會影響力；影響力傳播模型；影響力最大化；社會影響力學習；病毒營銷

doi: 10.11959/j.issn.2096-0271.2015031

Research on Influence Diffusion in Social Networks

Chen Wei

(Microsoft Research Asia, Beijing 100080, China)

Abstract: With the wide spread of internet and big data research and applications, influence diffusion research in social networks becomes one of the hot topics in data mining and social networks analysis in recent years. The main results on social influence diffusion research from the field of computer science in the last decade, which covers the three main areas -- influence diffusion modeling,influence diffusion learning, and influence diffusion optimization, were summarized. Different techniques, such as stochastic modeling, data mining,algorithmic optimization, and game theory, were demonstrated in their application to influence diffusion research. Finally, some discussions on thecurrent issues, challenges and future directions in influence diffusion research and applications were provided.

Key words: social networks, social influence, influence diffusion model, influence maximization, social influence learning, viral marketing

---

論文引用格式：陳衛.社交網絡影響力傳播研究.大數據,2015031

Chen W. Researchon influence diffusion in social networks. Big Data Research, 2015031

---

4 社會影響力傳播學習

前面介紹了影響力傳播模型和其上的影響力優化問題。要使影響力傳播研究在實際中發揮更大的作用，基于實際數據的影響力學習（influence learning）也是必不可少的一個方面。基于實際數據的網絡影響力分析在國內外社交媒體網站也都有出現，比如國外的Klout.com、國內的新浪微博影響力排名等。這些影響力分析側重對名人的排名，分析方法大多利用網絡拓撲結構（如粉絲數、PageRank）、用戶活躍度等。而基于影響力傳播的學習是希望從數據中挖掘用戶行為的傳播方式和對應的參數，從而為影響力傳播建模和優化服務。

4.1 影響力傳播學習的基本思想

在影響力傳播學習方面也有不少工作。這些工作基于的數據基本上是兩類：一類是社交網絡結構的數據，比如微博中用戶B關注了用戶A，那么就有一條有向邊從用戶A到用戶B，邊的方向在這里表示信息從用戶A傳向用戶B，與影響力的方向一致。當收集了大量用戶的關注數據后，就可以建立一個關于這些用戶的有向圖。當然有些網絡（如Facebook）對應的是無向圖，每條無向邊表示的是朋友關系。第二類數據是用戶的某一類行為的時間序列，比如一條記錄是微博用戶A在時刻t₁發布了一條帶有某個鏈接L1的微博，用(A,L₁,t₁)表示。一般來講，用戶的行為序列是由(u, a, t)組成的序列，其中，u表示一個用戶（對應圖上一個節點），a表示一個動作，t表示用戶u執行動作a的時間。

目前來講，影響力傳播學習的基本思想是如果相連的兩個用戶在相近時間先后執行同樣的動作，那么認為這是先執行動作的用戶對后執行動作的用戶的一次成功影響。比如在上文的微博例子中，如果在記錄(A, L₁, t₁)后面有一條記錄(B, L₁, t₂)，而時間t₂大于t₁但又不大很多，說明在用戶A發布了包含鏈接L₁的微博不久，關注用戶A的用戶B也發布了同樣鏈接的微博，這可被理解為用戶B看到用戶A的微博而轉發的行為，所以在發布鏈接這個行為上可以認為用戶B受到一次用戶A的影響。如果數據中發現用戶B經常在用戶A之后發布與用戶A相同的鏈接，那么可以推測在發布鏈接這類行為上用戶A對用戶B的影響力較大。

上述的思想比較直觀，但嚴格地說所發現的是用戶行為的相關性，并不能直接反映影響力的因果關系。比如上述微博例子中也有可能是用戶B并未看到用戶A的微博，或者即使看到，用戶B發同樣微博是因為用戶B和用戶A都對同一類鏈接內容感興趣，而并不是因為用戶B受到用戶A的影響，這稱為社會關系中的同質性（homophily）。在一組收集數據中要區分相關性行為的來源是同質性還是影響力并不是一件容易的事情。為此，Anagnostopoulos等人提出了洗牌測試（shuffle test）的方法^[44]，將實際發生事件的時間順序像洗牌一樣隨機打亂后，再觀察關于這個序列的某些特征值是否改變。如果發生改變，說明實際的時間順序是重要的，這是支持影響力的因果關系造成實際事件順序的證據；而如果不發生改變，說明時間順序并不重要，這是支持由同質性造成的相關性事件序列的證據。洗牌測試對判定影響力的存在性有一定作用，但在區分影響力和同質性方面仍有不少需要進一步完善的工作要做。

在影響力傳播中下一個要解決的問題是在一個節點執行一個動作之前，有多個該節點的鄰居節點都執行了同樣動作，在這種情況下如何判定是哪一個或哪幾個鄰居節點真正影響了該節點？現有的方法基本分兩種：一種是用最大似然估計（maximum likelihood estimate），一種是基于信用分配（credit distribution）的頻度分析（frequency analysis）。

4.2 最大似然估計

最大似然估計是基于一個隨機傳播模型（如獨立級聯模型）得到一次傳播結果的似然度，然后求得參數使得實際出現的傳播結果似然度最大^[45,46]。直觀上說，雖然一個節點有可能被多個鄰居節點影響，但如果實際數據中一個節點的動作經常跟隨它的某一個鄰居節點的動作，這說明這個特定節點對它的影響力可能較大。最大似然估計就是將這一想法嚴格數學化的方法。

直接應用最大似然估計很可能在圖中很難計算，通常會用中間變量和期望最大化迭代的EM算法^[46]。但這種算法在大圖中效率不高，且不一定保證能收斂到全局最優解。Netrapalli和Sanghavi對最大似然估計做了改進，將其計算變為一個凸規化（convex program）問題，從而能有效求解且保證全局最優^[45]。

4.3信用分配和頻度分析

最大似然估計的形式化和計算仍然比較復雜，對此Goyal、Bonchi和Lakshmanan提出了基于信用分布的頻度分析方法^[47]。它的基本思想是當需要決定在一次傳播中究竟是哪個已被激活的鄰居節點激活了一個節點時，將部分信用積分（partial credit）平攤到所有參與的鄰居節點中（每次的總信用為1）。這種信用積分的分配可以是完全平均，也可以不平均，比如激活時間上離被激活節點時間最近的信用積分最高。這種簡單的分配方式雖然是啟發式的，但避免了復雜的最大似然分析。當部分信用積分分配對所有的傳播實例都完成后，一個節點對它的鄰居節點的影響力就由直接的頻度分析得到，也即從得到的信用積分總和除以在數據中總共被激活的次數，這個比值表示了當被激活后被激活的頻度，而這個頻度考慮了對的部分信用積分。這種計算方法效率很高，適合于大規模圖的學習。

影響力傳播學習并不一定需要知道社交網絡的圖結構。在缺乏圖結構時，認為任何在激活時間上相接近的兩個節點都有可能存在邊而發生傳播。這相當于把圖看成是全連通圖。在學習結束后可以把權重很低的邊刪掉，從而一定程度上恢復原圖。如果已知原圖，則學習的效率和準確度都會大大提高。但從另一方面講，社交網絡中的圖結構并不能準確表達所有的傳播路徑，不基于圖結構的影響力傳播學習可能會挖掘出隱含的影響力關系，也有它的好處。另外，影響力的傳播在不同領域和不同話題下經常是不一樣的，為此Barbieri等提出了與話題相關的影響力傳播模型和在其上的學習方法^[48]。

5 影響力傳播研究和應用的問題、挑戰和方向

影響力傳播研究經過本世紀十幾年的發展，已經取得長足的進步，使大家對影響力傳播的模式和其上的優化問題都有了較深的認識。但是進一步發展其研究和應用，還要解決很多問題。

其中一個主要問題是影響力傳播學習方面的準確、有效問題，這仍然是當前一個很大的挑戰。與很多大數據分析不同，影響力傳播的大數據分析要求分析的是任意兩個關聯用戶之間的影響力強度，這比只分析一個用戶的特征或一個群體的特征難度要大很多。不僅如此，影響力傳播涉及對人的行為分析，而且是較為復雜的如產品購買、接受新思想等行為，這種行為數據在社交媒體數據中并不容易挖掘，因為大多數社交媒體數據都是無意義的噪聲，而諸如轉發等的行為傳播又過于簡單，與真正針對產品、思想等的行為傳播可能很不同。而且如前文所述，從數據中區分影響力和同質性也是一個較難的問題。所以，在影響力傳播的研究中影響力傳播的有效分析是目前的一大瓶頸。簡單地說，就是在這方面大數據還遠不夠大，在真正理解和分析用戶行為的大規模傳播方面還有很多路要走。

在影響力建模方面，已發展出很多模型，其中以獨立級聯模型為代表的一些模型在實際數據中也得到一定程度的印證。但是目前為止，對于更適于描述復雜傳播行為的閾值模型還缺乏實際數據的有效驗證。線性閾值模型對閾值的隨機性要求有局限性，而如果用更一般的閾值模型很可能會使模型不具備子模性等性質，從而無法設計有效的算法。所以對于閾值模型，從數據分析到建模和優化還都有不少問題要解決。

另外，絕大多數影響力傳播研究都是在靜態網絡中進行，而實際網絡都是動態變化的。如何將傳播的動態性和網絡的動態性合理結合，以達到有效的分析、建模和優化，也是一個需要更多關注的課題。

在影響力優化方面，其應用有效性還需實際檢驗。這是因為影響力優化需要因果關系的驗證，而這通常需要在實際系統中進行隨機可控試驗（randomized controlled experiment）才能真正驗證。絕大多數研究者還不具備大規模的社交網絡平臺和影響力傳播數據用以實施這樣的試驗。所以如何加強合作，構建這樣的共享平臺和共享大數據，是讓影響力傳播和最大化研究走出實驗室得以廣泛應用的關鍵課題。

盡管存在很多問題和挑戰，影響力傳播的研究仍然蓬勃發展，甚至展示了它在一些意料之外方面的應用。比如Shakarian等人將影響力最大化應用到芝加哥警察局挑選暴力團伙成員參加學習勸導班，使其影響其他團伙成員遠離暴力犯罪^[49]，而Wang等人將影響力傳播模型和最大化借用到文本概括（text summarization）領域，通過建立單詞之間的一個影響網絡來幫助文本概括^[50]。隨著大數據技術的發展和影響力傳播研究的深入，影響力傳播研究會有更廣泛的應用前景。

6 結束語

本文將影響力傳播研究分為三大方面：影響力傳播模型、影響力傳播學習和影響力傳播優化，并對3個方面的主要成果和近期進展進行了介紹。簡而言之，影響力傳播研究通過建立人們行為的傳播模型，從實際數據中學習傳播模型及其參數和基于傳播模型的各種影響力優化和控制技術，使大家對影響力的傳播機理和模式有了深入的了解，并將這種認識和理解轉化為對傳播行為的預測、優化和控制。本文也討論了當前影響力傳播研究和應用方面的問題和挑戰，比如如何利用更大規模的數據來支持影響力傳播的研究、如何結合網絡的動態性、如何在實際中檢驗優化結果等。隨著大數據研究和應用的不斷深入和發展，影響力傳播的研究也會取得更加豐碩的成果，并在產業界和實際生活中得到廣泛的應用。

參考文獻

[1] Bass F M. A new product growth for modelconsumer durables. Management Science, 1969, 15(5): 215~227

[2] Granovetter M. Threshold models for collective behavior. American Journal of Sociology, 1978, 83(6): 1420~1443

[3] Christakis N A, Fowler J H. The spread ofobesity in a large social network over 32 years. New England Journal of Medicine, 2007, 357(4): 370~379

[4] Christakis N A, Fowler J H. The collective dynamics of smoking in a large social network. New England Journal of Medicine,2008, 358(21): 2249~2258

[5] Aral S, Walker D. Identifying influential and susceptible members of social networks. Science, 2012(337): 337~341

[6] Bond R M, Fariss C J, Jones J J, et al. A61-million-person experiment in social influence and political mobilization.Nature, 2012(489): 295~298

[7] Charu C, Aggarwal. Social Network Data Analysis.New York: Springer, 2011: 177~214

[8] 吳信東, 李毅, 李磊. 在線社交網絡影響力分析. 中國計算機學報, 2014, 37(4): 735~752

Wu X D, Li Y, Li L. Influence analysis of online social networks. Chinese Journal of Computers, 2014, 37(4): 735~752

[9] Chen W, Lakshmanan L V S, Castillo C.Information and Influence Propagation in Social Networks. California: Morgan& Claypool Publishers, 2013

[10] Domingos P, Richardson M. Mining the networkvalue of customers. Proceedings of the 7th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD), San Francisco, USA, 2001: 57~66

[11] Kempe D, Kleinberg J M, Tardos é. Maximizing the spread of influence through a social network. Proceedings of the 9th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining (KDD),Washington DC, USA, 2003: 137~146

[12] Chen W, Lu W, Z ha ng N. Time-critical influence maximization in social networks with time-delayed diffusion process.Proceedings of the 26th National Conference on Artificial Intelligence (AAAI),Toronto, Canada, 2012

[13] Centola D, Macy M. Complex contagion and theweakness of long ties. American Journal of Sociology, 2007, 113(3): 702~734

[14] Gomez-Rodriguez M, Balduzzi D, Sch?lkopf B.Uncovering the temporal dynamics of diffusion networks. Proceedings of the 28th International Conference on Machine Learning (ICML), Bellevue, Washington, USA,2011:561~568

[15] Newman M E J. Networks: an Introduction.Oxford: Oxford University Press, 2010

[16] Even-Dar E,Shapira A. A note on maximizing thespread of influence in social networks. Proceedings of the 3rd Workshop on Internet and Network Economic (WINE), San Diego, USA, 2007: 281~286

[17] Li Y, Chen W, Wang Y, et al. Influence diffusion dynamics and influence maximization in social networks with friendand foe relationships. Proceedings of the 6th ACM International Conference onWeb Search and Data Mining (WSDM), Rome, Italy, 2013: 657~666

[18] Immorlica N, Kleinberg J M, Mahdian M, et al.The role of compatibility in the diffusion of technologies through social networks. Proceedings of the 8th ACM Conference on Electronic Commerce (EC),San Diego, USA, 2007: 75~83

[19] Montanari A,Saberi A. Convergence to equilibrium in local interaction games. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, USA, 2009:303~312

[20] Budak C, Agrawal D, Abbadi A E. Limiting the spread of misinformation in social networks. Proceedings of the 20th International Conference on World Wide Web (WWW), Hyderabad, India, 2011:665~674

[21] Chen W, Collins A, Cummings R, et al. Influencemaximization in social networks when negative opinions may emerge andpropagate. Proceedings of SIAM International Conference on Data Mining, Mesa,USA, 2011: 379~390

[22] He X, Song G, Chen W, et al. Influence blocking maximization in social networks under the competitive linear threshold Model.Proceedings of SIAM International Conference on Data Mining, Anaheim, USA,2012: 463~474

[23] Lu W, Bonchi F, Goyal A, et al. The bang forthe buck: fair competitive viral marketing from the host perspective. Proceedingsof the 19th ACM SIGKDD International Conference on Knowledge Discovery and DataMining (KDD), Chicago, USA, 2013: 928~936

[24] Lu W, Chen W, Lakshmanan L V S. Fromcompetition to complementarity: comparative influence diffusion and maximization. Proceedings of the 42nd International Conference on Very Large Data Bases (VLDB), New Delhi, India, 2016 Accepted

[25] Nemhauser G, Wolsey L, Fisher M. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 1978(14): 265~294

[26] Wang C, Chen W, Wang Y. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 2012, 25(3): 545~576

[27] Chen W, Yuan Y, Zhang L. Scalable influence maximizationin social networks under the linear threshold Model. Proceedings of the 10th IEEE International Conference on Data Mining (ICDM), Sydney, Australia, 2010:88~97

[28] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Paris,France, 2009: 199~208

[29] Goyal A, Lu W, Lakshmanan L V S. SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. Proceedings of the 11st IEEE International Conference on Data Mining(ICDM), Vancouver, Canada, 2011: 211~220

[30] Jung K, Heo W, Chen W. IRIE: scalable androbust influence maximization in social networks. Proceedings of the 12nd IEEE International Conference on Data Mining (ICDM), Brussels, Belgium, 2012: 918~923

[31] Borgs C, Brautbar M, Chayes J, et al.Maximizing social influence in nearly optimal time. Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, USA, 2014: 946~957

[32] Leskovec J, Krause A, Guestin C, et al.Cost-effective outbreak detection in networks. Proceedings of the 13rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD),San Jose, USA, 2007: 420~429

[33] Tang Y, Shi Y, Xiao X. Influence maximizationin near-linear time: a martingale approach. Proceedings of ACM SIGMOD Conference (SIGMOD), Melbourne, Australia, 2015: 1539~1554

[34] Tang Y, Xiao X, Shi Y. Influence maximization:near-optimal time complexity meets practical efficiency. Proceedings of ACM SIGMOD Conference (SIGMOD), Snowbird, USA, 2014: 75~86

[35] Cohen E, Delling D, Pajor T, et al.Sketch-based influence maximization and computation: scaling up with guarantees. Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM), Shanghai, China, 2014: 629~638

[36] Goyal A, Bonchi F, Lakshmanan L V S, et al. On minimizing budget and time in influence propagation over social networks.Social Network Analysis and Mining, 2012, 2(1)

[37] Long C, Wong R CW. Minimizing seed set forviral marketing. Proceedings of the 11st IEEE International Conference on Data Mining (ICDM), Vancouver, Canada, 2011: 427~436

[38] Lu W, Lakshmanan L V S . Profit maximization over social networks. Proceedings of the 12nd IEEE International Conference on Data Mining (ICDM),Brussels, Belgium, 2012: 479~488

[39] Khalil E, Dilkina B, Song L. Scalable diffusion-aware optimization of network topology. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD),New York, USA, 2014: 1226~1235

[40] Goldberg S, Liu Z. The diffusion of networking technologies. Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms(SODA), New Orleans, USA, 2013: 1577~1594

[41] Zhang P, Chen W, Sun X, et al. Minimizing seedset selection with probabilistic coverage guarantee in a social network.Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York, USA, 2014: 1306~1315

[42] Chen W, Li F, Lin T,et al. Combining traditional marketing and viral marketing with amphibious influence maximization. Proceedings of the 16th ACM Conference on Economics and Computation (EC), Portland, USA, 2015: 779~796

[43] Yang D N, Hung H J, Lee W C, et al. Maximizing acceptance probability for active friending in online social networks.Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Chicago, USA, 2013: 713~721

[44] Anagnostopoulos A, Kumar R, Mahdian M.Influence and correlation in social networks. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD),Las Vegas, USA, 2008: 7~15

[45] Netrapalli P, Sanghavi S. Learning the graph of epidemic cascades. Proceedings of ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems(SIGMETRICS), London, UK, 2012: 211~222

[46] Saito K, Nakano R, Kimura M. Prediction of information diffusion probabilities for independent cascade model. Proceedings of the 12nd International Conference on Knowledge-based Intelligent Informationand Engineering Systems (KES), Zagreb, Croatia, 2008: 67~75

[47] Goyal A, Bonchi F, Lakshmanan L V S. Learning influence probabilities in social networks. Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM), New York, USA,2010: 241~250

[48] Barbieri N, Bonchi F, Manco G. Topic-awaresocial influence propagation models. Knowledge Information Systems, 2013,37(3): 555~584

[49] Shakarian P, Salmento J, Pulleyblank W, et al.Reducing gang violence through network influence based targeting of social programs. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York, USA, 2014: 1829~1836

[50] Wang C, Yu X, Li Y, et al. Content coverage maximization on word networks for hierarchical topic summarization. Proceedingsof the 22nd ACM International Conference on Information and KnowledgeManagement(CIKM), San Francisco, USA, 2013: 249~258

---

總結

以上是生活随笔為你收集整理的《大数据》2015年第3期“研究”——社交网络影响力传播研究（下）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。