新型影響力最大化算法

宋 偉，梁 霖，李 鋒

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

近幾年，隨著互聯(lián)網(wǎng)技術(shù)的進步，各種大型復(fù)雜社交網(wǎng)絡(luò)不斷出現(xiàn)。如何從復(fù)雜網(wǎng)絡(luò)中選取初始節(jié)點集來傳播信息，使得信息接受最大化已成為社會網(wǎng)絡(luò)領(lǐng)域研究的熱點。且在疾病傳播、產(chǎn)品推廣、社會穩(wěn)定、輿情擴散和故障控制等方面都有著十分重要的應(yīng)用。

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

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

文獻［4］指出不同的網(wǎng)絡(luò)拓撲結(jié)構(gòu)也會對傳播效率產(chǎn)生影響，并通過實驗證明在網(wǎng)人數(shù)和傳播路徑等因素均相同的條件下，clustered-lattice network比random network傳播效果更好。文獻［5］也通過數(shù)據(jù)分析發(fā)現(xiàn)同一個社團的朋友發(fā)出的邀請，影響力不如不同社團的朋友，同一社團中度大的朋友影響力更大。

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

1 相關(guān)工作

1.1 貪心算法

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

1.2 Maxdegree算法

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

2 基于社區(qū)的影響力最大化算法

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

2.1 劃分網(wǎng)絡(luò)階段

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

2.2 啟發(fā)階段

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

2.3 貪心階段

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

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

輸入:社會網(wǎng)絡(luò)圖G(V，E)，初始節(jié)點個數(shù)k。

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

1)讀取網(wǎng)絡(luò);

2)使用FHACC算法根據(jù)緊密矩陣將復(fù)雜網(wǎng)絡(luò)劃分為n個社區(qū);

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

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

sq中，使得最終sq的節(jié)點總數(shù)為k1，即ki=k1;

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

6)循環(huán)j=1到k2;

7)計算當(dāng)前所有未激活節(jié)點的邊際影響值;

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

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

11)結(jié)束循環(huán)。

3 實驗和評估

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

圖1 社區(qū)劃分圖

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

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

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

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

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

表1 算法時間復(fù)雜度比較

可見，本文提出的算法在時間復(fù)雜度上也明顯優(yōu)于KK算法。

4 總結(jié)

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

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

:

［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，F(xiàn)rance: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］姜秀芳.面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究［D］.西安:西安電子科技大學(xué)，2011:25-34.