孫子力 彭艦 仝博

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

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

中圖分類號： TP301.6

文獻標志碼：A

文章編號：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 引言

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

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

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

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

1 社群衰減信息傳播模型

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

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

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

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

1）種子節(jié)點的擴散。

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

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

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

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

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

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

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

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

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

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

3 實驗與分析

3.1 實驗數(shù)據(jù)

本文實驗使用NETHEPT、DBLP兩個公開數(shù)據(jù)集，其中包括用戶ID、社群劃分、邊集等信息。

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

3.2 對比算法

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

3.3 實驗運行環(huán)境

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

3.4 實驗步驟及結(jié)果分析

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻 （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] 郭浩，陸余良，王宇，等.基于信息傳播的微博用戶影響力度量[J].山東大學學報（理學版），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] 吳凱，季新生，郭進時，等.基于微博網(wǎng)絡(luò)的影響力最大化算法[J].計算機應用，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] 田家堂，王軼彤，馮小軍.一種新型的社會網(wǎng)絡(luò)影響最大化算法[J].計算機學報，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.