新型影響力最大化算法

宋 偉，梁 霖，李 鋒

(1.南京郵電大學通信與信息工程學院，江蘇南京210003;2.華為技術有限公司，北京100094)

近幾年，隨著互聯網技術的進步，各種大型復雜社交網絡不斷出現。如何從復雜網絡中選取初始節點集來傳播信息，使得信息接受最大化已成為社會網絡領域研究的熱點。且在疾病傳播、產品推廣、社會穩定、輿情擴散和故障控制等方面都有著十分重要的應用。

針對影響力最大化問題，很多研究者針對某一具體的網絡結構提出了不同的算法，如貪心算法、Maxdegree算法等。目前，大部分研究認為，具有越多鏈接的節點影響力越大［1］，位于網絡越核心位置的節點，在傳播過程中所起的作用越大［2］。

對此，文獻［3］提出了不同的看法并通過調查分析指出對于單個傳播源而言，度最大的節點并不一定是最具影響力的節點，通過K-shell分解得到的K-shell值最大的節點才是最有影響力的節點。而對于多個傳播源網絡，度大的節點往往比K-shell值大的節點具有更好的傳播效果。因為K-shell值大的節點往往都聚集在網絡核心部位，傳播過程中存在交叉感染現象，出現較大允余。

文獻［4］指出不同的網絡拓撲結構也會對傳播效率產生影響，并通過實驗證明在網人數和傳播路徑等因素均相同的條件下，clustered-lattice network比random network傳播效果更好。文獻［5］也通過數據分析發現同一個社團的朋友發出的邀請，影響力不如不同社團的朋友，同一社團中度大的朋友影響力更大。

在此背景下，本文基于線性閾值模型(LT)提出了新的初始節點選擇算法——基于社區的影響力最大化算法，利用LT模型的影響力累積特性，以擴大最終的影響范圍為目的，兼顧時間復雜度來研究社會網絡中的影響力最大化問題。

1 相關工作

1.1 貪心算法

Kempe和Kleinberg等人曾在2003年提出使用貪心算法來求解影響力最大化問題，以下簡稱KK算法。KK算法的基本思想是:設最初的初始節點集合S=?，將k個初始節點的選擇過程分為k步，每一步都選擇當前網絡中邊際影響值最大的節點加入集合S，以得到局部最優解，直到|S|=k，即為最有影響力的初始節點集合S。該算法雖然能保證至少得到最優解的63%［6］，但是由于每一步初始節點的選擇，都要重新計算網絡中所有未激活節點的邊際影響值，所以時間復雜度相當高，這對于擁有成千上萬個節點的大型網絡來說并不適用。

1.2 Maxdegree算法

Maxdegree算法是經典的啟發式節點重要性排序方法，它將網絡中的節點按度值大小進行排序，選取鄰邊數目最大的k個節點作為初始節點［7］。該算法認為節點的度值越大，網絡中與其相連的節點越多，則該節點在網絡中的影響力越大。以度作為節點的重要性指標進行排序，它的優點是對于任意節點數量的網絡而言，時間復雜度均很低，僅為O(E+NlbN)，其中E為網絡中的鄰邊數量，N為節點總數。但該算法也有其明顯的缺點:在選取初始節點時，最具影響力的節點，其鄰居節點可能有較多的重合，冗余度增加，不利于信息更有效地傳播擴散;有些位于網絡中不同位置(核心和邊緣)的節點雖然度值相同，但其重要程度不同，所以單靠度來排序并不科學。

2 基于社區的影響力最大化算法

由于KK算法的時間復雜度很高，并不適用于大型的復雜網絡;Maxdegree算法雖然時間復雜度很低，但沒有考慮網絡結構的問題。現實的復雜網絡通常含有大量節點，節點與節點之間有著緊密的聯系，所以將網絡劃分為若干社區對于研究復雜網絡中的信息傳播具有重要意義。基于此，提出了一種新型的混合式影響力最大化算法——基于社區的影響力最大化算法。該算法利用LT模型的影響力累積特性，綜合考慮了KK算法和Maxdegree算法的優劣，將復雜網絡中初始節點的選擇過程劃分為以下3個階段。

2.1 劃分網絡階段

該階段利用復雜網絡的社區性，使用社區發現算法將社交網絡劃分為若干個社區。國內社區發現算法研究者姜秀芳等人曾提出一種基于社區緊密度的快速發現算法(FHACC)來劃分網絡［8］。該算法使用緊密度矩陣來表示各節點之間的緊密程度(每個社區抽象為一個節點)，節點之間共有的鄰居節點數目越多，緊密值越大，根據得到的緊密矩陣，將緊密值最大的節點進行合并，不斷迭代，直到迭代后社區的個數和各社區內的節點不再變化，迭代終止。該算法的時間復雜度很低，僅為O(mk+mt)，其中m為網絡中連邊的總數，k為所有節點的平均度值，t為迭代次數。用該方法將復雜網絡劃分為多個社區，有以下幾點好處:1)劃分出的各社區內部，節點的緊密程度、相似度增加，使信息更容易在社區內部傳播;2)啟發階段初始節點的選擇分散在各社區中，有效避免了節點選擇過于集中問題，提高了信息大范圍傳播的可能性和傳播速度。

2.2 啟發階段

劃分社區后，根據每個社區的節點數占全網絡節點總數的比值，在各社區內部按度值大小選取相應數目的初始節點，共計「ck?個。如復雜網絡中的節點總數為2 000，啟發階段共需選取12個初始節點，劃分為2個社區后，社區1和社區2的節點數分別為1 503和497，則社區1和2選取的初始節點個數為9，3(「(1503/2000)×12?=9)。各社區內初始節點的選擇按度值排序主要因為:劃分社區后的復雜網絡，社區內部節點的緊密值增加，此時，度越大的節點在社區中重要性越大，對鄰居節點的影響程度也越大;其次，初始階段的復雜網絡含有大量未激活節點，使用時間復雜度較低的Maxdegree算法更有利于信息高效地傳播與擴散。

2.3 貪心階段

經過劃分社區和啟發階段之后，網絡中未激活節點的數目大大減少，使用貪心算法從整個網絡剩下的未激活節點中選擇最具影響力的k－|ck|個節點加入初始節點集，不僅可以讓“累積”大量影響力的未激活節點一觸即發，更擴大了傳播的影響范圍。設啟發階段初始節點集合為sq，貪心階段初始節點集合為sg，則s=sq∪sg就是復雜網絡中影響力最大的初始節點集合。

基于社區的影響力最大化算法框架的偽代碼如下:

輸入:社會網絡圖G(V，E)，初始節點個數k。

輸出:影響力最大的k個初始節點集合s和最終被影響的節點總數。

1)讀取網絡;

2)使用FHACC算法根據緊密矩陣將復雜網絡劃分為n個社區;

3)初始集合S=?，k1=，k2=k－;

4)根據各社區內節點數目，在第i個社區(i=1，…，n)選取ki個度值最大的節點加入啟發階段初始節點集合

sq中，使得最終sq的節點總數為k1，即ki=k1;

5)基于集合sq激活尚未激活的節點;

6)循環j=1到k2;

7)計算當前所有未激活節點的邊際影響值;

8)選擇邊際影響值最大的節點u;

10)基于集合si+k1激活尚未激活的節點;

11)結束循環。

3 實驗和評估

上文介紹了基于社區的影響力最大化算法的設計與框架。本節主要在美國大學足球聯盟的數據集上驗證該算法的有效性，并驗證該算法的傳播效果優于已提出的部分算法。Football數據集是2000年美國大學秋季常規賽的關系數據，節點代表球隊，邊代表球隊之間存在比賽關系。簡化后的網絡拓撲中共有115個頂點、613條邊，使用FHACC算法經歷5次迭代后，網絡被劃分為12個社區，劃分結果如圖1所示。

圖1 社區劃分圖

對不同的初始節點數目k和參數c進行實驗，模擬實驗次數為50次，實驗結果為50次結果取平均。實驗效果如圖2所示，橫坐標為初始節點的數目，縱坐標為最終被影響的節點總數。當初始節點總數一定時，c取值不同，最終的影響效果不同。c=1時，為Maxdegree算法，影響效果最差;c=0時，為KK算法，相比于其他的c值，傳播效果略差。由圖可知，當c=0．5時，本文提出的算法傳播效果最好，且隨著初始節點數量的增多，被影響的節點總數呈遞增趨勢。

圖2 變量c不同取值時傳播效果對比

其他的初始節點選擇算法，如隨機算法、Maxdegree算法、KK算法，在取不同總數的初始節點時，與本文提出的基于社區的影響力最大化算法相比，最終影響的節點范圍如圖3所示。

圖3 不同算法傳播效果對比

可知，基于社區的影響力最大化算法其傳播效果均優于之前提出的隨機選擇算法、Maxdegree算法、KK算法等，且隨著初始節點數量的增多，相比于其他算法，傳播效果越好。前面主要對算法的最終影響范圍做了比較分析，下面對算法的時間復雜度進行比較。比較結果如表1所示。

表1 算法時間復雜度比較

可見，本文提出的算法在時間復雜度上也明顯優于KK算法。

4 總結

基于線性閾值模型，本文綜合考慮了貪心算法和Maxdegree算法的優劣，指出信息在網絡傳播之前，可以根據節點之間的緊密程度和相似性將復雜網絡劃分為多個社區。并基于此提出了一種新型影響力最大化算法——基于社區的影響力最大化算法。將此算法在美國Football聯盟數據集上進行了驗證，實驗結果表明，該算法相對于未劃分社區的網絡來說，傳播速度和范圍明顯上升，時間復雜度較KK算法也有顯著改善。

雖然基于社區的影響力最大化算法在綜合考慮影響范圍和時間復雜度的基礎上較之前有較大提升，但仍然存在很多需要改進和提高的地方。比如劃分社區算法的改進;劃分社區之后啟發階段初始節點的選擇使用的是時間復雜度較低的Maxdegree算法，仍然會存在鄰居重疊的現象等。

:

［1］ PASTOR-SATORRAS R，VESPIGNANI A.Epidemic spreading in scale-free networks［J］.Phys.Rev.Lett.，2011，86(14):3200-3203.

［2］ CHEN Wei，WANG Yajun，YANG Siyu.Efficient influence maximization in social networks［C］//Proc.15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris，France:ACM Press，2009:199-208.

［3］ KITSAK M.Identifying influential spreaders in complex networks［J］.Nature，2010(7):1-36.

［4］ CENTOLA D.The spread of behavior in an online social network experiment［J］.Science，2010(325):56-78.

［5］ UGANDER J，BACKSTROM L.Structural diversity in social contagion［J］.Proceedings of the National Academy of Sciences，2012，109(16):5962-5966.

［6］ GOYAL A，LU W，LAKSHMANAN L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks［C］//Proc.20th International Conference Companion on World Wide Web.Hyderabad，India:［s.n.］，2011:47-48.

［7］ KEMPE D，KLEINBERG J，TARDOS E.Maximizing the spread of influence through a social network［C］//Proc.9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ［S.l.］:ACM Press，2003:137-146.

［8］姜秀芳.面向復雜網絡的社區發現算法研究［D］.西安:西安電子科技大學，2011:25-34.