陳 衛(wèi)

微軟亞洲研究院 北京 100080

社交網(wǎng)絡(luò)影響力傳播研究

陳 衛(wèi)

微軟亞洲研究院 北京 100080

隨著互聯(lián)網(wǎng)和大數(shù)據(jù)的研究應(yīng)用日益廣泛，對社交網(wǎng)絡(luò)影響力傳播的研究成為數(shù)據(jù)挖掘和社交網(wǎng)絡(luò)分析中的熱點。從影響力傳播模型、影響力傳播學習和影響力傳播優(yōu)化3個方面總結(jié)了近些年計算機科學領(lǐng)域?qū)τ绊懥鞑パ芯康闹饕晒故玖擞绊懥鞑パ芯恐袑﹄S機模型、數(shù)據(jù)挖掘、算法優(yōu)化和博弈論等技術(shù)的綜合運用。最后，簡要討論了影響力傳播研究和應(yīng)用中存在的問題、挑戰(zhàn)及今后的研究方向。

社交網(wǎng)絡(luò)；社會影響力；影響力傳播模型；影響力最大化；社會影響力學習；病毒營銷

1 引言

任何社會性動物在個體與個體、群體與個體之間都存在著相互影響的關(guān)系，例如個體依從群體的行為會有利于獵食或減少被獵食的可能。而人類作為具有復雜交流手段的高級社會性動物，社會影響力在社會生活中更是無處不在。小到聽一首歌曲、選一個餐館，大到確定政治觀點或買一處房產(chǎn)等，人們的各種選擇和決定常常受家人、同事、朋友以及更廣泛的大眾傾向的影響。深入認識影響力的產(chǎn)生和傳播模式有助于理解人類群體和個體的行為，從而能夠預期人們的行為，為政府、機構(gòu)、企業(yè)等各部門的決策提供可靠的依據(jù)和建議。比如企業(yè)在進行新產(chǎn)品推廣時，可以利用對用戶影響力及其傳播的了解，選擇有影響力的用戶和傳播渠道幫助產(chǎn)品推廣，而政府可以選擇合適的影響力群體和渠道來擴大其政策的影響或抵御謠言的傳播。

社會影響力的研究在社會科學和市場學領(lǐng)域已有較長的歷史[1,2]，為影響力傳播的途徑和范圍帶來了新的認識。比如Christakis和Fowler利用美國一個城市上萬人跨32年的醫(yī)療記錄數(shù)據(jù)驗證了肥胖癥和吸煙行為會在社交網(wǎng)絡(luò)中相互影響和傳播[3,4]。而伴隨著互聯(lián)網(wǎng)、在線社交網(wǎng)絡(luò)和大數(shù)據(jù)的興起以及日益廣泛的應(yīng)用，在更大規(guī)模下更深入地研究影響力的傳播也成為可能。比如近期基于著名的社交網(wǎng)站臉譜（Facebook）平臺的兩項研究，都通過在線隨機試驗方式分別驗證了影響力在選舉意愿和應(yīng)用選擇中的存在性及其決定性因素[5,6]。

在計算機科學領(lǐng)域，基于互聯(lián)網(wǎng)和大數(shù)據(jù)的影響力傳播研究也從21世紀開始興起。本文集中介紹這十幾年來計算機科學領(lǐng)域在社交網(wǎng)絡(luò)影響力傳播方面的研究成果，并對面臨的挑戰(zhàn)和今后的方向加以簡要討論。概括來講，影響力傳播研究有三大支柱（如圖1所示）。第一是影響力傳播模型，主要描述影響力在社交網(wǎng)絡(luò)中如何傳播、有何特點和性質(zhì)。第二是影響力傳播的學習，即如何利用網(wǎng)絡(luò)大數(shù)據(jù)挖掘?qū)W習影響力傳播模式和具體傳播模型的參數(shù)。第三是影響力傳播優(yōu)化，著重考慮在不同的傳播模型下，如何通過施加外部作用（比如選取有影響力的初始傳播用戶和改變傳播途徑等）來擴大希望傳播的影響力或者控制和減弱不希望傳播的影響力，也包括有效地監(jiān)控影響力的傳播等。下文就分別對影響力傳播的這三大支柱進行一一講述。

影響力的研究和應(yīng)用也是一個涵蓋很廣的課題，也有其他的綜述型文章對其加以介紹[7,8]。與其他綜述不同的是本文重點介紹對影響力動態(tài)傳播特性的研究，而其他方面（如從靜態(tài)圖特性估計節(jié)點影響力等）請參見其他綜述文章的相關(guān)介紹[7,8]。Chen、Lakshmanan和Castillo在近期發(fā)表了信息和影響力傳播方面的專著[9]，對影響力傳播的研究有較詳盡的介紹。本文對該專著覆蓋的內(nèi)容進行了提煉、概括，并包含了對該專著出版后的最新研究成果的介紹和一些新觀點的討論。

圖1 社會影響力傳播研究的三大支柱

2 影響力傳播模型

信息和影響力在社交網(wǎng)絡(luò)中的傳播復雜多樣，但排除一些干擾因素后仍然有章可循。在下文中統(tǒng)一用影響力傳播來概括在社交網(wǎng)絡(luò)中信息、概念、想法、創(chuàng)新、產(chǎn)品、文化基因（meme）等的傳播。

首先把一個社交網(wǎng)絡(luò)描述成一個有向圖G=（V，E），其中V是節(jié)點的集合，是有向邊的集合。每一個節(jié)點v∈V代表一個社交網(wǎng)絡(luò)中的人，每一條邊（u,v）∈E代表節(jié)點u到節(jié)點v的影響力關(guān)系。邊是有向的，表明影響力是有方向的，節(jié)點u對節(jié)點v有影響力，但節(jié)點v對節(jié)點u可能沒有影響力。在后面具體建模中還通常會對邊加上權(quán)重以表示影響力的強度。對于一條有向邊（u,v）∈E，它叫做節(jié)點u的出邊，節(jié)點v的入邊，節(jié)點v是節(jié)點u的一個出鄰居，而節(jié)點u是節(jié)點v的一個入鄰居。一個節(jié)點v的所有出鄰居的集合用N+(v)表示，所有入鄰居的集合用N-(v)表示。

通常情況下，針對某一具體傳播的實體（信息、想法、產(chǎn)品等），將圖中的每個點描述為兩種可能狀態(tài)：不活躍（inactive）和活躍（active）。不活躍狀態(tài)表示該個體還沒有接受對應(yīng)實體（信息、想法或產(chǎn)品），而活躍狀態(tài)表示該個體已經(jīng)接受對應(yīng)的實體。節(jié)點從不活躍狀態(tài)變?yōu)榛钴S狀態(tài)表示該節(jié)點接受了對應(yīng)實體，也稱之為被激活。

影響力傳播模型用來刻畫影響力在社交網(wǎng)絡(luò)中的傳播模式，也即社交網(wǎng)絡(luò)中節(jié)點的狀態(tài)如何影響其相鄰節(jié)點的狀態(tài)，并造成某一狀態(tài)（通常指活躍狀態(tài)）在網(wǎng)絡(luò)中擴散傳播。傳播模型分很多種類，其中大多數(shù)以隨機模型（stochastic models）來描述，也有用博弈論模型（gametheoretic models）來描述的。本文著重描述隨機模型，因為它更直接地反映了影響力傳播中的不確定性，也是當前研究的主流。

隨機模型又可分為離散時間和連續(xù)時間模型、遞進性（progressive）和非遞進性（non-progressive）模型等。離散時間模型將影響力傳播和節(jié)點的狀態(tài)轉(zhuǎn)換規(guī)定在離散的時間點發(fā)生，以便于計算和分析，而連續(xù)時間模型允許傳播和節(jié)點狀態(tài)轉(zhuǎn)換在連續(xù)時間軸上發(fā)生。遞進性模型假設(shè)任意節(jié)點一旦從不活躍變?yōu)榛钴S就會一直保持在活躍狀態(tài)，不會再回到不活躍狀態(tài)。這類模型多用于信息、產(chǎn)品等的傳播，因為它們一旦擁有，就一般不會再失去，或者只關(guān)注傳播過程中所有曾經(jīng)接受該信息或產(chǎn)品的人群。非遞進模型則允許節(jié)點在兩個（或多個）不同狀態(tài)之間來回切換。這類模型多用于描述觀點、看法的傳播，因為人的觀點和看法經(jīng)常會隨著時間和周圍人群的觀點而改變。在這種情況下也許對狀態(tài)的描述用支持、反對等詞語比用不活躍和活躍更合適。在眾多模型中，離散時間遞進性模型是研究最多的。本文以介紹經(jīng)典的離散時間遞進性模型和其上的應(yīng)用問題為主線，附帶簡略介紹其他模型。

2.1 經(jīng)典離散時間遞進性傳播模型

影響力傳播模型的研究在社會和管理科學中由來已久[1,2]，但在計算機科學中基于計算和大數(shù)據(jù)的社交網(wǎng)絡(luò)影響力傳播模型的研究還是21世紀之后的事情。首先是Domingos和 Richardson 于2001年提出了基于馬爾科夫隨機場（Markov random field）的社交網(wǎng)絡(luò)影響力模型[10]。嚴格地說，這個模型是關(guān)于圖中節(jié)點被激活的相關(guān)性模型，而不直接表達影響力傳播的因果關(guān)系。2003年，Kempe、Kleinberg和 Tardos提出了獨立級聯(lián)（independent cascade）和線性閾值（linear threshold）等離散時間遞進性傳播模型和它們的若干拓展模型[11]。這些模型總結(jié)了前人在社會心理學、市場學及統(tǒng)計物理方面的模型，簡單直觀，基本符合人們對影響力傳播的直覺理解，同時模型具有較好的性質(zhì)，便于進一步分析和計算。這些模型如今已成為研究影響力傳播的經(jīng)典模型，被廣泛應(yīng)用到影響力最大化、影響力學習和影響力傳播模型拓展等各個研究方面。下面對獨立級聯(lián)和線性閾值模型加以介紹，并在以后各部分中以獨立級聯(lián)模型為主要實例，介紹模型在各方面研究的應(yīng)用。

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

如圖2所示，在獨立級聯(lián)模型中，每一條圖中的有向邊（u,v）∈E都有一個對應(yīng)的概率值p（u,v）∈[0,1]。直觀上說，p（u,v）表示當節(jié)點u被激活后，節(jié)點u通過邊（u,v）獨立激活節(jié)點v的概率。獨立級聯(lián)模型下的動態(tài)傳播過程在離散時間點以如下形式完成：在t=0時刻，一個預先選好的初始集合S0首先被激活，而其他節(jié)點都處于不活躍狀態(tài)。這個初始節(jié)點集合被稱作種子節(jié)點集合（seed set）。對任何時刻t≥1，用St表示到這個時刻為止所有活躍點的集合。在任何時刻點t≥1，對任何一個在上一時刻剛被激活的節(jié)點u∈St-1St-2（設(shè)S-1=φ），節(jié)點u會對它的每個尚未被激活的出鄰居節(jié)點v∈N+(v)St-1嘗試激活一次，而這次嘗試成功的概率為p（u,v），且這次激活嘗試與所有其他的激活嘗試事件相互獨立。如果嘗試成功，則節(jié)點v在時刻t被激活，即v∈StSt-1；如果嘗試不成功，且節(jié)點v的其他入鄰居也未在時刻t成功激活節(jié)點v，則節(jié)點v在時刻t仍為不活躍狀態(tài)，即v∈VSt。當在某一時刻不再有新的節(jié)點被激活時，傳播過程結(jié)束。

圖2 獨立級聯(lián)模型示意

圖2 給出了獨立級聯(lián)模型一次傳播結(jié)果的示意。實心方框表示種子節(jié)點，空心方框表示傳播結(jié)束時被激活的節(jié)點；圓圈表示未被激活的節(jié)點；實線邊表示影響力在該邊上成功傳播，虛線邊表示影響力未在其上傳播；邊上的數(shù)字是該邊上影響力傳播的概率。在t=0時刻，種子節(jié)點1和2被激活；在t=1時刻，節(jié)點1、2分別激活節(jié)點5、4，并且同時激活了節(jié)點3；在t=2時刻，節(jié)點5成功激活節(jié)點6但沒有成功激活節(jié)點9；在t=3時刻，節(jié)點6沒有成功激活節(jié)點7；傳播至此結(jié)束，節(jié)點7、8和9沒有在這次傳播中被激活。

用S∞表示在傳播過程結(jié)束時所有活躍節(jié)點的集合。如果總節(jié)點數(shù)為n，而每一步至少激活一個新節(jié)點，則在這個模型下傳播最多在n-1步后結(jié)束，即Sn-1=S∞。由于傳播過程是隨機過程，因此S∞是隨機集合。在影響力傳播中經(jīng)常關(guān)心的是傳播結(jié)束后被激活節(jié)點個數(shù)的期望值，即E[|S∞|]，用σ(S0)表示，并稱之為（最終）影響力延展度（influence spread）。

注意到在獨立級聯(lián)模型中，任何一個節(jié)點u對它的任何一個出鄰居v只有一次嘗試激活機會，且發(fā)生在節(jié)點u剛被激活的下一時刻。這看起來似乎是模型的一個局限。但如果只關(guān)心最終的影響力延展度，一個節(jié)點u在何時嘗試激活另一節(jié)點v或者是否多次嘗試激活節(jié)點v并不重要，只要用p（u,v）表示節(jié)點u多次嘗試激活節(jié)點v的總成功概率，影響力延展度和引入多次激活嘗試的擴展模型下的延展度是一樣的[9]。如果要考慮中間某時刻的影響力延展度，也可將獨立級聯(lián)模型進行適當擴展，以使其更適合實際情況[12]。

獨立級聯(lián)模型抽象概括了社交網(wǎng)絡(luò)中人與人之間獨立交互影響的行為。它通過邊上的概率來描述人與人之間發(fā)生影響的可能性和強度。很多簡單實體（如新消息在在線網(wǎng)絡(luò)的傳播或新病毒在人際間的傳播）很符合獨立傳播的特性[13]。獨立級聯(lián)模型也在基于實際數(shù)據(jù)的影響力學習中被初步驗證是有效的。所以獨立級聯(lián)模型是目前研究最廣泛、最深入的模型。

2.1.2 線性閾值模型

在線性閾值模型中，每條有向邊（u,v）∈E上都有一個權(quán)重w（u,v）∈[0,1]。直觀上說，w（u,v）反映了節(jié)點u在節(jié)點v的所有入鄰居中影響力的重要性占比。要求∑u∈N-(v)w（u,v）≤1。每個節(jié)點v還有一個被影響閾值θv∈[0,1]，這個閾值在0到1的范圍內(nèi)均勻、隨機地選取，一旦確定在傳播中就不再改變。與獨立級聯(lián)模型一樣，在t=0時刻有且僅有種子集合S0中的節(jié)點被激活。在之后每個時刻t≥1，每個不活躍節(jié)點v∈VSt-1都需要依據(jù)它所有已激活的入鄰居到它的線性加權(quán)和是否已達到它的被影響值來判斷是否被激活，即是否滿足若是，則節(jié)點v在時刻t被激活（v∈St）；否則，節(jié)點v仍然保持不活躍狀態(tài)。當某一時刻不再有新的節(jié)點被激活時，傳播過程結(jié)束。

線性閾值模型中節(jié)點v的閾值θv表達了節(jié)點對一個新實體的接受傾向：閾值越高，節(jié)點v越不容易被影響；反之，閾值越低越容易被影響。節(jié)點v的入鄰居對節(jié)點v的影響是聯(lián)合發(fā)生的，可能任何一個入鄰居都不能單獨激活節(jié)點v，但幾個入鄰居聯(lián)合起來就可能使對節(jié)點v的影響力權(quán)重超過節(jié)點v的閾值，從而激活節(jié)點v。這對應(yīng)了人類行為中在面對一個相對復雜選擇時（如購買新型手機、選擇移民、參與暴亂等）經(jīng)常出現(xiàn)的從眾行為[2,13]，也是與獨立級聯(lián)模型相比最主要的不同點。

線性閾值模型的隨機性完全由節(jié)點被影響閾值的隨機性所決定，一旦隨機閾值被確定，后面的傳播過程完全是確定性的。在線性閾值模型中閾值在0和1之間隨機選取，這反映了對節(jié)點閾值的不了解。然而，在實際中人的被影響閾值雖然有隨機性，但應(yīng)該在更窄的范圍內(nèi)波動。另一方面，如果用更窄范圍的隨機閾值（如固定閾值）會使模型的分析和計算難度顯著加大[9,11]。所以，線性閾值模型在閾值選取上面臨兩難選擇，這也是這一模型不如獨立級聯(lián)模型應(yīng)用廣泛的一個原因。

2.1.3 獨立級聯(lián)和線性閾值模型的推廣

Kempe等在獨立級聯(lián)和線性閾值模型的基礎(chǔ)上又對其進行了推廣[11]，引入了諸如觸發(fā)模型（triggering model）、通用級聯(lián)模型（general cascade model）、通用閾值模型（general threshold model）等?？傮w來講，是讓獨立級聯(lián)模型中的獨立概率或線性閾值模型中的線性權(quán)重變得更靈活、覆蓋更廣的傳播形式。由于篇幅關(guān)系，在這里不再展開介紹。感興趣的讀者請看原文或相關(guān)綜述[9,11]。

2.2 其他傳播模型

除了上文介紹的離散時間遞進性經(jīng)典模型，根據(jù)不同實際需要還有很多其他模型，用來刻畫社交網(wǎng)絡(luò)中信息和影響力的傳播。在這里只做簡要介紹。

2.2.1 連續(xù)時間模型

連續(xù)時間模型（continuous-time model）將網(wǎng)絡(luò)中兩個相連節(jié)點的傳播時延用一個連續(xù)時間的密度函數(shù)表示，這樣節(jié)點的激活可以在任何連續(xù)時間內(nèi)發(fā)生[14]。這個模型避免了對實際數(shù)據(jù)離散化分段，在數(shù)據(jù)分析時經(jīng)常是一種有效模型?，F(xiàn)在的研究大多是對獨立級聯(lián)模型的連續(xù)化，對線性閾值模型的連續(xù)化還有待進一步研究。

2.2.2 傳染病模型

顧名思義，傳染病模型（epidemic model）集中研究傳染病或病毒在人群中的傳播[15]，現(xiàn)在也被延伸用來研究信息和影響力傳播。經(jīng)典傳染病模型將人的狀態(tài)分為幾類，比如易感S（susceptible）、感染I（infected）、治愈R（recovered）等。然后，根據(jù)可行的狀態(tài)轉(zhuǎn)換定義出不同的模型，如SI 模型描述人從易感變?yōu)楦腥?；SIS模型允許人從感染回到易感狀態(tài)然后再被感染；SIR 模型刻畫人從易感變?yōu)楦腥救缓笤偃⒂谰妹庖叩那闆r。傳染病模型有考慮人群整體行為的，也有基于人際之間接觸網(wǎng)絡(luò)的。前面介紹的獨立級聯(lián)模型與SIR模型在網(wǎng)絡(luò)中的傳播基本具有相同的性質(zhì)。

2.2.3 選舉模型

選舉模型（voter model）原是統(tǒng)計物理里一個常用的模型，現(xiàn)在也被用到社交網(wǎng)絡(luò)影響力傳播的研究中[16,17]。在最基本的選舉模型中每個節(jié)點有兩個狀態(tài)，每個節(jié)點u在每個離散時刻從它的鄰居節(jié)點中隨機挑選一個節(jié)點v，將節(jié)點v在上一時刻的狀態(tài)作為自己的當前狀態(tài)。這一過程類似于社交網(wǎng)絡(luò)中人們通過和朋友交流而采納朋友意見的過程，所以選舉模型和它的變種常用來刻畫人們的看法、意見等在社交網(wǎng)絡(luò)中的演變。因為節(jié)點的狀態(tài)可在多個狀態(tài)中反復變化，所以選舉模型屬于非遞進性模型，一般用于分析在某一時間點或穩(wěn)態(tài)下的狀態(tài)分布和相關(guān)性質(zhì)。

2.2.4 博弈論模型

博弈論模型（game-theoretic model）將每一個節(jié)點描述為利益最大化的自私節(jié)點，其狀態(tài)就是它的博弈策略。用于刻畫傳播的網(wǎng)絡(luò)博弈論模型經(jīng)常將每條邊描述為其兩個頂點的一個協(xié)調(diào)博弈（coordination game），當兩個頂點選取同一策略時各自的收益都最大[18,19]。這種模型反映了人際之間的趨同效應(yīng)和某些產(chǎn)品的網(wǎng)絡(luò)外部效應(yīng)（network externality），比如雙方都用Skype作為網(wǎng)絡(luò)通信工具對雙方都有益處。這種模型在某節(jié)點的一次狀態(tài)轉(zhuǎn)換過程類似于閾值模型，而狀態(tài)的反復交替又與選舉模型有類似性質(zhì)。

2.2.5 多實體傳播模型

在網(wǎng)絡(luò)中很可能有多個實體同時傳播它們的影響力，它們之間有可能是相互競爭的關(guān)系（比如小米手機和iPhone，或者關(guān)于某熱點事件的官方消息和謠言等），也有可能是互補合作關(guān)系（比如iPhone和Apple Watch、微軟視窗操作系統(tǒng)和聯(lián)想筆記本電腦等）。多實體的傳播會造成更復雜的傳播現(xiàn)象和結(jié)果。近幾年，已有不少工作著眼于將單實體傳播模型（如獨立級聯(lián)和線性閾值模型）擴展為多實體傳播模型（multi-item diffusion model）[9,20～24]。絕大多數(shù)擴展模型只考慮競爭性實體的并發(fā)傳播。這些擴展在網(wǎng)絡(luò)傳播上基本繼承單實體的傳播模型，但在節(jié)點上設(shè)置先來先用、后來放棄的規(guī)則，并輔以同時到達時的打破平局（tie-breaking）規(guī)則。Lu等人最近將多實體的競爭性模型又進一步擴展為既可以描述競爭也可以描述互補合作的比較影響力傳播模型（comparative influence diffusion model）[24]。該模型利用節(jié)點自動機和少數(shù)幾個參數(shù)刻畫了節(jié)點在接受一個實體前后會接受另一個實體的不同概率。參數(shù)的不同取值范圍可以囊括從完全競爭到部分競爭、相互獨立、部分互補和完全互補的各種可能情況。總的來說，由于多實體傳播模型引入了更復雜的交互和傳播機制，模型的性質(zhì)分析和其上的優(yōu)化問題等也變得更為復雜。

3 影響力最大化問題

影響力傳播建模的一個主要目的是控制和優(yōu)化影響力的傳播，這其中被廣泛研究的一個核心問題就是影響力最大化（influence maximization）問題。本節(jié)以獨立級聯(lián)和線性閾值模型為基礎(chǔ)，介紹影響力最大化的研究技術(shù)和主要成果，并附帶介紹其他影響力傳播中的優(yōu)化問題。

3.1 影響力最大化問題的定義

影響力最大化是在給定社交網(wǎng)絡(luò)結(jié)構(gòu)G=（V，E）、影響力傳播模型及其參數(shù)（如獨立級聯(lián)模型和邊上的概率）的情況下，選擇k個節(jié)點作為種子節(jié)點集合S*，使得以S*為種子節(jié)點產(chǎn)生的影響力延展度σ(S*)最大，即

影響力最大化問題是對病毒營銷（viral marketing）的一個直接數(shù)學刻畫。比如一個廠家要推廣產(chǎn)品，希望用病毒式營銷手段，先選擇網(wǎng)絡(luò)中少數(shù)人送以免費試用產(chǎn)品，希望選中的人試用以后喜歡新產(chǎn)品并主動在其朋友圈推廣，使得更多的人接受和購買該產(chǎn)品，而這些新用戶又會在他們的朋友圈中進一步推廣該產(chǎn)品。廠家的期望是，基于對網(wǎng)絡(luò)中影響力傳播的了解（參見第4節(jié)影響力傳播學習），能夠找出接受試用產(chǎn)品的最佳用戶（種子節(jié)點），使得最終接受產(chǎn)品的人最多（影響力延展度最大）。這個問題正是影響力最大化的優(yōu)化目標。

3.2 子模函數(shù)（submodular function）和影響力最大化的貪心算法技術(shù)

上述影響力最大化問題屬于組合優(yōu)化問題，更具體地說，影響力最大化在經(jīng)典的獨立級聯(lián)和線性閾值模型下都屬于圖上覆蓋問題的一種擴展，因而與圖覆蓋問題一樣，在這些模型下影響力最大化是NP難的問題。解決NP難優(yōu)化問題的一個重要方法是利用有效的近似算法，比如即使找不到使影響力延展度達到最大的種子集合，但可能找到一個較好的集合，使得該集合的影響力延展度接近最優(yōu)值，而兩者之間的比例就是近似算法的近似比。影響力最大化的近似算法設(shè)計核心依賴于影響力延展度函數(shù)的子模性質(zhì)和其帶來的貪心算法技術(shù)。

對于一個將有限集合V的任意子集映射到實數(shù)值的函數(shù)f:2V→R，稱f滿足子模性，對于任意一個子集和它的任意一個超集以及T外的任意一個元素u∈VT，f滿足f（S∪{u}）-f（S）≥f（T∪{u}）-f（T）。子模性反映了元素u在集合S基礎(chǔ)上的增量效應(yīng)隨著S的增大而遞減，這就是在經(jīng)濟學中經(jīng)常用到的邊界效用遞減現(xiàn)象。很多圖覆蓋問題都具有子模性，因為覆蓋的重疊現(xiàn)象會造成邊界效用遞減。重要的是，影響力延展度作為種子集合的函數(shù)σ(S)已被證明在獨立級聯(lián)和線性閾值模型以及它們的很多擴展模型下都滿足子模性[11]。

和子模性經(jīng)常在一起使用（但非絕對必要）的還有集合函數(shù)的單調(diào)性，稱集合函數(shù)f滿足單調(diào)性，對于任意一個子集和它的任意一個超集f滿足f（S）≤f（T）。影響力延展度函數(shù)σ(S)同樣具有單調(diào)性。

一個單調(diào)子模函數(shù)的重要性質(zhì)是可以用如下的貪心算法得到函數(shù)最大值的近似解。

算法：單調(diào)子模函數(shù)的貪心算法。

輸入：單調(diào)子模函數(shù)f，預算k。

輸出：大小為k的子集S。

初始化：S=φ

返回S

貪心算法分k輪，每一輪都要找到一個元素，使得它對已找到的元素來說邊界增量最大。如果f是單調(diào)子模的，且f（φ）=0，則貪心算法找到的貪心解保證至少是最優(yōu)解的（1-1/e），即大約63%[25]。所以貪心算法是單調(diào)子模函數(shù)最大化的（1-1/e）的近似算法。

由于影響力延展度函數(shù)σ(S)在獨立級聯(lián)和線性閾值模型下都具有單調(diào)性和子模性，且顯然σ(φ)=0，所以可以用貪心算法來解決影響力最大化問題，以達到的（1-1/e）近似比。

3.3 可擴展的影響力最大化算法

然而，第3.2節(jié)給出的單調(diào)子模函數(shù)的貪心算法并未完全解決影響力最大化問題，因為其中的關(guān)鍵一步需要計算一個種子集合S的延展度σ(S)，而計算σ(S)的精確值本身在獨立級聯(lián)和線性閾值模型下都是很難的問題（技術(shù)上稱為NP難問題[26,27]）。在Kempe等人的論文中[11]，簡單地提出用隨機模擬的方法（通稱蒙特卡洛方法）來模擬影響力傳播，從而估算σ(S)的近似解。在這種近似解情況下，貪心算法的解能達到的（1-1/e-ε）近似解，其中ε是一個大于零的數(shù)，對應(yīng)σ(S)估算的精確性。

但是簡單地在影響力最大化中用蒙特卡洛方法有一個嚴重的問題，就是時間效率很低。在一個不算大的上萬個節(jié)點的圖中，如果對每一次延展度估計都用并不算多的2 000次蒙特卡洛模擬，找出50個種子節(jié)點的貪心算法要運行好幾天[9]。為了解決這個效率問題，諸多研究提出了各種可擴展的影響力最大化（scalable influence maximization）算法。這些算法基本可分為兩大類，一類是利用模型具體特點的啟發(fā)式算法[26～30]，另一類是改進蒙特卡洛方法的貪心近似算法[31～35]。

在啟發(fā)式算法中，PMIA是一個有代表性的針對獨立級聯(lián)模型的算法[26]。PMIA的主要思想是將在一般圖上針對某一節(jié)點影響力的傳播轉(zhuǎn)化為在該節(jié)點附近區(qū)域的一棵有代表性的最大影響力傳播子樹上的傳播。這樣做的好處是：獨立級聯(lián)模型的影響力延展度計算在樹結(jié)構(gòu)上可在線性時間內(nèi)完成；構(gòu)造以某一節(jié)點為中心的最大影響力子樹（maximum influence arborescence）可以用Dijkstra最短路徑算法在近線性時間完成；只考慮節(jié)點附近的子樹會大大減少計算量，同時又不會損失太多計算精度，因為影響力在幾步傳播后已變?nèi)醯娇梢院雎圆挥?。PMIA和當時已做過優(yōu)化的蒙特卡洛貪心算法相比，速度提高了1 000倍，而選出種子的影響力在很多實際網(wǎng)絡(luò)的模擬實驗中都很接近貪心算法。之后，又有不少工作對算法做了進一步改進和提高，比如IRIE算法利用圖上整體迭代方法提高了算法速度，同時節(jié)省了內(nèi)存使用[30]。針對線性閾值模型也有LDAG算法[27]和SIMPATH算法[29]。這些算法的優(yōu)點是速度很快，通常效果也很好，但它們?nèi)狈碚摫ＷC，所以究竟它在哪些實際網(wǎng)絡(luò)中適用，還有待進一步論證。

在對蒙特卡洛貪心算法的改進方面，一種改進是依據(jù)延展度函數(shù)的子模性利用偷懶估值方法（lazy evaluation）減少對函數(shù)估值的次數(shù)，如CELF算法[32]。單純用這種方法雖然對最原始的蒙特卡洛方法有上百倍的提高（運行時間從幾天降低到幾個小時），但與高效的啟發(fā)式算法相比還有上千倍的差別（幾小時和幾秒鐘的差別）。最近，由Borgs等人率先提出的反向蒙特卡洛算法改變了這種局面[31]。反向蒙特卡洛算法的核心思想是不從種子節(jié)點去模擬估算種子節(jié)點的影響力，而是隨機選取圖上節(jié)點，從該節(jié)點出發(fā)以所有邊的相反方向進行蒙特卡洛模擬，得到的集合實際上是最可能影響該節(jié)點的集合。這樣的集合被稱作反向可達集合（reserve reachable set），簡稱RR集合。而如果一個節(jié)點經(jīng)常在RR集合中出現(xiàn)，那么該節(jié)點就是一個影響力大的節(jié)點?；谶@種思想，Borgs等人理論上證明了他們的算法可達到近乎最優(yōu)的近線性時間，同時仍有（1-1/e-ε）的近似比保證。之后Tang等人對他們的算法加以改進，提出了TIM/ TIM+和IMM算法[33,34]，并進行了模擬實驗驗證，最新的IMM算法在實驗中已超越了啟發(fā)式算法（如IRIE、SIMPATH）的速度，同時仍有一定的理論保證（ε=0.5，所以理論保證較弱，但對任意圖適用）。同時他們指出這種方法適用于獨立級聯(lián)、線性閾值和更廣的觸發(fā)模型。但基于RR集合的這些算法有一個問題是，當選出k個種子節(jié)點時，算法并不保證也同時找到所有小于k個種子集合的近似解。Cohen等人提出的SKIM算法避免了這個問題[35]：SKIM算法通過刻畫節(jié)點在隨機意義下的可達性草圖（reachability sketches）來高效計算節(jié)點影響力和選擇種子節(jié)點。理論上，SKIM算法不保證近線性時間但有近似比保證；實驗上，它與TIM/TIM+相當。

3.4 其他基于影響力的優(yōu)化問題

基于影響力傳播還可以提出很多的優(yōu)化問題或?qū)δＰ偷耐卣?。這仍然是現(xiàn)在學術(shù)界十分活躍的領(lǐng)域。下面簡要介紹一下這方面的幾個問題和相關(guān)研究。

（1）種子集合最小化

種子集合最小化是影響力最大化的對偶問題。它要求影響力延展度達到一定數(shù)值情況下選取的種子集合盡量小。這個問題的解法也是基于單調(diào)子模函數(shù)的貪心算法，但由于優(yōu)化目標變?yōu)樽钚』N子集合的大小，近似比變?yōu)榱薕（lnη），其中η是影響力延展度要求達到的閾值[36,37]。

（2）利潤最大化

利潤最大化考慮到選取種子有成本，而被影響的非種子節(jié)點才會產(chǎn)生收益。所以，利潤最大化的目標是選取合適的種子節(jié)點（不再受硬性的個數(shù)限制），使得最終的期望收益減去種子成本最大。與影響力最大化相比，利潤最大化的一個重要區(qū)別是它的目標函數(shù)（即給定種子集合下的期望利潤）不再是單調(diào)的。因為當種子集合達到一定程度時，再加一個節(jié)點作為種子帶來的額外期望收益可能已經(jīng)不能抵消加入這個種子的費用，但是利潤函數(shù)仍具有子模性，在這種情況下，利潤最大化要利用非單調(diào)子模函數(shù)的優(yōu)化技術(shù)[38]。

（3）影響力傳播監(jiān)控

影響力傳播可能達到網(wǎng)絡(luò)的各個角落，如何布置有效的監(jiān)控節(jié)點對各種影響力傳播提供及時、準確的報告，也是一個重要課題。在技術(shù)層面，選擇有效的網(wǎng)絡(luò)監(jiān)控節(jié)點和選擇有效的種子節(jié)點有相似性，在適當?shù)哪Ｐ秃蛦栴}描述下都具有單調(diào)性和子模性，所以都可以用貪心算法來解決[32]。

（4）多實體傳播模型下的影響力最大化

多實體的傳播會給影響力優(yōu)化帶來很多變種。比如在已知一個競爭實體分布的種子節(jié)點情況下，如何選取我方的種子節(jié)點從而最大化我方的影響力[9]或者盡量減少對方的影響力，也稱為影響力阻斷最大化（influence blocking maximization）[20,22]。影響力阻斷最大化可以應(yīng)用在抵御謠言的傳播。也有學者研究社交網(wǎng)絡(luò)平臺在有多個競爭實體下如何公平分配種子資源的問題[23]。Lu等人在他們最新的研究中還考慮了在互補性實體間的影響力最大化問題[24]，比如在已知一個互補實體的種子節(jié)點情況下，如何選取本方實體的種子節(jié)點以最大化本方的影響力（即自我影響力最大化（self influence maximization））或者最大化互補的對方的影響力（即互補影響力最大化（complementary influence maximization））?？梢钥闯?，多實體傳播下的影響力最大化種類繁多，具體應(yīng)用要具體分析。絕大多數(shù)問題仍然基于子模函數(shù)的最大化，但是多實體模型在不少情況下不再具備子模性，所以需要尋找新的解決途徑。

（5）網(wǎng)絡(luò)拓撲的優(yōu)化

影響力傳播研究中，也有研究如何有效地改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)來優(yōu)化影響力的。比如如何有效刪除圖中的邊或節(jié)點使得種子節(jié)點的影響力盡量小，這對應(yīng)了防止傳染病傳播中的隔離和免疫措施。也可以考慮如何增加點或邊以最大化影響力，這在一定程度上對應(yīng)了社交網(wǎng)絡(luò)平臺朋友推薦的情形。Khalil等人針對一種拓撲變化下定義的目標函數(shù)，論證了它的子模性或?qū)ΨQ的超模性（supermodularity），從而用子?；虺：瘮?shù)的優(yōu)化技術(shù)進行處理[39]。值得一提的是，他們定義的一個集合的影響力并不是集合整體的影響力延展度，而是集合中每個個體的影響力延展度的算術(shù)平均。這個定義使得他們能夠得到對應(yīng)的子?；虺Ｐ越Y(jié)論，但這樣的模型只適用于單一種子從種子集合中隨機選取的情形。

（6）非子模性的影響力優(yōu)化問題

當對影響力傳播模型進行一定擴展或?qū)?yōu)化目標進行一定改變后，新的模型或問題經(jīng)常就不再具有子模性（或超模性）。在最近的研究中對非子模性的影響力優(yōu)化問題也提出了一些解決方法，比如利用整數(shù)規(guī)劃[40]，將其轉(zhuǎn)化為相近的子模問題[41]，假設(shè)圖的一部分對應(yīng)的帶權(quán)重的鄰接矩陣有常數(shù)秩[42]，將非子模函數(shù)夾于兩個子模函數(shù)之間的三明治方法[24]或者利用基于傳播模型的啟發(fā)式算法[43]。這些方法對某些具體問題有較好的效果，但非子模性的影響力優(yōu)化問題的系統(tǒng)性研究還有待完善。

影響力傳播中還有很多其他相關(guān)問題和相關(guān)算法，受篇幅限制，本文不能面面俱到。

4 社會影響力傳播學習

前面介紹了影響力傳播模型和其上的影響力優(yōu)化問題。要使影響力傳播研究在實際中發(fā)揮更大的作用，基于實際數(shù)據(jù)的影響力學習（influence learning）也是必不可少的一個方面?；趯嶋H數(shù)據(jù)的網(wǎng)絡(luò)影響力分析在國內(nèi)外社交媒體網(wǎng)站也都有出現(xiàn)，比如國外的Klout.com、國內(nèi)的新浪微博影響力排名等。這些影響力分析側(cè)重對名人的排名，分析方法大多利用網(wǎng)絡(luò)拓撲結(jié)構(gòu)（如粉絲數(shù)、PageRank）、用戶活躍度等。而基于影響力傳播的學習是希望從數(shù)據(jù)中挖掘用戶行為的傳播方式和對應(yīng)的參數(shù)，從而為影響力傳播建模和優(yōu)化服務(wù)。

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

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

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

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

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

4.2 最大似然估計

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

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

4.3 信用分配和頻度分析

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

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

5 影響力傳播研究和應(yīng)用的問題、挑戰(zhàn)和方向

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

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

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

另外，絕大多數(shù)影響力傳播研究都是在靜態(tài)網(wǎng)絡(luò)中進行，而實際網(wǎng)絡(luò)都是動態(tài)變化的。如何將傳播的動態(tài)性和網(wǎng)絡(luò)的動態(tài)性合理結(jié)合，以達到有效的分析、建模和優(yōu)化，也是一個需要更多關(guān)注的課題。

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

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

6 結(jié)束語

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

[1] Bass F M. A new product growth for model consumer 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. A 61-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] 吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析. 中國計算機學報, 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 network value of customers. Proceedings of the 7th ACM SIGKDD International Conference on 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 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Washington DC, USA, 2003: 137～146

[12] Chen W, Lu W, Zhang N. Timecritical 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 the weakness 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 the spread 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 friend and foe relationships. Proceedings of the 6th ACM International Conference on Web 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 WideWeb (WWW), Hyderabad, India, 2011: 665～674

[21] Chen W, Collins A, Cummings R,et al. Influence maximization in social networks when negative opinions may emerge and propagate. 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 for the buck: fair competitive viral marketing from the host perspective. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Chicago, USA, 2013: 928～936

[24] Lu W, Chen W, Lakshmanan L V S. From competition 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 maximization in 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 and robust 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 ACMSIAM 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 maximization in 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 InternationalConference 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 for viral 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 seed set 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 DN, Hung HJ, Lee WC,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 Information and 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. Topicaware social 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. Contentcoverage maximization on word networks for hierarchical topic summarization. Proceedings of the 22nd ACM International Conference on Information and Knowledge Management(CIKM), San Francisco, USA, 2013: 249～258

Chen W. Research on influence diffusion in social network. Big Data Research, 2015031

Research on Influence Diffusion in Social Network

Chen Wei
Microsoft Research Asia, Beijing 100080, China

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.

social network, social influence, influence diffusion model, influence maximization, social influence learning, viral marketing

10.11959/j.issn.2096-0271.2015031

2015-08-26

國家自然科學基金重點項目（No.61433014）

Foundation Item:The National Natural Science Foundation of China (No.61433014)

陳衛(wèi). 社交網(wǎng)絡(luò)影響力傳播研究. 大數(shù)據(jù), 2015031

陳衛(wèi)，男，微軟亞洲研究院高級研究員，清華大學客座教授，中國科學院計算所客座研究員，多個國際頂級數(shù)據(jù)挖掘和數(shù)據(jù)管理會議（KDD、WSDM、SIGMOD、ICDE、WWW等）的程序委員會成員，中國計算機學會大數(shù)據(jù)專家委員會首批成員，《大數(shù)據(jù)》期刊編委。近期主要研究方向包括社交與信息網(wǎng)絡(luò)算法和數(shù)據(jù)挖掘、網(wǎng)絡(luò)博弈論和經(jīng)濟學、在線學習等。近幾年在社會影響力最大化方面的一系列開創(chuàng)性研究成果，在KDD、ICDM、SDM、WSDM、ICWSM、AAAI、VLDB等頂級數(shù)據(jù)挖掘、人工智能和數(shù)據(jù)庫學術(shù)會議上發(fā)表后得到良好反響，并引發(fā)這一方向眾多的后續(xù)工作。最早發(fā)表的KDD’2009論文被引用次數(shù)排同會議所有論文第二位，而第二篇KDD’2010論文被引用次數(shù)排同會議所有論文第一位。2013年與另外兩位合作者合寫了一部關(guān)于影響力傳播和最大化的專著（Information and Influence Propagation in Social Networks, Morgan & Claypool, 2013），系統(tǒng)總結(jié)了這方面的研究成果和最新發(fā)展。另外，在與社會和信息網(wǎng)絡(luò)相關(guān)的方向，如社區(qū)檢測、網(wǎng)絡(luò)中心化度量排序、網(wǎng)絡(luò)博弈、網(wǎng)絡(luò)定價、網(wǎng)絡(luò)激勵機制等方面也都做出開創(chuàng)性的工作，其中將博弈論引入網(wǎng)絡(luò)社區(qū)檢測的論文獲得了2010年歐洲機器學習及數(shù)據(jù)挖掘會議最佳學生論文獎。