王春佳

（西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都610039）

0 引言

在線社交網(wǎng)絡(luò)是一種社會(huì)個(gè)體之間用來(lái)分享生活、學(xué)習(xí)、經(jīng)驗(yàn)和觀點(diǎn)的工具和平臺(tái)。在線社交網(wǎng)絡(luò)又被稱(chēng)為社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)具有平民性、非專(zhuān)業(yè)性、無(wú)門(mén)檻性。社交網(wǎng)絡(luò)成為社會(huì)個(gè)體之間的信息傳播的一種新的方式。因此，在線社交網(wǎng)絡(luò)中的信息傳播在多個(gè)領(lǐng)域引起了廣泛研究，包括計(jì)算機(jī)科學(xué)、流行病研究等，并成為社交網(wǎng)絡(luò)分析中的一個(gè)重點(diǎn)研究問(wèn)題。

信息傳播最大化，又稱(chēng)影響最大化，是信息傳播研究領(lǐng)域中的一個(gè)研究?jī)?nèi)容，由于其具有的實(shí)際研究?jī)r(jià)值，近年來(lái)受到了廣泛關(guān)注。本文主要圍繞在線社交網(wǎng)絡(luò)（本文關(guān)注微博客類(lèi)，即Twitter、微博）中影響最大化問(wèn)題的相關(guān)研究工作展開(kāi)綜述，首先概述了社交網(wǎng)絡(luò)中的信息傳播并分析了其特點(diǎn)；其次，介紹了國(guó)內(nèi)外研究者對(duì)影響最大化問(wèn)題所做的各類(lèi)研究工作；最后，對(duì)這類(lèi)研究存在的問(wèn)題和未來(lái)的研究方向進(jìn)行了概述。

1 社交網(wǎng)絡(luò)上的信息傳播

1.1 信息傳播

信息傳播是個(gè)人、組織和團(tuán)體通過(guò)符號(hào)和媒介交流信息，向其他個(gè)人或團(tuán)體傳遞信息、觀念、態(tài)度或情意，以期發(fā)生相應(yīng)變化的活動(dòng)。在古時(shí)候，信息傳播使用的是飛鴿傳書(shū)、烽煙、風(fēng)箏、孔明燈、飛騎、煙花爆竹、派遣信使等。不論是采用的是哪種方式，信息的傳播都受到了地域和時(shí)間的限制。后來(lái)，由于科技的飛速發(fā)展，信息傳播的方式發(fā)生改變，出現(xiàn)電話、電報(bào)傳真、手機(jī)短信、電視等進(jìn)行信息傳播的媒介。這些現(xiàn)代信息傳播速度較快，但信息量小。隨著互聯(lián)網(wǎng)的興起，互聯(lián)網(wǎng)被稱(chēng)為繼報(bào)紙、廣播、電視三大傳統(tǒng)媒體之后的“第四媒體”?；诨ヂ?lián)網(wǎng)的網(wǎng)絡(luò)媒體集三大傳統(tǒng)媒體的諸多優(yōu)勢(shì)為一體，是跨媒體的數(shù)字化媒體?；ヂ?lián)網(wǎng)使信息傳播更快捷、更方便。信息傳播具有以下幾個(gè)方面的特點(diǎn)：第一，傳播表現(xiàn)為傳播者、傳播渠道（媒介）、接收者等一系列傳播要素之間的傳播關(guān)系；第二，傳播過(guò)程是信息傳遞和信息接收的過(guò)程，也是傳播者與接收者信息資源共享的過(guò)程；第三，傳播者與接收者、相關(guān)人群之間，由于信息的交流而相互影響、相互作用。

1.2 社交網(wǎng)絡(luò)中信息傳播的特點(diǎn)

微博客類(lèi)社交網(wǎng)絡(luò)中的信息傳播是通過(guò)用戶之間的發(fā)布行為進(jìn)行的。信息傳播過(guò)程的參與者為：信息發(fā)布者、信息內(nèi)容、信息接收者。

（1）信息發(fā)布者

原作者：信息原始內(nèi)容的編輯者和發(fā)布者。

分享者：對(duì)信息感興趣，添加內(nèi)容或不添加內(nèi)容進(jìn)行再次發(fā)布的信息接收者。

（2）信息內(nèi)容

信息原文：其中顯示內(nèi)容信息和原文作者。

加工信息：再次發(fā)布的信息接收者所編輯的內(nèi)容。

（3）信息接收者

能夠接收到傳播過(guò)程中的原作者或分享者發(fā)布的信息的社交網(wǎng)絡(luò)用戶。

信息的發(fā)布者和信息的接收者之間是存在單向的或雙向的關(guān)聯(lián)關(guān)系的?！靶畔l(fā)布者-（信息內(nèi)容）-信息接收者”為信息傳播過(guò)程的“元過(guò)程”。社交網(wǎng)絡(luò)中的信息傳播是由無(wú)數(shù)個(gè)這樣的“元過(guò)程”組成。

2 傳播模型

信息傳播最大化問(wèn)題，又被稱(chēng)為影響最大化問(wèn)題（Influence Maximization）。Domingos 和Richardson 是第一個(gè)研究影響最大化的人[1-2]。影響最大化問(wèn)題最早是由Kempe 和Kleinberg[3]描述為一個(gè)離散優(yōu)化算法問(wèn)題。它研究的對(duì)象是一個(gè)社交網(wǎng)絡(luò)圖，表示為有向圖或無(wú)向圖G=（V,E），其中V 表示G 中節(jié)點(diǎn)的集合（對(duì)應(yīng)社交網(wǎng)絡(luò)中的用戶），E 表示G 中邊的集合（對(duì)應(yīng)社交網(wǎng)絡(luò)中用戶之間的社交聯(lián)系）。影響最大化問(wèn)題旨在從G 中找到k 個(gè)用戶，這k 個(gè)用戶他們所能影響到的用戶范圍最大。由于影響最大化問(wèn)題中的用戶之間的影響是通過(guò)用戶間的信息傳播過(guò)程進(jìn)行定義和量化的，我們先回顧影響最大化問(wèn)題中所使用的幾類(lèi)常用的傳播模型。

2.1 獨(dú)立級(jí)聯(lián)模型（Independent Cascade Model，IC）

獨(dú)立級(jí)聯(lián)（IC）是經(jīng)典常用的且被許多研究者研究使用過(guò)的傳播模型[4]。在獨(dú)立了級(jí)聯(lián)模型中，一個(gè)社交網(wǎng)絡(luò)表示為圖G=( )V,E ，V 為節(jié)點(diǎn)集，E 為邊集，每條邊e( u → v )有一個(gè)概率puv，puv表示節(jié)點(diǎn)u 把其鄰居v 激活的概率。在傳播過(guò)程開(kāi)始的t0時(shí)間指定種子集S，這個(gè)傳播過(guò)程從種子集開(kāi)始以離散化的時(shí)間步驟進(jìn)行傳播。傳播過(guò)程以下述原則進(jìn)行。在時(shí)間t，每個(gè)激活狀態(tài)的節(jié)點(diǎn)u 都嘗試以成功概率puv去激活其指向的每個(gè)未激活鄰居v。在此過(guò)程中，每個(gè)激活節(jié)點(diǎn)只能?chē)L試激活其指向鄰居一次。也就是說(shuō)一旦這個(gè)節(jié)點(diǎn)嘗試過(guò)激活其指向鄰居，不論其鄰居是否被激活，之后的時(shí)間步驟中只是保持激活狀態(tài)而不進(jìn)行激活行為。直到?jīng)]有新節(jié)點(diǎn)再被激活，整個(gè)傳播過(guò)程就停止。

2.1 線性閾值模型（Linear Threshold Model，LT）

2.3 觸發(fā)模型（Triggering Model，TR）

Kempe 等人[3]提出了可概括IC 和LT 模型的觸發(fā)模型（TR）。觸發(fā)模型的主要思想在于：對(duì)于給定的節(jié)點(diǎn)v，分配觸發(fā)節(jié)點(diǎn)集Tv代替LT 中的閾值，即如果Tv中有節(jié)點(diǎn)在步驟t-1 被激活，則v 在步驟t 中被激活。與IC 和LT 模型一樣，觸發(fā)模型的整個(gè)傳播過(guò)程也是離散時(shí)間的。傳播過(guò)程描述如下：

（1）首先為網(wǎng)絡(luò)圖G 中的每個(gè)節(jié)點(diǎn)隨機(jī)選擇一個(gè)觸發(fā)節(jié)點(diǎn)集Tv，Tv是v 的所有鄰居的集合的一個(gè)子集，以及選擇一個(gè)已激活節(jié)點(diǎn)的集合作為初始的種子集；

（2）步驟t 中，對(duì)于還未被激活的節(jié)點(diǎn)v 而言，只要Tv中有一個(gè)節(jié)點(diǎn)u 在步驟t-1中被激活，則v 被激活；

（3）重復(fù)上個(gè)步驟，直到?jīng)]有新節(jié)點(diǎn)再能被激活，整個(gè)傳播過(guò)程結(jié)束。

2.4 其他模型

不論是IC 模型，還是LT 模型，亦或是TR 模型，都是以離散步驟進(jìn)行傳播的，即不再有新的節(jié)點(diǎn)被激活時(shí)停止。然而在實(shí)際情況中，傳播過(guò)程中節(jié)點(diǎn)之間的影響是與時(shí)間相關(guān)的。因此，有研究者針對(duì)這個(gè)問(wèn)題開(kāi)展了相關(guān)研究[7-8]?；贗C 模型的連續(xù)時(shí)間（Continuous-Time，CT）模型[7]認(rèn)為節(jié)點(diǎn)之間成對(duì)傳播的可能性是時(shí)間的連續(xù)分布。即節(jié)點(diǎn)u 的激活時(shí)間tu和其鄰居被u 所激活的時(shí)間tv滿足條件分布p( tv|tu;αu,v)，其中αu,v為參數(shù)。CT 模型預(yù)先會(huì)給定一個(gè)停止時(shí)間T>0，時(shí)間T 內(nèi)沒(méi)有新節(jié)點(diǎn)被激活，傳播過(guò)程停止。DynaDiffuse 模型[8]認(rèn)為節(jié)點(diǎn)的傳播速率隨時(shí)間呈指數(shù)下降趨勢(shì)。即給定節(jié)點(diǎn)u 的激活時(shí)間tu和u 激活v 的初始概率，則u 在時(shí)間tv>tu將v 激活的概率為。

又有研究者提出傳播過(guò)程中網(wǎng)絡(luò)結(jié)構(gòu)是可能發(fā)生變化的。Tong 等人[9]提出了動(dòng)態(tài)獨(dú)立級(jí)聯(lián)（Dynamic Independent Cascade，DIC）模型，該模型能夠追蹤真實(shí)的社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)。在DIC 模型中，種子節(jié)點(diǎn)可能以一定的概率無(wú)法被激活并且兩個(gè)用戶之間的傳播概率服從一個(gè)分布，由此來(lái)反映一個(gè)社會(huì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化。

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

3.1 基于貪心算法的算法

2003 年，Kempe 等人[3]從離散優(yōu)化的角度提出如何選擇有影響力的種子問(wèn)題，并證明了該問(wèn)題是NP 難問(wèn)題。同時(shí)證明了傳播影響函數(shù)的次模性并提出了一種近似比為1-1/e-ε 的貪心算法，其中ε 是與社交圖G 和r 相關(guān)的常數(shù)，r 是計(jì)算E[I（S）]估計(jì)值時(shí)的測(cè)量次數(shù)?；贗C 和LT，該算法從初始化S 為空集開(kāi)始，通過(guò)向種子集S 中并入使得傳播影響范圍的期望E[I（S）]增長(zhǎng)最大的節(jié)點(diǎn)，直到種子集S 中包含k 個(gè)節(jié)點(diǎn)，算法結(jié)束。

由于簡(jiǎn)單貪心算法的計(jì)算時(shí)間很長(zhǎng)，通過(guò)進(jìn)一步研究次模性質(zhì)，Leskovec 等人[10]提出了CELF 算法，該算法利用影響函數(shù)的子模屬性來(lái)計(jì)算影響擴(kuò)散。而后，經(jīng)過(guò)進(jìn)一步的研究，Goyal 等人[11]提出了CELF++算法優(yōu)化CELF，并提高了效率。UBLF[12]使用矩陣分析技術(shù)減少了CELF 的計(jì)算次數(shù)，并實(shí)現(xiàn)了2 倍到10 倍的加速。Lu 等人[13]提出了CascadeDiscount 算法，使用從ScoreCumulate 模型評(píng)估的初始影響中去除節(jié)點(diǎn)對(duì)鄰居的影響損失來(lái)估計(jì)節(jié)點(diǎn)的邊際收益從而達(dá)到減少計(jì)算時(shí)長(zhǎng)的目的。同樣的有好些研究工作[14-15]也對(duì)貪心算法進(jìn)行過(guò)改進(jìn)。雖然改進(jìn)的貪心算法在傳播概率較小的網(wǎng)絡(luò)中性能良好，但是當(dāng)網(wǎng)絡(luò)規(guī)模很大或傳播概率很大時(shí)，依然是高耗時(shí)。

3.2 基于啟發(fā)式的算法

最早Domingos 和Richardso[1-2]提出了影響最大化問(wèn)題：如何從社交圖中尋找t 個(gè)初始節(jié)點(diǎn)，使得信息的最終傳播范圍最廣，并提出選擇全局影響最大用戶的啟發(fā)式算法。啟發(fā)式算法避免傳播概率對(duì)算法運(yùn)行時(shí)間的影響。

2009 年，Chen 等人[16]提出了新的度折扣啟發(fā)式算法，該算法非常有效并且能夠產(chǎn)生良好的影響傳播，其時(shí)間復(fù)雜度為O（klogn+m）。在提出的方法中，最初將每個(gè)節(jié)點(diǎn)的度視為其影響力的指標(biāo)，并以k 步迭代選擇種子。每個(gè)迭代步驟中，將影響力最高的節(jié)點(diǎn)作為新成員添加到種子集中。如果將節(jié)點(diǎn)v 作為新成員添加到集合中，則其鄰居的影響力降低，并且隨后它們被選擇為種子的機(jī)會(huì)降低。還有一些研究工作[17-18]也是采用這樣的方式。

Bao 等人[19]提出了一種啟發(fā)式聚類(lèi)方法，首先確定每對(duì)節(jié)點(diǎn)之間的相似度，然后將節(jié)點(diǎn)聚類(lèi)為k 個(gè)不同的聚類(lèi)。然后，選擇每個(gè)群集中最具影響力的節(jié)點(diǎn)作為種子的成員。

Jiang 等人[20]提出了一種預(yù)期擴(kuò)散值（EDV）度量來(lái)近似估計(jì)潛在候選種子節(jié)點(diǎn)的影響，并采用模擬退火算法來(lái)優(yōu)化和識(shí)別有影響的節(jié)點(diǎn)。Gong 等人[21]改進(jìn)EDV，并使用粒子群優(yōu)化（PSO）算法最大化目標(biāo)函數(shù)。Cui 等人[22]提出了一種使用差分進(jìn)化算法最大化EDV函數(shù)找到種子集的方法。除了節(jié)點(diǎn)的影響外，還可以考慮將預(yù)算約束定義為IM 的優(yōu)化問(wèn)題[23-24]。

3.3 基于反向影響采樣的算法

2014 年，Borgs 等人[25]發(fā)現(xiàn)沒(méi)有必要對(duì)整個(gè)圖進(jìn)行計(jì)算而提出一種新的算法思想，即反向影響采樣（Reverse Influence Sampling）。根據(jù)RIS 的思想，如果一個(gè)節(jié)點(diǎn)經(jīng)常以“影響者”的身份出現(xiàn)，那么它可能是最有影響力的節(jié)點(diǎn)的良好候選者?；谠撍枷隑orgs等人[25]提出了一種基于閾值的方法（RIS）。該算法需要運(yùn)行O( ε-3· k·( n+m)·log2n )，并且以不小于1-1/n-1的概率得到近似比為1-1/e-ε 的近似解。

為了優(yōu)化生成的子圖的數(shù)量和采樣方案，研究者提出了許多改進(jìn)的方法來(lái)緩解基本RIS 算法的不足。Youze Tang 等人[26]提出了TIM 算法，通過(guò)使用組合可達(dá)性草圖來(lái)逐步選擇種子節(jié)點(diǎn)，其預(yù)期時(shí)間復(fù)雜度為O( ε-2· ( n+m)·log n )。此外通過(guò)改進(jìn)參數(shù)估計(jì)，提出了TIM+算法。TIM＋算法具有與TIM 相同的最壞情況下的時(shí)間復(fù)雜度，但表現(xiàn)出的經(jīng)驗(yàn)性能更好。進(jìn)一步地，唐等人提出IMM[27]來(lái)改進(jìn)TIM/TIM+，IMM 使用一組基于martingale 分析的估計(jì)技術(shù)，取得比TIM/TIM+更好的性能。

Nguyen 等人[28]提出了兩種命名為SSA 和D-SSA的新穎采樣框架用于IMM[27]方法的優(yōu)化。盡管基于采樣的算法可以在大規(guī)模網(wǎng)絡(luò)中有效地選擇k 個(gè)有影響力的種子節(jié)點(diǎn)，但是它們不可避免地會(huì)遭受巨大的存儲(chǔ)成本的問(wèn)題，因?yàn)楸仨毶纱罅康腞IS 樣本才能提供近似的保證，尤其是在大規(guī)模網(wǎng)絡(luò)中。為了減少內(nèi)存消耗，Wang 等人[29]提出一種惰性采樣技術(shù)（BKRIS），將IMM[25]速度提高了兩個(gè)數(shù)量級(jí)。

3.4 上下文感知影響最大化

近幾年來(lái)，一些研究工作不再聚焦如何從算法層面對(duì)影響最大化問(wèn)題進(jìn)行研究，而是開(kāi)始研究基于上下文感知的影響最大化問(wèn)題。這類(lèi)問(wèn)題對(duì)傳統(tǒng)的IM問(wèn)題進(jìn)行擴(kuò)展，進(jìn)一步考慮上下文特征，例如主題，時(shí)間和位置?；谥黝}的影響最大化問(wèn)題：這類(lèi)問(wèn)題需要考慮被傳播內(nèi)容中的主題信息。這類(lèi)研究問(wèn)題又可被細(xì)分為節(jié)點(diǎn)主題感知[30-31]和邊主題感知[32-33]，均有相關(guān)的研究工作開(kāi)展?；跁r(shí)間的影響最大化問(wèn)題：傳統(tǒng)IM 算法是在沒(méi)有新激活點(diǎn)的時(shí)候停止。在實(shí)際情況中，這樣的停止條件不合理。傳播過(guò)程是隨著時(shí)間逐漸變化的。因此，開(kāi)始有將時(shí)間因素納入傳播過(guò)程中的研究開(kāi)展。這類(lèi)問(wèn)題可被分為離散時(shí)間感知和連續(xù)時(shí)間感知。離散時(shí)間感知的研究工作[34-35]是將離散步驟作為時(shí)間度量，限制步驟長(zhǎng)度。連續(xù)時(shí)間感知的研究工作[36-37]認(rèn)為時(shí)間與傳播過(guò)程密切相關(guān)?；谖恢玫挠绊懽畲蠡瘑?wèn)題：隨著基于位置的社交網(wǎng)絡(luò)的普及，一些研究者[38-39]開(kāi)始研究基于位置的影響最大化問(wèn)題?；舅枷胧亲畲蠡繕?biāo)位置相關(guān)用戶的影響范圍。

4 結(jié)語(yǔ)

本文概述了影響最大化問(wèn)題使用的公認(rèn)傳播模型和幾種基本的算法。影響最大化問(wèn)題具有很大的現(xiàn)實(shí)應(yīng)用空間和某些方面的技術(shù)困難，成為研究熱點(diǎn)之一。同時(shí)由于這些現(xiàn)實(shí)應(yīng)用，解決影響最大化問(wèn)題（尤其是在大型網(wǎng)絡(luò)中）時(shí)，如何在合理的時(shí)間消耗甚至內(nèi)存成本之間很好地平衡求解精度就成為需要考慮的。因?yàn)樯缃痪W(wǎng)絡(luò)中的網(wǎng)絡(luò)結(jié)構(gòu)不是一成不變的，因而影響最大化解決方案的可擴(kuò)展性、魯棒性是一個(gè)難點(diǎn)。隨著越來(lái)越多的研究者投入研究，相信這些問(wèn)題都可以得到解決。