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

陳 衛(wèi)

微軟亞洲研究院 北京 100080

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

陳 衛(wèi)

微軟亞洲研究院 北京 100080

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

社交網(wǎng)絡(luò)；社會(huì)影響力；影響力傳播模型；影響力最大化；社會(huì)影響力學(xué)習(xí)；病毒營(yíng)銷(xiāo)

1 引言

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

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

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

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

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

2 影響力傳播模型

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

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

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

影響力傳播模型用來(lái)刻畫(huà)影響力在社交網(wǎng)絡(luò)中的傳播模式，也即社交網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài)如何影響其相鄰節(jié)點(diǎn)的狀態(tài)，并造成某一狀態(tài)（通常指活躍狀態(tài)）在網(wǎng)絡(luò)中擴(kuò)散傳播。傳播模型分很多種類(lèi)，其中大多數(shù)以隨機(jī)模型（stochastic models）來(lái)描述，也有用博弈論模型（gametheoretic models）來(lái)描述的。本文著重描述隨機(jī)模型，因?yàn)樗苯拥胤从沉擞绊懥鞑ブ械牟淮_定性，也是當(dāng)前研究的主流。

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

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

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

2.1.1 獨(dú)立級(jí)聯(lián)模型

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

圖2 獨(dú)立級(jí)聯(lián)模型示意

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

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

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

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

2.1.2 線(xiàn)性閾值模型

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

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

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

2.1.3 獨(dú)立級(jí)聯(lián)和線(xiàn)性閾值模型的推廣

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

2.2 其他傳播模型

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

2.2.1 連續(xù)時(shí)間模型

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

2.2.2 傳染病模型

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

2.2.3 選舉模型

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

2.2.4 博弈論模型

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

2.2.5 多實(shí)體傳播模型

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

3 影響力最大化問(wèn)題

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

3.1 影響力最大化問(wèn)題的定義

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

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

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

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

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

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

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

算法：?jiǎn)握{(diào)子模函數(shù)的貪心算法。

輸入：?jiǎn)握{(diào)子模函數(shù)f，預(yù)算k。

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

初始化：S=φ

返回S

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

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

3.3 可擴(kuò)展的影響力最大化算法

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

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

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

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

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

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

（1）種子集合最小化

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

（2）利潤(rùn)最大化

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

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

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

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

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

（5）網(wǎng)絡(luò)拓?fù)涞膬?yōu)化

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

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

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

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

4 社會(huì)影響力傳播學(xué)習(xí)

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

4.1 影響力傳播學(xué)習(xí)的基本思想

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

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

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

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

4.2 最大似然估計(jì)

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

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

4.3 信用分配和頻度分析

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

本文將影響力傳播研究分為三大方面：影響力傳播模型、影響力傳播學(xué)習(xí)和影響力傳播優(yōu)化，并對(duì)3個(gè)方面的主要成果和近期進(jìn)展進(jìn)行了介紹。簡(jiǎn)而言之，影響力傳播研究通過(guò)建立人們行為的傳播模型，從實(shí)際數(shù)據(jù)中學(xué)習(xí)傳播模型及其參數(shù)和基于傳播模型的各種影響力優(yōu)化和控制技術(shù)，使大家對(duì)影響力的傳播機(jī)理和模式有了深入的了解，并將這種認(rèn)識(shí)和理解轉(zhuǎn)化為對(duì)傳播行為的預(yù)測(cè)、優(yōu)化和控制。本文也討論了當(dāng)前影響力傳播研究和應(yīng)用方面的問(wèn)題和挑戰(zhàn)，比如如何利用更大規(guī)模的數(shù)據(jù)來(lái)支持影響力傳播的研究、如何結(jié)合網(wǎng)絡(luò)的動(dòng)態(tài)性、如何在實(shí)際中檢驗(yàn)優(yōu)化結(jié)果等。隨著大數(shù)據(jù)研究和應(yīng)用的不斷深入和發(fā)展，影響力傳播的研究也會(huì)取得更加豐碩的成果，并在產(chǎn)業(yè)界和實(shí)際生活中得到廣泛的應(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] 吳信東, 李毅, 李磊. 在線(xiàn)社交網(wǎng)絡(luò)影響力分析. 中國(guó)計(jì)算機(jī)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目（No.61433014）

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

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

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