社會(huì)網(wǎng)絡(luò)中基于社群衰減的影響力最大化算法

孫子力 彭艦 仝博

摘 要：針對(duì)現(xiàn)有網(wǎng)絡(luò)傳播模型忽略了信息傳播過(guò)程中的信息衰減，傳統(tǒng)影響力最大化算法無(wú)法有效利用社群結(jié)構(gòu)提高影響力傳播范圍的問(wèn)題，提出一種基于社群結(jié)構(gòu)的影響力最大化算法——社群衰減的影響力最大化（IMID）算法（Influence Maximization On Internal Decay）。首先對(duì)整個(gè)社會(huì)網(wǎng)絡(luò)進(jìn)行社群結(jié)構(gòu)劃分，評(píng)估社群中節(jié)點(diǎn)影響力范圍，并考慮社群之間關(guān)聯(lián)點(diǎn)之間的關(guān)聯(lián)概率，在信息傳播過(guò)程中增加節(jié)點(diǎn)之間信息傳播衰減度計(jì)算。通過(guò)實(shí)驗(yàn)與分析，該算法不僅降低了時(shí)間復(fù)雜度，還獲得了接近貪心算法的影響力傳播范圍，影響覆蓋率達(dá)到90%以上。因此，在核心種子節(jié)點(diǎn)集和連接社群之間紐帶節(jié)點(diǎn)選取若干節(jié)點(diǎn)作為初始節(jié)點(diǎn)，會(huì)讓信息以最小的代價(jià)在網(wǎng)絡(luò)中獲得廣泛傳播。

關(guān)鍵詞：信息傳播;影響力最大化;社會(huì)網(wǎng)絡(luò);社群劃分

中圖分類(lèi)號(hào)： TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2019）03-0834-05

Abstract： The existing network transmissionspread model ignores the information attenuation in the process of information transmissionspread， and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence transmissionspread range. To solve these problems， an algorithm of Influence Maximization on Internal Decay （IMID） based on community structure was proposed. Firstly， the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated. Then， with spread probability of association points between the communities considered， the attenuation degree of information spread between nodes was calculated. Experimental and analysis results show that the proposed algorithm not only reduces the time complexity， but also obtains the influence transmission range near that of greedy algorithm， with influence coverage over 90%. Therefore， with several nodes selected as the initial nodes between the core seed node set and connected communities， information will be widely disseminatedspread in the network at the minimum cost.

Key words： information spread; influence maximization; social network; community division

0 引言

目前，移動(dòng)設(shè)備和互聯(lián)網(wǎng)的發(fā)展為信息傳播提供了巨大的便利，社群網(wǎng)絡(luò)的發(fā)展形成了一個(gè)又一個(gè)的社會(huì)網(wǎng)絡(luò)，如Facebook、Twitter以及國(guó)內(nèi)的微信朋友圈、微博、QQ等。從線(xiàn)上到線(xiàn)下，人們的決定也被不同的社會(huì)網(wǎng)絡(luò)所影響。社會(huì)網(wǎng)絡(luò)在信息的傳播擴(kuò)散過(guò)程中發(fā)揮了非常重要的作用。從大規(guī)模社群網(wǎng)絡(luò)中尋找k個(gè)節(jié)點(diǎn)使得某一事件傳播范圍最廣，這是傳統(tǒng)社群網(wǎng)絡(luò)所關(guān)心的問(wèn)題。但是社群網(wǎng)絡(luò)復(fù)雜多樣，除了傳統(tǒng)基于獨(dú)立節(jié)點(diǎn)的社群網(wǎng)絡(luò)意外，基于社群的社群網(wǎng)絡(luò)也越來(lái)越多，例如豆瓣興趣小組、微信朋友圈等。一個(gè)社群表現(xiàn)出來(lái)的特性是社群之間的聯(lián)系較少，但是社群內(nèi)部的聯(lián)系度較高。例如一個(gè)家庭在決定是否要第二個(gè)孩子的時(shí)候，受家庭內(nèi)部影響較大，而社群外部影響較小。因社群關(guān)系距離遠(yuǎn)近對(duì)一個(gè)群體性決定又產(chǎn)生不同影響，這說(shuō)明信息即使在社群內(nèi)部也是存在衰減的，節(jié)點(diǎn)層級(jí)增大，增加節(jié)點(diǎn)所帶來(lái)的信息增益也越來(lái)越小，因此，在社群網(wǎng)絡(luò)中研究衰減情況下影響力最大化問(wèn)題變得越來(lái)越重要。挖掘社會(huì)網(wǎng)絡(luò)的影響力關(guān)鍵節(jié)點(diǎn)，解決社群網(wǎng)絡(luò)的影響力最大化問(wèn)題、提高算法效率是一個(gè)值得研究的領(lǐng)域。

近些年，影響力最大化問(wèn)題得到工業(yè)界和學(xué)術(shù)界的廣泛研究與討論。Kempe等[1]將影響力最大化問(wèn)題定義為一個(gè)離散的優(yōu)化問(wèn)題，證明了影響力最大化是一個(gè)NP難的問(wèn)題，并提出了近似比為（1-1/e）的爬山貪心算法;但是時(shí)間復(fù)雜度較高，并不能解決現(xiàn)實(shí)情況下影響力最大化問(wèn)題。IMID算法通過(guò)社群劃分，縮小單一計(jì)算單元，提高時(shí)間復(fù)雜度。Leskovec等[2]利用次模函數(shù)減少在影響力傳播過(guò)程評(píng)估次數(shù)的CELF（Cost-Effective Lazy Forward）算法。Goyal等[3]受CELF影響提出了CELF++算法，CELF++算法將同時(shí)計(jì)算節(jié)點(diǎn)u相對(duì)于S∪{u}的邊際增益，而CELF則需要兩輪蒙特卡羅模擬，因此可以提高時(shí)間效率;但CELF++算法依舊要進(jìn)行多次蒙特卡洛模擬，因此無(wú)法高效處理大規(guī)模社群網(wǎng)絡(luò)情況。而IMID算法并沒(méi)有使用蒙特卡洛模擬，而是簡(jiǎn)化邊際影響力計(jì)算，從而提高影響力計(jì)算效率。Chen等[4]通過(guò)考慮已經(jīng)選擇的節(jié)點(diǎn)對(duì)當(dāng)前候選節(jié)點(diǎn)的影響提出了SD（SingleDegree）算法，SD算法對(duì)所有節(jié)點(diǎn)都基于度進(jìn)行排序，然后迭代選擇具有最大度數(shù)的節(jié)點(diǎn)并添加到種子集合S中。SD算法在影響力傳播方面有較好的表現(xiàn)，但是它并沒(méi)有考慮特定的信息傳播模型，所以對(duì)性能的提升非常有限。IMID算法引入社群衰減，通過(guò)社群衰減度對(duì)社會(huì)關(guān)系建模，更準(zhǔn)確描述不同類(lèi)型的社會(huì)關(guān)系對(duì)信息傳播的影響。Zhu等[5]通過(guò)研究有限的傳播距離和影響傳遞性提出了半規(guī)劃的算法，但是半規(guī)劃算法忽略社群結(jié)構(gòu)的影響。文獻(xiàn)[6]中結(jié)合時(shí)間連續(xù)馬爾可夫鏈與獨(dú)立級(jí)聯(lián)模型（Independent Cascade Model， ICM）進(jìn)行影響力最大化分析，考慮了影響最大化問(wèn)題的分布傳播問(wèn)題，考慮了時(shí)序?qū)π畔鞑サ挠绊?，但是沒(méi)有考慮網(wǎng)絡(luò)結(jié)構(gòu)邊界點(diǎn)的傳播概率。IMID算法在選擇初始節(jié)點(diǎn)的時(shí)候考慮核心種子節(jié)點(diǎn)和社群邊緣節(jié)點(diǎn)對(duì)局部影響力傳播的影響。文獻(xiàn)[7]中考慮了社區(qū)結(jié)構(gòu)，并通過(guò)組合熵的方法來(lái)將較小的社區(qū)合并為一個(gè)大的社區(qū)，網(wǎng)絡(luò)的切割讓邊際節(jié)點(diǎn)的影響力傳播計(jì)算效率低下，整個(gè)算法的時(shí)間復(fù)雜度非常高。IMID算法不僅降低時(shí)間復(fù)雜度，還獲得了貪心算法的傳播范圍。

本文利用斯坦福大學(xué)SNAP（Stanford Network Analysis Project）的公開(kāi)數(shù)據(jù)來(lái)進(jìn)行影響力計(jì)算，并獲取種子節(jié)點(diǎn)。通過(guò)將大規(guī)模社群網(wǎng)絡(luò)進(jìn)行社群聚合，并考慮傳播概率以及信息衰減，本文提出一個(gè)基于社群衰減的影響力最大化（Influence Maximization on Internal Decay， IMID）算法，實(shí)驗(yàn)結(jié)果相對(duì)于由文獻(xiàn)[8]提出的獨(dú)立路徑算法（Independent Path Algorithm， IPA），以及Degree和SD算法，受影響節(jié)點(diǎn)更多，信息傳播范圍更廣，并且時(shí)間復(fù)雜度更低。本文的主要工作有：1）分析在社群網(wǎng)絡(luò)中影響力傳播過(guò)程;2）針對(duì)社群內(nèi)部的信息衰減情況，建立UARM（User Attenuation Rating Mechanism）機(jī)制，并根據(jù)用戶(hù)衰減機(jī)制提出了新的傳播模型，分析了在衰減模型下，社群內(nèi)部的信息傳播過(guò)程;3）提出一種基于社群結(jié)構(gòu)的影響力最大化IMID（Influence Maximization on Internal Decay）算法，在群衰減的社群網(wǎng)絡(luò)中獲取種子節(jié)點(diǎn)。

IMID算法并沒(méi)有使用蒙特卡洛模擬，而是簡(jiǎn)化邊際影響力計(jì)算，從而提高影響力和計(jì)算效率。IMID算法引入社群衰減，通過(guò)社群衰減度對(duì)社會(huì)關(guān)系建模，更準(zhǔn)確描述不同類(lèi)型的社會(huì)關(guān)系對(duì)信息傳播的影響。IMID算法在選擇初始節(jié)點(diǎn)的時(shí)候考慮核心種子節(jié)點(diǎn)和社群邊緣節(jié)點(diǎn)對(duì)局部影響力傳播的影響。IMID算法不僅降低時(shí)間復(fù)雜度，還獲得了貪心算法的傳播范圍。

1 社群衰減信息傳播模型

在傳統(tǒng)社群網(wǎng)絡(luò)影響力最大化問(wèn)題中，獨(dú)立級(jí)聯(lián)模型和線(xiàn)性閾值模型使用較為廣泛，但是獨(dú)立級(jí)聯(lián)模型與線(xiàn)性閾值模型沒(méi)有考慮社群結(jié)構(gòu)和衰減度對(duì)信息傳播的影響，針對(duì)傳統(tǒng)影響力傳播模型的缺陷，本文提出社群衰減信息傳播模型并給出相關(guān)定義。

社群內(nèi)部?jī)?nèi)部節(jié)點(diǎn)集NCi對(duì)社群內(nèi)部影響較大。雖然邊界節(jié)點(diǎn)集Nbi對(duì)社群內(nèi)部影響較小，但它是社群之間的紐帶，對(duì)社群之間的影響力傳播影響較大。對(duì)于社群衰減模型，在候選節(jié)點(diǎn)集中選擇k個(gè)節(jié)點(diǎn)，經(jīng)過(guò)k個(gè)節(jié)點(diǎn)使得信息傳播范圍最大。

社群衰減模型是基于獨(dú)立級(jí)聯(lián)模型的改進(jìn)模型，相比于獨(dú)立級(jí)聯(lián)模型，社群衰減模型增加社群結(jié)構(gòu)，并調(diào)整社群內(nèi)部節(jié)點(diǎn)和邊界節(jié)點(diǎn)的選取比例。社群網(wǎng)絡(luò)之間連接稀疏，即邊界之間的聯(lián)系較少。如果忽略邊界點(diǎn)之間的聯(lián)系，信息在社群之間便無(wú)法傳播。在選取k個(gè)影響力種子節(jié)點(diǎn)時(shí)，k-k′個(gè)節(jié)點(diǎn)從邊界點(diǎn)集合Nb中獲取，k′個(gè)節(jié)點(diǎn)從社群內(nèi)部節(jié)點(diǎn)獲取。

對(duì)于一個(gè)給定的社會(huì)網(wǎng)絡(luò)，首先使用Louvain算法對(duì)整個(gè)大規(guī)模網(wǎng)絡(luò)進(jìn)行社群劃分，Louvain算法基于模塊化優(yōu)化，并已經(jīng)被證明在社群劃分方面有很好的性能表現(xiàn)。得到社群結(jié)構(gòu)以后，將整個(gè)信息傳播過(guò)程如圖1所示分為兩個(gè)階段：1）種子節(jié)點(diǎn)的擴(kuò)散;2）社群內(nèi)部的傳播。

1）種子節(jié)點(diǎn)的擴(kuò)散。

這一階段的目的是使信息在不同社群之間進(jìn)行傳播。初始的種子節(jié)點(diǎn)S向S的鄰居節(jié)點(diǎn)集N（S）傳播，由此產(chǎn)生第二階段點(diǎn)集N（S），N（S）可能分布在不同的社群內(nèi)部，種子節(jié)點(diǎn)的初始信息便傳遞到了不同社群內(nèi)部。對(duì)于第二階段節(jié)點(diǎn)集合中任意一一個(gè)節(jié)點(diǎn)v∈N（S），在種子擴(kuò)散階段被激活的概率為：

2）社群內(nèi)部的傳播。

在這個(gè)階段，影響力只會(huì)在社群內(nèi)部進(jìn)行傳播。社群內(nèi)部的影響力傳播彼此獨(dú)立并且互不干涉。

定義3 社群影響力。對(duì)于某個(gè)社群C′，初始時(shí)刻只能被種子節(jié)點(diǎn)S及其鄰近節(jié)點(diǎn)所影響，所以社群集合的影響力可以定義為：

單一社群的影響力是社群節(jié)點(diǎn)影響力的累加和。根據(jù)式（6）可以將社群內(nèi)部節(jié)點(diǎn)分為種子節(jié)點(diǎn)的子集和非種子節(jié)點(diǎn)子集。式（7）中|S∩C′|表示第一階段種子節(jié)點(diǎn)傳播過(guò)程中影響力數(shù)值大小，其中C′表示內(nèi)部節(jié)點(diǎn)集合，式（7）后半部分表示社群內(nèi)部傳播過(guò)程中影響力的提升，二者相加就可以得到社群的影響力大小。在獲取每一個(gè)單一社群的影響力之后就可以計(jì)算得到整個(gè)社群網(wǎng)絡(luò)的影響力傳播范圍。

2 基于社群衰減的影響力最大化算法

本文提出了一個(gè)基于社群衰減的影響力最大（Influence Maximization on Internal Decay， IMID）算法，根據(jù)社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社群劃分，然后獲得使影響力傳播范圍最大的種子節(jié)點(diǎn)集合，即：

IMID算法的核心思想是簡(jiǎn)化全局影響力計(jì)算，在計(jì)算社群節(jié)點(diǎn)邊際影響力的過(guò)程中，需要證明全局影響力的目標(biāo)函數(shù)是一個(gè)次模函數(shù)。定理1用以證明σ（S）是一個(gè)次模函數(shù)。

通過(guò)影響力功能函數(shù)的次模屬性和單調(diào)性，Kempe的爬山貪心算法確保了（1-1/e-ε）的近似比，σ（S）的近似估計(jì)可以替代時(shí)間復(fù)雜度較高的蒙特卡洛模擬，通過(guò)影響力最大化目標(biāo)函數(shù)的次模屬性可以獲得每個(gè)節(jié)點(diǎn)增加到種子節(jié)點(diǎn)時(shí)的邊際增益，進(jìn)而IMID算法偽代碼如下：

其中EIIA（G，S，u， ρ）用以計(jì)算d（v，u）<4時(shí)，新增一個(gè)節(jié)點(diǎn)的有效影響力增益。對(duì)于一個(gè)給定的社群網(wǎng)絡(luò)，IMID算法的貪心策略比傳統(tǒng)的貪心算法時(shí)間復(fù)雜度更低，因?yàn)镮MID算法沒(méi)有使用蒙特卡洛計(jì)算影響力變化。對(duì)于一個(gè)給定的節(jié)點(diǎn)u，嘗試計(jì)算節(jié)點(diǎn)u加入到種子節(jié)點(diǎn)以后影響力變化時(shí)，可以使用衰減模型中影響力動(dòng)態(tài)變化來(lái)計(jì)算影響力增益值。EIIA（Efficent Incremental Influence Algorithm）的偽代碼如下：

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)使用NETHEPT、DBLP兩個(gè)公開(kāi)數(shù)據(jù)集，其中包括用戶(hù)ID、社群劃分、邊集等信息。

NEHEPT和DBLP是有關(guān)學(xué)術(shù)論文領(lǐng)域作者之間聯(lián)系的數(shù)據(jù)集，如果作者i與作者j之間合作過(guò)一篇文章，那么這兩個(gè)節(jié)點(diǎn)之間就有一條無(wú)向邊。數(shù)據(jù)集中Nodes表示節(jié)點(diǎn)數(shù)碼，Edges表示邊的數(shù)量，Communities表示數(shù)據(jù)集中社群的數(shù)量。NETHEPT包含15200個(gè)節(jié)點(diǎn)，31300條邊，2200個(gè)社群結(jié)構(gòu)。DBLP包含317000個(gè)節(jié)點(diǎn)，1000000條邊，11900個(gè)社群結(jié)構(gòu)。Max_Degree代表了社群網(wǎng)絡(luò)中節(jié)點(diǎn)度的最大值，用以影響力傳播范圍的計(jì)算。Avg.Com.Size表示社群網(wǎng)絡(luò)中平均節(jié)點(diǎn)數(shù)目，用以表示社群規(guī)模。

3.2 對(duì)比算法

本文實(shí)驗(yàn)的對(duì)比算法主要使用IPA[8]、SingleDegree[4]、Degree[4]三個(gè)算法。IPA假設(shè)信息只在傳播概率大于某個(gè)閾值的傳播路徑上進(jìn)行傳播。SingleDegree算法屬于基于中心的啟發(fā)式算法，在算法的每次迭代過(guò)程中都會(huì)選擇度數(shù)最大的節(jié)點(diǎn)，然后將該節(jié)點(diǎn)加入到種子節(jié)點(diǎn)集合中。一旦節(jié)點(diǎn)被加入到種子集合中，該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都會(huì)被從候選節(jié)點(diǎn)集中刪除。Degree算法則是簡(jiǎn)單從候選節(jié)點(diǎn)集合中選取度數(shù)最大的節(jié)點(diǎn)。

3.3 實(shí)驗(yàn)運(yùn)行環(huán)境

本實(shí)驗(yàn)運(yùn)行環(huán)境如下：CPU為2.7GHz Intel Core i5，內(nèi)存為8GB 1600MHz DDR3，操作系統(tǒng)使用OS X。本文實(shí)驗(yàn)代碼主要使用C++完成。

3.4 實(shí)驗(yàn)步驟及結(jié)果分析

本文提出了IMID算法，本次實(shí)驗(yàn)主要采用Louvain算法對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)進(jìn)行社群劃分。Louvain算法基于多層優(yōu)化Modularity，它能夠刻畫(huà)發(fā)現(xiàn)社區(qū)的緊密程度，可以被當(dāng)作一個(gè)優(yōu)化函數(shù)，Modularity的定義如下：

Louvain將社群劃分為兩個(gè)階段。第一個(gè)階段：不斷地遍歷社群網(wǎng)絡(luò)中的節(jié)點(diǎn)，將單節(jié)點(diǎn)嘗試加入能夠使modularity達(dá)到最大的社群中，直到社群網(wǎng)絡(luò)中的節(jié)點(diǎn)都不再變化。第二個(gè)階段：處理第一階段的結(jié)果，將一個(gè)個(gè)小的社區(qū)歸并為一個(gè)超節(jié)點(diǎn)來(lái)重新構(gòu)造新的網(wǎng)絡(luò)，這時(shí)邊的權(quán)重為兩個(gè)節(jié)點(diǎn)內(nèi)所有原始節(jié)點(diǎn)的邊權(quán)重之和。迭代這兩個(gè)步驟直至算法穩(wěn)定。

在實(shí)驗(yàn)中，影響力傳播范圍顯示如果忽略社群之間的弱連接節(jié)點(diǎn)，將不能解決社群衰減模型下影響力最大化問(wèn)題。影響力度量問(wèn)題與影響力最大化問(wèn)題是不一樣的，為了說(shuō)明這個(gè)問(wèn)題，定義差異對(duì)比函數(shù)：

圖3的結(jié)果顯示IMID和Degree算法結(jié)果之間的差異隨著種子節(jié)點(diǎn)數(shù)目k增加呈現(xiàn)先增大后平穩(wěn)下降的趨勢(shì)。這說(shuō)明在種子節(jié)點(diǎn)數(shù)目比較少的時(shí)候，兩者之間的相似度較高。然而當(dāng)k的增大的時(shí)候Degree算法的前k個(gè)節(jié)點(diǎn)更加聚合，而IMID算法得到的k個(gè)節(jié)點(diǎn)則包含了社群之間的弱連接節(jié)點(diǎn)。當(dāng)k值持續(xù)增大時(shí)，未被檢測(cè)到的社群之間的連接點(diǎn)變少，差異性呈現(xiàn)平穩(wěn)下降趨勢(shì)。

如圖4所示，描述在NetHEPT下不同種子節(jié)點(diǎn)數(shù)目下影響力的傳播范圍。實(shí)驗(yàn)表明在種子節(jié)點(diǎn)數(shù)目較少時(shí)，整個(gè)網(wǎng)絡(luò)中不同算法的影響力傳播范圍差異較小。在種子節(jié)點(diǎn)數(shù)節(jié)點(diǎn)數(shù)超過(guò)25以后，IMID相對(duì)于SingleDegree和Degree的傳播范圍差距開(kāi)始變大;當(dāng)k=50的時(shí)候，IMID算法的傳播范圍比SingleDegree多了8.64%。

圖4是在數(shù)據(jù)集DBLP下，IMID算法與IPA、SingleDegre、Degree算法影響力傳播范圍差值的對(duì)比。當(dāng)k=50時(shí)，IMID算法的傳播范圍相對(duì)于SingleDegree算法提高了8.6%。

時(shí)間效率也是算法研究過(guò)程中非常重要的一個(gè)指標(biāo)。表2展示了幾個(gè)算法在不同數(shù)據(jù)集下的運(yùn)行時(shí)間。

IMID算法相對(duì)于影響力傳播范圍來(lái)說(shuō)效率非常高IMID算法比其他影響力最大化算法運(yùn)行效率更高，在k=50的時(shí)候，NETHEPT和DBLP上運(yùn)行時(shí)間都小于1s。DBLP有317000節(jié)點(diǎn)，相對(duì)于IPA提升明顯。IMID算法采用二段式傳播模型，考慮社群結(jié)構(gòu)對(duì)影響力傳播的提升。與傳統(tǒng)的影響力最大化算法相比，邊際節(jié)點(diǎn)計(jì)算與社群劃分可以提高模型算法的并行化程度，從而評(píng)估模型時(shí)間效率復(fù)雜度不高并且比較穩(wěn)定。

隨著種子節(jié)點(diǎn)數(shù)k越來(lái)越大，影響力傳播范圍的差別越來(lái)越大。當(dāng)k的數(shù)值達(dá)到50的時(shí)候，差別達(dá)到最大?；谥行牡膯l(fā)式算法雖然影響力傳播范圍較好，但是無(wú)法提供性能上的保證，在k值超過(guò)一定范圍的時(shí)候，影響傳播范圍的增速小于IMID算法，這也從側(cè)面說(shuō)明了社群結(jié)構(gòu)的分階段傳播可以提高影響力的傳播能力。

4 結(jié)語(yǔ)

為了解決社群網(wǎng)絡(luò)中考慮信息衰減情況下影響力最大化問(wèn)題，提出了一個(gè)基于社群衰減的信息傳播模型，將信息傳播分為兩個(gè)階段，簡(jiǎn)化影響力傳播的計(jì)算方法;并在單獨(dú)社群網(wǎng)絡(luò)中快速有效地尋找初始節(jié)點(diǎn)，使信息以最小代價(jià)在網(wǎng)絡(luò)中盡量傳播?；谏缛核p的IMID算法同時(shí)考慮到了邊界點(diǎn)的影響力傳播問(wèn)題，減小了因社群劃分而導(dǎo)致局部與整體的差異，通過(guò)并行處理挖掘每個(gè)社群內(nèi)部有影響力的節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果證明了IMID算法的有效性和算法效率。后續(xù)會(huì)繼續(xù)提高算法的效率和精度，并與基于地理位置的社群網(wǎng)絡(luò)結(jié)合，挖掘出最有影響力的k個(gè)用戶(hù)，為網(wǎng)絡(luò)信息傳播提供理論依據(jù)和實(shí)踐經(jīng)驗(yàn)。

參考文獻(xiàn) （References）

[1] KEMPE D， KLEINBERG J， TARDOS E. Maximizing the spread of influence through a social network [C]// KDD '03： Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 137-146.

[2] LESKOVEC J， KRAUSE A， GUESTRIN C， et al. Cost-effective outbreak detection in networks [C]// Proceedings of the 2007 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429.

[3] GOYAL A， LU W， LAKSHMANAN L V S. CELF++：optimizing the greedy algorithm for influence maximization in social networks [C]// Proceedings of the 2011 International Conference Companion on World Wide Web. New York： ACM， 2011：47-48.

[4] CHEN W， WANG Y， YANG S. Efficient influence maximization in social networks [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 199-208.

[5] ZHU T， WANG B， WU B， et al. Maximizing the spread of influence ranking in social networks [J]. Information Sciences， 2014， 278： 535-544.

[6] LAMBA H， NARAYANAM R. A novel and model independent approach for efficient influence maximization in social networks [C]// Proceedings of the 2013 International Conference on Web Information Systems Engineering， LNCS 8181. Berlin： Springer， 2013： 73-87.

[7] 郭浩，陸余良，王宇，等.基于信息傳播的微博用戶(hù)影響力度量[J].山東大學(xué)學(xué)報(bào)（理學(xué)版），2012， 47（5）：78-83.（GUO H， LU Y L， WANG Y， et al. Measuring user influence of a microblog based on information diffusion[J]. Journal of Shandong University （Natural Science）， 2012， 47（5）： 78-83.）

[8] WANG Y， CONG G， SONG G， et al. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks [C]// Proceedings of the 2010 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 1039-1048.

[9] YU H， KIM S K， KIM J. Scalable and parallelizable processing of influence maximization for large-scale social networks [C]// Proceedings of the 2013 IEEE International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 2013： 266-277.

[10] 吳凱，季新生，郭進(jìn)時(shí)，等.基于微博網(wǎng)絡(luò)的影響力最大化算法[J].計(jì)算機(jī)應(yīng)用，2013，33（8）：2091-2094.（WU K， JI X S， GUO J S， et al. Influence maximization algorithm for micro-blog network [J]. Journal of Computer Applications， 2013， 33（8）： 2091-2094.）

[11] FISCHETTI M， KAHR M， LEITNER M， et al. Least cost influence propagation in （social） networks [J]. Mathematical Programming， 2018， 170（1）： 293-325.

[12] 田家堂，王軼彤，馮小軍.一種新型的社會(huì)網(wǎng)絡(luò)影響最大化算法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1956-1965.（TIAN J T， WANG Y T， FENG X J. A new hybrid algorithm for influence maximization in social networks [J]. Chinese Journal of Computers， 2011， 34（10）： 1956-1965.）

[13] TONG G， WU W， TANG S， et al. Adaptive influence maximization in dynamic social networks [J]. IEEE/ACM Transactions on Networking， 2017， 25（1）： 112-125.

[14] LI Y， FAN J， WANG Y， et al. Influence maximization on social graphs： a survey [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（10）： 1852-1872.

[15] FISCHETTI M， KAHR M， LEITNER M， et al. Least cost influence propagation in （social） networks [J]. Mathematical Programming， 2018， 170（1）： 293-325.