基于合并影響概率的社交網絡影響最大化算法

周 飛,高茂庭

(上海海事大學 信息工程學院,上海 201306)

0 概述

隨著互聯網技術的迅猛發展,社交網絡服務(Social Network Service,SNS)作為互聯網應用發展的必備要素,不再局限于信息傳遞,而是與溝通交流、商務交易類應用融合,借助其他應用的用戶基礎,形成更強大的關系鏈,從而實現對信息的廣泛、快速傳播。鑒于社交網絡影響力的傳播特性,信息在社交網絡傳播中具有“口碑效應”,即當某用戶接受一新鮮事物時,他通常會將該事物推薦給他的朋友,當他的朋友接受的時候就實現了信息的有效擴散。于是,在日常生產生活中決策者們便利用“口碑效應”在社交網絡中進行產品信息宣傳,實現影響最大化在網絡營銷、輿情監控等方面的實際應用。社交網絡的流行也為“病毒式營銷”提供了天然的營銷網絡,因此,如何從眾多網絡節點中尋找若干較少節點,使得影響力能夠最廣泛地擴散成為一個研究熱點。

已知社交網絡由M個節點和N條邊所組成的有向圖G(V,E)表示。社交網絡影響最大化問題(Influence Maximization Problem,IMP)由文獻[1]提出,IMP問題就是如何從M個節點中選取K個種子節點,讓這個K種子節點在初始時刻處于激活狀態,通過網絡傳播模型嘗試激活其他當前狀態是未激活的節點,最終使得被激活成功的節點數最多的問題。針對該問題,本文提出一種基于合并影響概率的社交網絡影響最大化算法。

1 相關研究

為了解決影響最大化問題,文獻[2]將影響最大化問題歸納為離散最優問題,并提出了近似可達最優解63%的爬山貪心算法,運用多次蒙特卡洛模擬獲得影響范圍,取最優解,但對于大規模社交網絡,這種貪心算法的時間復雜度太高。針對此問題,文獻[3]提出了改進的貪心算法CELF,利用網絡傳播的子模性,延遲計算邊際收益,將時間效率提高了數百倍。在此基礎上,文獻[4]利用堆特性對CELF 算法做出改進并提出了CELF++算法。文獻[5]提出NewGreedy算法,在獨立級聯傳播模型下,以1-p的概率去除原圖中的邊,再迭代考慮子圖的最大影響力。MixGreedy算法[5]結合NewGreedy算法和CELF算法,仿真實驗表明,其性能略好于NewGreedy。文獻[5]亦在Degree算法[6]的基礎上提出DegreeDiscount算法,性能也有所提升。網頁排名的PageRank算法[7]也被運用于尋找網絡影響力節點中。PMIA算法[8]提供了穩定的傳播范圍,且運行速度比貪心算法提升了大約3個數量級,但由于在本地計算節點樹結構,運行時需要耗費較大內存。文獻[9]提出CGA算法,采用分治思想,拆分數據集,對各個子集并行計算。文獻[10]在CELE的基礎上使用上界逼近法減小了算法響應時間。UGGreedy算法[11]在去除不重要節點簡化網絡結構后再使用貪心算法求解,但算法時間復雜度依然相對較高。文獻[12]提出k-核概念,并考慮節點間影響區域重疊現象提出核覆蓋CCA算法,認為影響重疊會使得影響力難以擴散,帶來的邊際受益很小。CCA算法優先選擇距離參數d內影響重疊較少的節點。然而,在獨立級聯的模型下,重疊部分的節點被影響次數要多于非重疊部分節點,因此,重疊部分節點相對被影響的概率更大,繼而可以影響到其他后續節點。文獻[13]結合網絡在線傳播和現實社會中口口相傳的特性建立模型,但也正因如此算法擴展性較差。BCIM算法,先使用PageRank選取備用節點,再使用動態規劃的方法獲取最優解,其不足之處是只考慮到近距離鄰居的影響,雖然在算法時間上有較大提高,但是會出現部分影響力在傳播過程中丟失的現象。

為了更好地解決影響最大化問題,且考慮到現有算法中存在貪心算法時間復雜度過高,節點間影響區域重疊,算法可擴展性以及在傳播過程中只考慮近距離傳播而犧牲影響力間接傳播來提高算法時間性能等問題。本文在第4節提出基于合并影響概率的社交網絡影響最大化算法(Influence Maximization with Combined Impact Probability,CIPIM),在沿用BCIM算法中先使用PageRank選取備用種子節點,再在計算備選種子節點合并影響概率的基礎上,使用遺傳算法(Genetic Algorithm,GA)解決全局優化問題。

2 傳播模型

尋找社交網絡影響最大化節點往往需要借助于網絡傳播模型,通常情況下將社交網絡表示為由M個節點和N條邊所組成的有向圖G(V,E),其中,節點表示社交網絡中的個體,有向邊表示個體之間的關系,如Twitter中用戶之間的關注關系。線性閾值模型(Linear Threshold Model)和獨立級聯模型(Independent Cascade Model,ICM)是2種常用的網絡傳播模型。

2.1 線性閾值模型

2.2 獨立級聯模型

在獨立級聯模型[15]中,任意一條邊∈E都有一個puv∈[0,1],表示節點u通過邊影響節點v的概率。該模型中,只有在當前節點被激活后才有一次機會去激活其鄰居節點。假設u在時間t被激活,那么在單步時間內,u可以嘗試去激活它的鄰居v。如果v被激活,那么v將在時間t+1變成激活狀態。時間t+1之后,u將不再嘗試激活其鄰居節點。當若干單步時間后,如果不存在激活可能性的時候,傳播過程結束。在簡單的獨立級聯模型中,通常將puv設置為常量,或是從{0.1,0.01,0.001}中隨機選取。獨立級聯模型更側重于影響力的傳播過程,在現實工作中應用更為廣泛,因此本文選用獨立級聯模型作為傳播模型。

3 影響最大化算法CIPIM

影響最大化問題就是要從M個節點中選取影響傳播影響范圍最大的K個種子節點。但在實際社交網絡中存在大量低影響力用戶,在信息傳播中幾乎沒有任何貢獻,因此,他們不能作為種子節點。從減少種子選取范圍上考慮,先使用PageRank算法計算M個節點的PageRank值,從中選取排名靠前的節點作為備選種子集合,再對各備選種子節點進行合并影響概率預計算,最后使用遺傳算法進行全局優化挑選出K個種子節點。

3.1 種子選取范圍的減少

意見領袖通常是網絡社區中的活躍分子,是信息的積極傳播者,能夠引起大量關注并影響社區中的輿論導向。在線社交網絡通常采用PageRank值來表示用戶的影響力大小,值越大則影響力越大。社交網絡中還存在著大量的信息接收者,但單純的接受者對信息傳播的貢獻卻非常小。為了分析選取高影響力用戶作為備用種子節點的占比規律,對Wiki-Vote數據集[16]7 115個節點按照PageRank值進行排序,歸一化處理各節點PageRank值并計算可影響范圍占比情況,考慮圖像顯示效果和方便觀察,截取前1 000個節點,如圖1所示。1 000位之后的圖像延續圖1后半段走勢,平緩遞增與遞減。

圖1 前1 000名PageRank值及影響范圍占比情況

圖1顯示,選取1/10的節點就可達到超過80%的影響范圍,僅需1%的節點即可達到60%以上的影響范圍。因此,本文從減小種子節點選取范圍出發,選取具有較高PageRank值的節點作為備選種子節點。考慮到當K值較小時(比如K=10),并不需要從前500個甚至很多的節點中挑選出10個種子節點,僅從前100個節點來看完全可以達到預想效果。同時,為了防止使用固定數量的備選種子可能會造成的局部最優情況,本文使用線性規則來選取備用種子節點,即選取PageRank值排名靠前的hK個節點作為備選種子節點,為了方便計算在實驗中將h值設為10。這樣,不僅從數量上減少運算時間,而且在一定程度上消除可能存在的局部最優情況。

3.2 備選種子合并影響預計算

文獻[17]在數據集DBLP上證實了六度分割理論猜想:每個人最多通過6個人就可以認識一個陌生人。同樣,在社交網絡信息傳播的過程中,也僅需幾次即可將信息傳播開。圖2是社交網絡中種子節點A、B影響傳播的局部路徑簡單傳播模型,其中,t表示當前傳播次數。

圖2 社交網絡信息傳播路徑

在圖2中,設每條有向邊傳播概率相同,為常量p,那么種子節點A通過邊激活節點C的概率即為p,節點C被激活后,就有p的概率通過邊影響到F節點,故節點A通過邊和激活節點F的概率為p2。節點D的影響來源于種子節點A、B以及節點C的傳遞影響,那么它可被以p概率激活2次,以p2概率激活一次,于是,節點D被激活的概率為1-(1-p)2+p2。

備選種子合并影響預計算,是對備選種子集中每個備選種子進行一次節點自身傳播范圍內可被激活節點次數及輪次統計。對于種子節點A,其可激活節點集為{C,D,F,G,M},且t=1的有{C,D},t=2的有{D,F,G},t=3的有{G,M},其中,當t=3時有節點G的原因是存在一條A-C-D-G通路。對于種子集合{A,B}來說,由于它們之間有共同影響部分,故它們的影響概率并不是節點A和B的概率簡單相加。因此,在最終計算種子集合的影響概率時,先要分別統計各種子節點的預處理結果,再合并計算它們的影響概率。

在不同傳播概率p下,若以不同傳播次數t分別嘗試500次激活,通過公式P=1-(1-pt)500可計算出節點被激活概率。例如,當t=3時,節點被激活的概率為p3,假設該節點被激活500次,則該節點在t=3下被激活概率為1-(1-p3)500,如表1所示。

表1 500次激活下節點被激活概率

如表1所示,當t=3,p=0.01時,仍有萬分之五的概率能夠激活節點,而當t=3,p=0.06時被激活概率達到約0.1。當t=4,p=0.01時,節點幾乎不可能被激活,而p=0.06時也僅僅只有0.006的概率。因此,本文針對文獻[13]中只考慮近距離(t=2)傳播的問題,將種子節點可影響步數調整為t=3步,雖然在一定程度上加大了算法的時間復雜度,但是其傳播概率計算更為準確合理。

設G(V,E)為有向圖,seed表示某種子節點,t表示當前傳播輪次,該備選種子預處理算法(Alternative Seed Preprocess Algorithm,ASPA)采用圖深度優先遍歷策略,算法描述如下:

輸入t,seed,G(V,E)

輸出各種子節點統計信息

執行步驟:

1)如果t>3,返回,否則轉到2)。

2)Fseed←節點seed所有未嘗試激活的鄰居節點,轉到3)。

3)SR(seed,times)←Fseed,轉到4)。

4)標記節點seed已嘗試激活,轉到5)。

5)對于?u∈Fseed,遞歸計算ASPA(t+1,u,G)。

6)返回SR。

其中,步驟1)、步驟3)、步驟4)的時間復雜度都是O(1),步驟2)的時間復雜度為O(n),G圖以類似鄰接表的形式存儲,在一定程度上降低了算法時間復雜度,以單節點出發的時間復雜度為O(n+e),因此,總體時間復雜度為O(Kn+e)。

3.3 遺傳算法全局優化過程

設p表示傳播模型傳播概率,seedlist表示包含k個種子節點的列表集合,SR表示3.2節計算所得信息集,遺傳算法優化過程的適應性函數CountSeed描述如下:

輸入seedlist,p,SR

輸出這k個種子節點的綜合影響概率

1.total_probability←0

2.for t=1 to 3:

4.count=Count(infect_list)

5.for user in count.keys():

6.number←count[user]

7.probability←1-(1-pt)numbers

8.total_probability+=probability

9.return total_probability

該適應性函數CountSeed時間復雜度為O(n),設p為傳播模型各邊傳播概率,k表示一個族群中種子個數,popsize表示種群集合中種群數,elite表示種群集合中精英所占比例,maxiter表示最大迭代次數,vatiprob用來判定族群選擇交叉還是變異,CIPIM算法GA過程描述如下:

輸入costfunc,k,popsize,elite,maxiter,vatiprob,p

輸出k個種子組成的集合

1)生成初始種群POP={P1,P2…,Ppopsize},其中每個族群P都包含k個節點,轉到2)。

2)計算種群集每個族群綜合影響概率,將種群中CountSeed返回值較大者作為精英保留;如果迭代次數達到maxiter,轉到5),否則轉到3)。

3)根據vatiprob判斷對保留下來的精英族群進行交叉操作還是變異操作,并添加到新的種群集POP'中,轉到4)。

4)如果len(POP′)小于popsize,轉到3),否則轉到2)。

5)返回綜合影響概率最高的種子集合。

4 實驗結果與分析

4.1 實驗數據集

為了全面分析CIPIM算法在不同規模網絡環境下影響傳播效果、可擴展性及性能,本文選取規模不同的2個真實社交網絡數據集Wiki-Vote[16]和Twitter[18],它們的統計特性如表2所示。

表2 屬性特征權重

4.2 實驗設置

為驗證本文算法的性能,選取當前較有代表性的算法進行比較。因為貪心算法在時間復雜度上較高,即便是后續優化后的算法仍然需要較長、甚至數天的時間才能得到結果,所以本文不與貪心算法進行比較,而與DegreeDiscount、PageRank、CCA等算法進行比較。DegreeDiscount算法是一種種子節點對鄰居節點進行度折扣的啟發式算法;PageRank算法,是Google用于標識網頁重要性的算法,本文中將阻尼因子設置為0.85;CCA(d)算法是基于核數層次特征、消除重復影響的一種啟發式算法,原文中距離參數d為2時效果更好,因此,本文使用CCA(2)進行比較。本文算法CIPIM中備選種子比例h取為10;種群數一般設置為20～100,本文將種群數popsize設為50;最大迭代數一般取100～500,在本算法中因為對下一層精英選擇過程做了特殊處理,算法將加速收斂,因此將最大迭代次數maxiter設為100;同理,精英策略elite設為0.2。

為了討論傳播概率對傳播結果的影響,排除實驗結果的偶然性,分別將影響傳播概率設置為0.01、0.03、0.06進行蒙特卡洛模擬傳播,并對每次模擬傳播進行1 000次實驗,取平均值作為傳播結果。

實驗硬件環境為macOS,內存8 GB,處理器1.6 GHz Intel Core i5,所有代碼均使用Python2.7.10書寫。

4.3 結果分析

影響最大化算法的評價通常從影響范圍和時間效率2個方面衡量。

4.3.1 Wiki-Vote數據集實驗

Wiki-Vote數據集是維基百科的一個投票數據,屬于中型數據集。圖3～圖5為各傳播概率下的模擬實驗平均被影響節點個數趨勢。

圖3 Wiki-Vote上p=0.01時被影響節點數

圖4 Wiki-Vote上p=0.03時被影響節點數

圖5 Wiki-Vote上p=0.06時被影響節點數

從圖3～圖5可以看出,在k<10時,各種算法在影響范圍上結果較為接近,相差不大。但當k>10時,可以明顯看出,CCA算法比其他算法在影響范圍上要稍稍遜色,且隨著k值增大,差異也越來越大。CCA算法為了減少算法運行時間,犧牲掉間接傳播這一網絡特性,導致其影響范圍跟其他算法相比有些差距。CIPIM算法在PageRank的算法基礎上進行全局優化,其結果要好于單純的PageRank算法。隨著種子數k和傳播概率p的變大,算法之間效果的差異也越來越大。表3為不同傳播概率下各算法的平均運行時間。

表3 WikiVote數據集下各算法平均運行時間 s

由表3可以看出,CIPIM算法在運行時間上比其他算法稍多一點,但時間差距并不算大,居于相同數量級下。由于種子節點數k對CIPIM算法有一定的影響,因此,隨著k值的增大,算法所用時間也會隨之稍稍增大。但對于貪心算法而言,CIPIM算法用時已經相當低了。綜上,CIPIM算法在數據集Wiki-Vote上有良好表現,算法有效。

4.3.2 Twitter數據集實驗

Twitter數據集屬于大型社交網絡數據集,雖然節點數不到10萬個,但是卻有著百萬級別由關注關系形成的有向邊。圖6～圖8為各傳播概率下的模擬實驗被影響節點數趨勢。

圖6 Twitter上p=0.01時被影響節點數

圖7 Twitter上p=0.03時被影響節點數

圖8 Twitter上p=0.06時被影響節點數

從圖6～圖8可以看出,在較大型社交網絡中,CIPIM算法表現優異。當k值較小時,除了PageRank算法表現一般,各算法相差不大。和Wiki-Vote數據集的運行結果相似,但是在k>10之后,算法之間的差異開始凸顯,CCA算法在Twitter數據集上比DegreeDiscount算法要好上一點,說明在真正的社交網絡上確實會有影響重疊的現象存在。CIPIM算法是從經PageRank算法排序后的節點中選擇有較高影響力的節點作為備選節點,然后再通過潛在被激活節點的綜合激活概率優化得到,所以在運行結果上,CIPIM算法始終高于PageRank算法。表4為不同傳播概率下各算法的平均運行時間。

表4 Twitter數據集下各算法平均運行時間 s

從表4可以看出,CIPIM算法在大型數據集上平均運行時間方面仍然表現良好,雖然比一些算法稍稍偏多,但是在影響范圍覆蓋度上彌補了這些不足。其中需要說明的是,在CIPIM算法中包含PageRank算法,但是只需計算一次,所以,在運行時間內沒有包含在里面。

從以上實驗結果表明,不管是在Wiki-Vote數據集還是Twitter數據集上,不管傳播概率的取值如何,CIPIM算法均表現出較大優勢。因為本文算法會在全局上進行優化,所以與直接從節點度或核出發的算法相比在平均時間上要略高,但在節點選取效果上要好于這些算法,且在時間效率上要遠遠好于貪心算法,能在影響覆蓋度和運行時間上取得了較好的平衡。

5 結束語

本文提出一種基于合并影響概率的遺傳算法,并利用該算法來解決影響最大化問題,通過縮減種子搜尋范圍來減少工作量,使用遺傳算法進行全局優化。實驗結果表明,CIPIM算法改善了CCA算法在共同影響概率缺失方面的問題,同時與CCA算法、DegreeDiscount算法以及PageRank算法相比影響范圍更廣,時間復雜度遠小于貪心算法。然而,本文算法仍存在不足之處,即各節點間的傳播概率都是固定值,但在實際社交網絡中并非如此。因此,在下一步工作中,將通過數據挖掘、機器學習等方法綜合考慮多個社交網絡,使其能夠確定用戶間不同的傳播概率。

[1] DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2001:57-66.

[2] KEMPE D,KLEINBERG J,TARDOSE.Maximizing the spread of influence through a social network[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:137-146.

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

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

[5] CHEN Wei,WANG Yajun,YANG Siyu.Efficient influence maximization in social networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2009:199-208.

[6] WASSERMAN S,FAUST K.Social network analysis[J].Encyclopedia of Social Network Analysis & Mining,2011,22(Suppl 1):109-127.

[7] BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks & Isdn Systems,1998,30(1-7):107-117.

[8] CHEN W,WANG C,WANG Y.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2010:1029-1038.

[9] SONG Guojie,ZHOU Xiabing,WANG Yu,et al.Influence maximization on large-scale mobile social network:a divide-and-conquer method[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(5):1379-1392.

[10] ZHOU Chuan,ZHANG Peng,ZANG Wenyu,et al.On the upper bounds of spread for greedy algorithms in social network influence maximization[J].IEEE Transactions on Knowledge & Data Engineering,2015,27(10):1.

[11] LI Ji,CAI Zhipeng,YAN Mingyuan,et al.Using crowdsourced data in location-based social networks to explore influence maximization[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2016:1-9.

[12] 曹玖新,董 丹,徐 順,等.一種基于k-核的社會網絡影響最大化算法[J].計算機學報,2015,38(2):238-248.

[13] MIAO Yu,WU Yang,WANG Wei,et al.UGGreedy:Influence maximization for user group in microb-logging[J].Chinese Journal of Electronics,2016,25(2):241-248.

[14] GRANOVETTER M.Threshold models of collective behavior[J].American Journal of Sociology,1978,83(6):1420-1443.

[15] WATTS D J.A simple model of global cascades on random networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(9):5766-5771.

[16] LESKOVEC J.Wikipedia vote network[EB/OL].[2017-03-10].http://snap.stanford.edu/data/wiki-Vote.html.

[17] ELMACIOGLU E,LEE D.On six degrees of separation in DBLP-DB and more[J].Acm Sigmod Record,2005,34(2):33-40.

[18] LESKOVEC J.Social corcles:twitter[EB/OL].[2017-03-10].http://snap.stanford.edu/data/egonets-Twitter.html.