《大数据》2015年第3期“研究”——社交网络影响力传播研究（上）
社交網絡影響力傳播研究
陳衛
（微軟亞洲研究院 北京 100080）
摘 要：隨著互聯網和大數據的研究應用日益廣泛，對社交網絡影響力傳播的研究成為數據挖掘和社交網絡分析中的熱點。從影響力傳播模型、影響力傳播學習和影響力傳播優化3個方面總結了近些年計算機科學領域對影響力傳播研究的主要成果，展示了影響力傳播研究中對隨機模型、數據挖掘、算法優化和博弈論等技術的綜合運用。最后，簡要討論了影響力傳播研究和應用中存在的問題、挑戰及今后的研究方向。
關鍵詞：社交網絡；社會影響力；影響力傳播模型；影響力最大化；社會影響力學習；病毒營銷
doi: 10.11959/j.issn.2096-0271.2015031
Research on Influence Diffusion in Social Network
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 network becomes one of the hot topics in data mining and social network 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 the current issues, challenges and future directions in influence diffusion research and applications were provided.
Key words: social network, social influence, influence diffusion model, influence maximization, social influence learning, viral marketing
論文引用格式：陳衛.社交網絡影響力傳播研究.大數據,2015031
Chen W. Researchon influence diffusion in social network. Big Data Research, 2015031
1 引言
任何社會性動物在個體與個體、群體與個體之間都存在著相互影響的關系，例如個體依從群體的行為會有利于獵食或減少被獵食的可能。而人類作為具有復雜交流手段的高級社會性動物，社會影響力在社會生活中更是無處不在。小到聽一首歌曲、選一個餐館，大到確定政治觀點或買一處房產等，人們的各種選擇和決定常常受家人、同事、朋友以及更廣泛的大眾傾向的影響。深入認識影響力的產生和傳播模式有助于理解人類群體和個體的行為，從而能夠預期人們的行為，為政府、機構、企業等各部門的決策提供可靠的依據和建議。比如企業在進行新產品推廣時，可以利用對用戶影響力及其傳播的了解，選擇有影響力的用戶和傳播渠道幫助產品推廣，而政府可以選擇合適的影響力群體和渠道來擴大其政策的影響或抵御謠言的傳播。
社會影響力的研究在社會科學和市場學領域已有較長的歷史[1,2]，為影響力傳播的途徑和范圍帶來了新的認識。比如Christakis和Fowler利用美國一個城市上萬人跨32年的醫療記錄數據驗證了肥胖癥和吸煙行為會在社交網絡中相互影響和傳播[3,4]。而伴隨著互聯網、在線社交網絡和大數據的興起以及日益廣泛的應用，在更大規模下更深入地研究影響力的傳播也成為可能。比如近期基于著名的社交網站臉譜（Facebook）平臺的兩項研究，都通過在線隨機試驗方式分別驗證了影響力在選舉意愿和應用選擇中的存在性及其決定性因素[5,6]。
在計算機科學領域，基于互聯網和大數據的影響力傳播研究也從21世紀開始興起。本文集中介紹這十幾年來計算機科學領域在社交網絡影響力傳播方面的研究成果，并對面臨的挑戰和今后的方向加以簡要討論。概括來講，影響力傳播研究有三大支柱（如圖1所示）。第一是影響力傳播模型，主要描述影響力在社交網絡中如何傳播、有何特點和性質。第二是影響力傳播的學習，即如何利用網絡大數據挖掘學習影響力傳播模式和具體傳播模型的參數。第三是影響力傳播優化，著重考慮在不同的傳播模型下，如何通過施加外部作用（比如選取有影響力的初始傳播用戶和改變傳播途徑等）來擴大希望傳播的影響力或者控制和減弱不希望傳播的影響力，也包括有效地監控影響力的傳播等。下文就分別對影響力傳播的這三大支柱進行一一講述。
圖 1 社會影響力傳播研究的三大支柱
影響力的研究和應用也是一個涵蓋很廣的課題，也有其他的綜述型文章對其加以介紹[7,8]。與其他綜述不同的是本文重點介紹對影響力動態傳播特性的研究，而其他方面（如從靜態圖特性估計節點影響力等）請參見其他綜述文章的相關介紹[7,8]。Chen、Lakshmanan和Castillo在近期發表了信息和影響力傳播方面的專著[9]，對影響力傳播的研究有較詳盡的介紹。本文對該專著覆蓋的內容進行了提煉、概括，并包含了對該專著出版后的最新研究成果的介紹和一些新觀點的討論。
2 影響力傳播模型
信息和影響力在社交網絡中的傳播復雜多樣，但排除一些干擾因素后仍然有章可循。在下文中統一用影響力傳播來概括在社交網絡中信息、概念、想法、創新、產品、文化基因（meme）等的傳播。
首先把一個社交網絡描述成一個有向圖G=（V，E），其中V是節點的集合，E?V×V是有向邊的集合。每一個節點v∈V代表一個社交網絡中的人，每一條邊（u,v）∈E代表節點u到節點v的影響力關系。邊是有向的，表明影響力是有方向的，節點u對節點v有影響力，但節點v對節點u可能沒有影響力。在后面具體建模中還通常會對邊加上權重以表示影響力的強度。對于一條有向邊（u,v）∈E，它叫做節點u的出邊，節點v的入邊，節點v是節點u的一個出鄰居，而節點u是節點v的一個入鄰居。一個節點v的所有出鄰居的集合用N+(v)表示，所有入鄰居的集合用N-(v)表示。
通常情況下，針對某一具體傳播的實體（信息、想法、產品等），將圖中的每個點描述為兩種可能狀態：不活躍（inactive）和活躍（active）。不活躍狀態表示該個體還沒有接受對應實體（信息、想法或產品），而活躍狀態表示該個體已經接受對應的實體。節點從不活躍狀態變為活躍狀態表示該節點接受了對應實體，也稱之為被激活。
影響力傳播模型用來刻畫影響力在社交網絡中的傳播模式，也即社交網絡中節點的狀態如何影響其相鄰節點的狀態，并造成某一狀態（通常指活躍狀態）在網絡中擴散傳播。傳播模型分很多種類，其中大多數以隨機模型（stochastic models）來描述，也有用博弈論模型（game-theoretic models）來描述的。本文著重描述隨機模型，因為它更直接地反映了影響力傳播中的不確定性，也是當前研究的主流。
隨機模型又可分為離散時間和連續時間模型、遞進性（progressive）和非遞進性（non-progressive）模型等。離散時間模型將影響力傳播和節點的狀態轉換規定在離散的時間點發生，以便于計算和分析，而連續時間模型允許傳播和節點狀態轉換在連續時間軸上發生。遞進性模型假設任意節點一旦從不活躍變為活躍就會一直保持在活躍狀態，不會再回到不活躍狀態。這類模型多用于信息、產品等的傳播，因為它們一旦擁有，就一般不會再失去，或者只關注傳播過程中所有曾經接受該信息或產品的人群。非遞進模型則允許節點在兩個（或多個）不同狀態之間來回切換。這類模型多用于描述觀點、看法的傳播，因為人的觀點和看法經常會隨著時間和周圍人群的觀點而改變。在這種情況下也許對狀態的描述用支持、反對等詞語比用不活躍和活躍更合適。在眾多模型中，離散時間遞進性模型是研究最多的。本文以介紹經典的離散時間遞進性模型和其上的應用問題為主線，附帶簡略介紹其他模型。
2.1 經典離散時間遞進性傳播模型
影響力傳播模型的研究在社會和管理科學中由來已久[1,2]，但在計算機科學中基于計算和大數據的社交網絡影響力傳播模型的研究還是21世紀之后的事情。首先是Domingos和Richardson于2001年提出了基于馬爾科夫隨機場（Markov random field）的社交網絡影響力模型[10]。嚴格地說，這個模型是關于圖中節點被激活的相關性模型，而不直接表達影響力傳播的因果關系。2003年，Kempe、Kleinberg和Tardos提出了獨立級聯（independent cascade）和線性閾值（linear threshold）等離散時間遞進性傳播模型和它們的若干拓展模型[11]。這些模型總結了前人在社會心理學、市場學及統計物理方面的模型，簡單直觀，基本符合人們對影響力傳播的直覺理解，同時模型具有較好的性質，便于進一步分析和計算。這些模型如今已成為研究影響力傳播的經典模型，被廣泛應用到影響力最大化、影響力學習和影響力傳播模型拓展等各個研究方面。下面對獨立級聯和線性閾值模型加以介紹，并在以后各部分中以獨立級聯模型為主要實例，介紹模型在各方面研究的應用。
2.1.1 獨立級聯模型
如圖2所示，在獨立級聯模型中，每一條圖中的有向邊（u,v）∈E都有一個對應的概率值p（u,v）∈[0,1]。直觀上說，p（u,v）表示當節點u被激活后，節點u通過邊（u,v）獨立激活節點v的概率。獨立級聯模型下的動態傳播過程在離散時間點以如下形式完成：在t=0時刻，一個預先選好的初始集合S0首先被激活，而其他節點都處于不活躍狀態。這個初始節點集合被稱作種子節點集合（seedset）。對任何時刻t≥1，用St表示到這個時刻為止所有活躍點的集合。在任何時刻點t≥1，對任何一個在上一時刻剛被激活的節點u∈St-1\St-2（設S-1=φ），節點u會對它的每個尚未被激活的出鄰居節點v∈N+(v)\St-1嘗試激活一次，而這次嘗試成功的概率為p（u,v），且這次激活嘗試與所有其他的激活嘗試事件相互獨立。如果嘗試成功，則節點v在時刻t被激活，即v∈St\St-1；如果嘗試不成功，且節點v的其他入鄰居也未在時刻t成功激活節點v，則節點v在時刻t仍為不活躍狀態，即v∈V\St。當在某一時刻不再有新的節點被激活時，傳播過程結束。
圖 2 獨立級聯模型示意
圖2給出了獨立級聯模型一次傳播結果的示意。實心方框表示種子節點，空心方框表示傳播結束時被激活的節點；圓圈表示未被激活的節點；實線邊表示影響力在該邊上成功傳播，虛線邊表示影響力未在其上傳播；邊上的數字是該邊上影響力傳播的概率。在t=0時刻，種子節點1和2被激活；在t=1時刻，節點1、2分別激活節點5、4，并且同時激活了節點3；在t=2時刻，節點5成功激活節點6但沒有成功激活節點9；在t=3時刻，節點6沒有成功激活節點7；傳播至此結束，節點7、8和9沒有在這次傳播中被激活。
用S∞表示在傳播過程結束時所有活躍節點的集合。如果總節點數為n，而每一步至少激活一個新節點，則在這個模型下傳播最多在n-1步后結束，即Sn-1=S∞。由于傳播過程是隨機過程，因此S∞是隨機集合。在影響力傳播中經常關心的是傳播結束后被激活節點個數的期望值，即E[|S∞|]，用σ(S0)表示，并稱之為（最終）影響力延展度（influence spread）。
注意到在獨立級聯模型中，任何一個節點u對它的任何一個出鄰居v只有一次嘗試激活機會，且發生在節點u剛被激活的下一時刻。這看起來似乎是模型的一個局限。但如果只關心最終的影響力延展度，一個節點u在何時嘗試激活另一節點v或者是否多次嘗試激活節點v并不重要，只要用p（u,v）表示節點u多次嘗試激活節點v的總成功概率，影響力延展度和引入多次激活嘗試的擴展模型下的延展度是一樣的[9]。如果要考慮中間某時刻的影響力延展度，也可將獨立級聯模型進行適當擴展，以使其更適合實際情況[12]。
獨立級聯模型抽象概括了社交網絡中人與人之間獨立交互影響的行為。它通過邊上的概率來描述人與人之間發生影響的可能性和強度。很多簡單實體（如新消息在在線網絡的傳播或新病毒在人際間的傳播）很符合獨立傳播的特性[13]。獨立級聯模型也在基于實際數據的影響力學習中被初步驗證是有效的。所以獨立級聯模型是目前研究最廣泛、最深入的模型。
2.1.2 線性閾值模型
在線性閾值模型中，每條有向邊（u,v）∈E上都有一個權重w（u,v）∈[0,1]。直觀上說，w（u,v）反映了節點u在節點v的所有入鄰居中影響力的重要性占比。要求∑u∈N-(v)w（u,v）≤1。每個節點v還有一個被影響閾值θv∈[0,1]，這個閾值在0到1的范圍內均勻、隨機地選取，一旦確定在傳播中就不再改變。與獨立級聯模型一樣，在t=0時刻有且僅有種子集合S0中的節點被激活。在之后每個時刻t≥1，每個不活躍節點v∈V\St-1都需要依據它所有已激活的入鄰居到它的線性加權和是否已達到它的被影響值來判斷是否被激活，即是否滿足∑u∈N-(v)∩St-1w（u,v）≤θv；若是，則節點v在時刻t被激活（v∈St）；否則，節點v仍然保持不活躍狀態。當某一時刻不再有新的節點被激活時，傳播過程結束。
線性閾值模型中節點v的閾值θv表達了節點對一個新實體的接受傾向：閾值越高，節點v越不容易被影響；反之，閾值越低越容易被影響。節點v的入鄰居對節點v的影響是聯合發生的，可能任何一個入鄰居都不能單獨激活節點v，但幾個入鄰居聯合起來就可能使對節點v的影響力權重超過節點v的閾值，從而激活節點v。這對應了人類行為中在面對一個相對復雜選擇時（如購買新型手機、選擇移民、參與暴亂等）經常出現的從眾行為[2,13]，也是與獨立級聯模型相比最主要的不同點。
線性閾值模型的隨機性完全由節點被影響閾值的隨機性所決定，一旦隨機閾值被確定，后面的傳播過程完全是確定性的。在線性閾值模型中閾值在0和1之間隨機選取，這反映了對節點閾值的不了解。然而，在實際中人的被影響閾值雖然有隨機性，但應該在更窄的范圍內波動。另一方面，如果用更窄范圍的隨機閾值（如固定閾值）會使模型的分析和計算難度顯著加大[9,11]。所以，線性閾值模型在閾值選取上面臨兩難選擇，這也是這一模型不如獨立級聯模型應用廣泛的一個原因。
2.1.3 獨立級聯和線性閾值模型的推廣
Kempe等在獨立級聯和線性閾值模型的基礎上又對其進行了推廣[11]，引入了諸如觸發模型（triggering model）、通用級聯模型（general cascade model）、通用閾值模型（general threshold model）等?？傮w來講，是讓獨立級聯模型中的獨立概率或線性閾值模型中的線性權重變得更靈活、覆蓋更廣的傳播形式。由于篇幅關系，在這里不再展開介紹。感興趣的讀者請看原文或相關綜述[9,11]。
2.2 其他傳播模型
除了上文介紹的離散時間遞進性經典模型，根據不同實際需要還有很多其他模型，用來刻畫社交網絡中信息和影響力的傳播。在這里只做簡要介紹。
2.2.1 連續時間模型
連續時間模型（continuous-time model）將網絡中兩個相連節點的傳播時延用一個連續時間的密度函數表示，這樣節點的激活可以在任何連續時間內發生[14]。這個模型避免了對實際數據離散化分段，在數據分析時經常是一種有效模型?，F在的研究大多是對獨立級聯模型的連續化，對線性閾值模型的連續化還有待進一步研究。
2.2.2 傳染病模型
顧名思義，傳染病模型（epidemic model）集中研究傳染病或病毒在人群中的傳播[15]，現在也被延伸用來研究信息和影響力傳播。經典傳染病模型將人的狀態分為幾類，比如易感S（susceptible）、感染I（infected）、治愈R（recovered）等。然后，根據可行的狀態轉換定義出不同的模型，如SI模型描述人從易感變為感染；SIS模型允許人從感染回到易感狀態然后再被感染；SIR模型刻畫人從易感變為感染然后再痊愈并永久免疫的情況。傳染病模型有考慮人群整體行為的，也有基于人際之間接觸網絡的。前面介紹的獨立級聯模型與SIR模型在網絡中的傳播基本具有相同的性質。
2.2.3 選舉模型
選舉模型（voter model）原是統計物理里一個常用的模型，現在也被用到社交網絡影響力傳播的研究中[16,17]。在最基本的選舉模型中每個節點有兩個狀態，每個節點u在每個離散時刻從它的鄰居節點中隨機挑選一個節點v，將節點v在上一時刻的狀態作為自己的當前狀態。這一過程類似于社交網絡中人們通過和朋友交流而采納朋友意見的過程，所以選舉模型和它的變種常用來刻畫人們的看法、意見等在社交網絡中的演變。因為節點的狀態可在多個狀態中反復變化，所以選舉模型屬于非遞進性模型，一般用于分析在某一時間點或穩態下的狀態分布和相關性質。
2.2.4 博弈論模型
博弈論模型（game-theoretic model）將每一個節點描述為利益最大化的自私節點，其狀態就是它的博弈策略。用于刻畫傳播的網絡博弈論模型經常將每條邊描述為其兩個頂點的一個協調博弈（coordination game），當兩個頂點選取同一策略時各自的收益都最大[18,19]。這種模型反映了人際之間的趨同效應和某些產品的網絡外部效應（network externality），比如雙方都用Skype作為網絡通信工具對雙方都有益處。這種模型在某節點的一次狀態轉換過程類似于閾值模型，而狀態的反復交替又與選舉模型有類似性質。
2.2.5 多實體傳播模型
在網絡中很可能有多個實體同時傳播它們的影響力，它們之間有可能是相互競爭的關系（比如小米手機和iPhone，或者關于某熱點事件的官方消息和謠言等），也有可能是互補合作關系（比如iPhone和Apple Watch、微軟視窗操作系統和聯想筆記本電腦等）。多實體的傳播會造成更復雜的傳播現象和結果。近幾年，已有不少工作著眼于將單實體傳播模型（如獨立級聯和線性閾值模型）擴展為多實體傳播模型（multi-item diffusion model）[9,20~24]。絕大多數擴展模型只考慮競爭性實體的并發傳播。這些擴展在網絡傳播上基本繼承單實體的傳播模型，但在節點上設置先來先用、后來放棄的規則，并輔以同時到達時的打破平局（tie-breaking）規則。Lu等人最近將多實體的競爭性模型又進一步擴展為既可以描述競爭也可以描述互補合作的比較影響力傳播模型（comparative influence diffusion model）[24]。該模型利用節點自動機和少數幾個參數刻畫了節點在接受一個實體前后會接受另一個實體的不同概率。參數的不同取值范圍可以囊括從完全競爭到部分競爭、相互獨立、部分互補和完全互補的各種可能情況?？偟膩碚f，由于多實體傳播模型引入了更復雜的交互和傳播機制，模型的性質分析和其上的優化問題等也變得更為復雜。
3 影響力最大化問題
影響力傳播建模的一個主要目的是控制和優化影響力的傳播，這其中被廣泛研究的一個核心問題就是影響力最大化（influence maximization）問題。本節以獨立級聯和線性閾值模型為基礎，介紹影響力最大化的研究技術和主要成果，并附帶介紹其他影響力傳播中的優化問題。
3.1 影響力最大化問題的定義
影響力最大化是在給定社交網絡結構G=（V，E）、影響力傳播模型及其參數（如獨立級聯模型和邊上的概率）的情況下，選擇k個節點作為種子節點集合S*，使得以S*為種子節點產生的影響力延展度σ(S*)最大，即S*=argmaxS?V, |S|=kσ(S)。
影響力最大化問題是對病毒營銷（viral marketing）的一個直接數學刻畫。比如一個廠家要推廣產品，希望用病毒式營銷手段，先選擇網絡中少數人送以免費試用產品，希望選中的人試用以后喜歡新產品并主動在其朋友圈推廣，使得更多的人接受和購買該產品，而這些新用戶又會在他們的朋友圈中進一步推廣該產品。廠家的期望是，基于對網絡中影響力傳播的了解（參見第4節影響力傳播學習），能夠找出接受試用產品的最佳用戶（種子節點），使得最終接受產品的人最多（影響力延展度最大）。這個問題正是影響力最大化的優化目標。
3.2 子模函數（submodular function）和影響力最大化的貪心算法技術
上述影響力最大化問題屬于組合優化問題，更具體地說，影響力最大化在經典的獨立級聯和線性閾值模型下都屬于圖上覆蓋問題的一種擴展，因而與圖覆蓋問題一樣，在這些模型下影響力最大化是NP難的問題。解決NP難優化問題的一個重要方法是利用有效的近似算法，比如即使找不到使影響力延展度達到最大的種子集合，但可能找到一個較好的集合，使得該集合的影響力延展度接近最優值，而兩者之間的比例就是近似算法的近似比。影響力最大化的近似算法設計核心依賴于影響力延展度函數的子模性質和其帶來的貪心算法技術。
對于一個將有限集合V的任意子集映射到實數值的函數f:2V→R，稱f滿足子模性，對于任意一個子集S?V和它的任意一個超集T（S?T?V）以及T外的任意一個元素u∈V\T，f滿足f（S∪{u}）-f（S）≥f（T∪{u}）-f（T）。子模性反映了元素u在集合S基礎上的增量效應隨著S的增大而遞減，這就是在經濟學中經常用到的邊界效用遞減現象。很多圖覆蓋問題都具有子模性，因為覆蓋的重疊現象會造成邊界效用遞減。重要的是，影響力延展度作為種子集合的函數σ(S)已被證明在獨立級聯和線性閾值模型以及它們的很多擴展模型下都滿足子模性[11]。
和子模性經常在一起使用（但非絕對必要）的還有集合函數的單調性，稱集合函數f滿足單調性，對于任意一個子集S?V和它的任意一個超集T（S?T?V），f滿足f（S）≤f（T）。影響力延展度函數σ(S)同樣具有單調性。
一個單調子模函數的重要性質是可以用如下的貪心算法得到函數最大值的近似解。
算法：單調子模函數的貪心算法。
輸入：單調子模函數f，預算k。
輸出：大小為k的子集S。
初始化： S= φ
fori =1 to k do
v=arg max u∈V\S (f(S∪{u} )-f(S) )
S=S∪{v}
endfor
返回S
貪心算法分k輪，每一輪都要找到一個元素，使得它對已找到的元素來說邊界增量最大。如果f是單調子模的，且f（φ）=0，則貪心算法找到的貪心解保證至少是最優解的（1-1/e），即大約63%[25]。所以貪心算法是單調子模函數最大化的（1-1/e）的近似算法。
由于影響力延展度函數σ(S)在獨立級聯和線性閾值模型下都具有單調性和子模性，且顯然σ(φ)=0，所以可以用貪心算法來解決影響力最大化問題，以達到的（1-1/e）近似比。
3.3 可擴展的影響力最大化算法
然而，第3.2節給出的單調子模函數的貪心算法并未完全解決影響力最大化問題，因為其中的關鍵一步需要計算一個種子集合S的延展度σ(S)，而計算σ(S)的精確值本身在獨立級聯和線性閾值模型下都是很難的問題（技術上稱為NP難問題[26,27]）。在Kempe等人的論文中[11]，簡單地提出用隨機模擬的方法（通稱蒙特卡洛方法）來模擬影響力傳播，從而估算σ(S)的近似解。在這種近似解情況下，貪心算法的解能達到的（1-1/e-ε）近似解，其中ε是一個大于零的數，對應σ(S)估算的精確性。
但是簡單地在影響力最大化中用蒙特卡洛方法有一個嚴重的問題，就是時間效率很低。在一個不算大的上萬個節點的圖中，如果對每一次延展度估計都用并不算多的2 000次蒙特卡洛模擬，找出50個種子節點的貪心算法要運行好幾天[9]。為了解決這個效率問題，諸多研究提出了各種可擴展的影響力最大化（scalable influence maximization）算法。這些算法基本可分為兩大類，一類是利用模型具體特點的啟發式算法[26~30]，另一類是改進蒙特卡洛方法的貪心近似算法[31~35]。
在啟發式算法中，PMIA是一個有代表性的針對獨立級聯模型的算法[26]。PMIA的主要思想是將在一般圖上針對某一節點影響力的傳播轉化為在該節點附近區域的一棵有代表性的最大影響力傳播子樹上的傳播。這樣做的好處是：獨立級聯模型的影響力延展度計算在樹結構上可在線性時間內完成；構造以某一節點為中心的最大影響力子樹（maximum influence arborescence）可以用Dijkstra最短路徑算法在近線性時間完成；只考慮節點附近的子樹會大大減少計算量，同時又不會損失太多計算精度，因為影響力在幾步傳播后已變弱到可以忽略不計。PMIA和當時已做過優化的蒙特卡洛貪心算法相比，速度提高了1 000倍，而選出種子的影響力在很多實際網絡的模擬實驗中都很接近貪心算法。之后，又有不少工作對算法做了進一步改進和提高，比如IRIE算法利用圖上整體迭代方法提高了算法速度，同時節省了內存使用[30]。針對線性閾值模型也有LDAG算法[27]和SIMPATH算法[29]。這些算法的優點是速度很快，通常效果也很好，但它們缺乏理論保證，所以究竟它在哪些實際網絡中適用，還有待進一步論證。
在對蒙特卡洛貪心算法的改進方面，一種改進是依據延展度函數的子模性利用偷懶估值方法（lazy evaluation）減少對函數估值的次數，如CELF算法[32]。單純用這種方法雖然對最原始的蒙特卡洛方法有上百倍的提高（運行時間從幾天降低到幾個小時），但與高效的啟發式算法相比還有上千倍的差別（幾小時和幾秒鐘的差別）。最近，由Borgs等人率先提出的反向蒙特卡洛算法改變了這種局面[31]。反向蒙特卡洛算法的核心思想是不從種子節點去模擬估算種子節點的影響力，而是隨機選取圖上節點，從該節點出發以所有邊的相反方向進行蒙特卡洛模擬，得到的集合實際上是最可能影響該節點的集合。這樣的集合被稱作反向可達集合（reserve reachabl set），簡稱RR集合。而如果一個節點經常在RR集合中出現，那么該節點就是一個影響力大的節點?；谶@種思想，Borgs等人理論上證明了他們的算法可達到近乎最優的近線性時間，同時仍有（1-1/e-ε）的近似比保證。之后Tang等人對他們的算法加以改進，提出了TIM/TIM+和IMM算法[33,34]，并進行了模擬實驗驗證，最新的IMM算法在實驗中已超越了啟發式算法（如IRIE、SIMPATH）的速度，同時仍有一定的理論保證（ε=0.5，所以理論保證較弱，但對任意圖適用）。同時他們指出這種方法適用于獨立級聯、線性閾值和更廣的觸發模型。但基于RR集合的這些算法有一個問題是，當選出k個種子節點時，算法并不保證也同時找到所有小于k個種子集合的近似解。Cohen等人提出的SKIM算法避免了這個問題[35]：SKIM算法通過刻畫節點在隨機意義下的可達性草圖（reachability sketches）來高效計算節點影響力和選擇種子節點。理論上，SKIM算法不保證近線性時間但有近似比保證；實驗上，它與TIM/TIM+相當。
3.4 其他基于影響力的優化問題
基于影響力傳播還可以提出很多的優化問題或對模型的拓展。這仍然是現在學術界十分活躍的領域。下面簡要介紹一下這方面的幾個問題和相關研究。
（1）種子集合最小化
種子集合最小化是影響力最大化的對偶問題。它要求影響力延展度達到一定數值情況下選取的種子集合盡量小。這個問題的解法也是基于單調子模函數的貪心算法，但由于優化目標變為最小化種子集合的大小，近似比變為了O（lnη），其中η是影響力延展度要求達到的閾值[36,37]。
（2）利潤最大化
利潤最大化考慮到選取種子有成本，而被影響的非種子節點才會產生收益。所以，利潤最大化的目標是選取合適的種子節點（不再受硬性的個數限制），使得最終的期望收益減去種子成本最大。與影響力最大化相比，利潤最大化的一個重要區別是它的目標函數（即給定種子集合下的期望利潤）不再是單調的。因為當種子集合達到一定程度時，再加一個節點作為種子帶來的額外期望收益可能已經不能抵消加入這個種子的費用，但是利潤函數仍具有子模性，在這種情況下，利潤最大化要利用非單調子模函數的優化技術[38]。
（3）影響力傳播監控
影響力傳播可能達到網絡的各個角落，如何布置有效的監控節點對各種影響力傳播提供及時、準確的報告，也是一個重要課題。在技術層面，選擇有效的網絡監控節點和選擇有效的種子節點有相似性，在適當的模型和問題描述下都具有單調性和子模性，所以都可以用貪心算法來解決[32]。
（4）多實體傳播模型下的影響力最大化
多實體的傳播會給影響力優化帶來很多變種。比如在已知一個競爭實體分布的種子節點情況下，如何選取我方的種子節點從而最大化我方的影響力[9]或者盡量減少對方的影響力，也稱為影響力阻斷最大化（influence blocking maximization）[20,22]。影響力阻斷最大化可以應用在抵御謠言的傳播。也有學者研究社交網絡平臺在有多個競爭實體下如何公平分配種子資源的問題[23]。Lu等人在他們最新的研究中還考慮了在互補性實體間的影響力最大化問題[24]，比如在已知一個互補實體的種子節點情況下，如何選取本方實體的種子節點以最大化本方的影響力（即自我影響力最大化（self influence maximization））或者最大化互補的對方的影響力（即互補影響力最大化（complementary influence maximization））。可以看出，多實體傳播下的影響力最大化種類繁多，具體應用要具體分析。絕大多數問題仍然基于子模函數的最大化，但是多實體模型在不少情況下不再具備子模性，所以需要尋找新的解決途徑。
（5）網絡拓撲的優化
影響力傳播研究中，也有研究如何有效地改變網絡拓撲結構來優化影響力的。比如如何有效刪除圖中的邊或節點使得種子節點的影響力盡量小，這對應了防止傳染病傳播中的隔離和免疫措施。也可以考慮如何增加點或邊以最大化影響力，這在一定程度上對應了社交網絡平臺朋友推薦的情形。Khalil等人針對一種拓撲變化下定義的目標函數，論證了它的子模性或對稱的超模性（supermodularity），從而用子?；虺：瘮档膬灮夹g進行處理[39]。值得一提的是，他們定義的一個集合的影響力并不是集合整體的影響力延展度，而是集合中每個個體的影響力延展度的算術平均。這個定義使得他們能夠得到對應的子模或超模性結論，但這樣的模型只適用于單一種子從種子集合中隨機選取的情形。
（6）非子模性的影響力優化問題
當對影響力傳播模型進行一定擴展或對優化目標進行一定改變后，新的模型或問題經常就不再具有子模性（或超模性）。在最近的研究中對非子模性的影響力優化問題也提出了一些解決方法，比如利用整數規劃[40]，將其轉化為相近的子模問題[41]，假設圖的一部分對應的帶權重的鄰接矩陣有常數秩[42]，將非子模函數夾于兩個子模函數之間的三明治方法[24]或者利用基于傳播模型的啟發式算法[43]。這些方法對某些具體問題有較好的效果，但非子模性的影響力優化問題的系統性研究還有待完善。
影響力傳播中還有很多其他相關問題和相關算法，受篇幅限制，本文不能面面俱到。
總結
以上是生活随笔為你收集整理的《大数据》2015年第3期“研究”——社交网络影响力传播研究（上）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Go Embed简明教程
- 下一篇： 【软件工程】软件复用