社會網絡中基于社群衰減的影響力最大化算法

孫子力 彭艦 仝博

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

關鍵詞：信息傳播;影響力最大化;社會網絡;社群劃分

中圖分類號： 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 引言

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

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

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

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

1 社群衰減信息傳播模型

在傳統社群網絡影響力最大化問題中，獨立級聯模型和線性閾值模型使用較為廣泛，但是獨立級聯模型與線性閾值模型沒有考慮社群結構和衰減度對信息傳播的影響，針對傳統影響力傳播模型的缺陷，本文提出社群衰減信息傳播模型并給出相關定義。

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

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

對于一個給定的社會網絡，首先使用Louvain算法對整個大規模網絡進行社群劃分，Louvain算法基于模塊化優化，并已經被證明在社群劃分方面有很好的性能表現。得到社群結構以后，將整個信息傳播過程如圖1所示分為兩個階段：1）種子節點的擴散;2）社群內部的傳播。

1）種子節點的擴散。

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

2）社群內部的傳播。

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

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

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

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

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

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

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

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

3 實驗與分析

3.1 實驗數據

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

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

3.2 對比算法

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

3.3 實驗運行環境

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

3.4 實驗步驟及結果分析

本文提出了IMID算法，本次實驗主要采用Louvain算法對大規模社會網絡進行社群劃分。Louvain算法基于多層優化Modularity，它能夠刻畫發現社區的緊密程度，可以被當作一個優化函數，Modularity的定義如下：

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

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

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

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

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

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

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

隨著種子節點數k越來越大，影響力傳播范圍的差別越來越大。當k的數值達到50的時候，差別達到最大。基于中心的啟發式算法雖然影響力傳播范圍較好，但是無法提供性能上的保證，在k值超過一定范圍的時候，影響傳播范圍的增速小于IMID算法，這也從側面說明了社群結構的分階段傳播可以提高影響力的傳播能力。

4 結語

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

參考文獻 （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] 吳凱，季新生，郭進時，等.基于微博網絡的影響力最大化算法[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] 田家堂，王軼彤，馮小軍.一種新型的社會網絡影響最大化算法[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.