吳海林
【摘 要】為了解決傳統(tǒng)貪心算法不能有效解決大規(guī)模社會網(wǎng)絡(luò)影響力最大化的效率問題,采用模塊度將大規(guī)模的通信網(wǎng)絡(luò)劃分成較小的社區(qū)模塊,并通過改進(jìn)PageRank排名算法來評價有向復(fù)雜網(wǎng)絡(luò)節(jié)點的傳播能力,然后再利用KK算法挑選當(dāng)前帶來最大影響范圍的剩余種子節(jié)點,提出基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法。實驗證明,該方法具有一定的擴(kuò)展性和有效性。
【關(guān)鍵詞】社區(qū)劃分 改進(jìn)PageRank KK算法 影響力最大化 傳播能力
1 引言
隨著各類移動社交服務(wù)如Facebook、Twitter、微博、微信、QQ等對人類生活、社交的滲透,社交網(wǎng)絡(luò)在信息溝通、信息共享、信息傳播擴(kuò)散等方面起到了不可忽視的作用。伴隨移動社交網(wǎng)絡(luò)節(jié)點的增長,核心節(jié)點作為信源,其傳播影響作用不容小覷,其中影響力最大化研究能夠?qū)ι鐣卜馈⑹袌鰻I銷等領(lǐng)域起到重要作用,因此得到了不少學(xué)者的追捧。比如:Luo[1]等人基于冪定律法則的影響力分布下,提出了PageRank的啟發(fā)式算法來尋找種子節(jié)點;Chen[2]等人考慮節(jié)點的拓?fù)浣Y(jié)構(gòu),提出了基于節(jié)點、最鄰近節(jié)點以及次近節(jié)點的多級鄰居指標(biāo)的節(jié)點重要性排序;Wang[3]等人提出了基于社區(qū)發(fā)現(xiàn)求解影響力的CGA算法;郭進(jìn)時[4]等人選取影響力傳播范圍和影響力傳播時延這兩個指標(biāo)衡量節(jié)點的影響力,提出了社區(qū)結(jié)構(gòu)的影響力最大化算法。在上述研究的基礎(chǔ)上,本文提出了基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法。該算法首先通過模塊度進(jìn)行社區(qū)劃分,然后通過改進(jìn)PageRank算法選取移動通信有向加權(quán)復(fù)雜網(wǎng)絡(luò)的種子節(jié)點,再利用KK算法局部最優(yōu)的特性選取當(dāng)前帶來最大影響范圍的剩余種子節(jié)點,以期盡可能地擴(kuò)展算法的傳播影響范圍。
2 網(wǎng)絡(luò)影響力最大化研究
網(wǎng)絡(luò)影響力最大化這個問題要追溯到2002年,Richardson和Domings如何尋找社會網(wǎng)絡(luò)中最具影響力的成員,并發(fā)放免費樣品,通過這些最具影響力的成員口口相傳,使這些樣品的相關(guān)信息在社會網(wǎng)絡(luò)中順利傳播,以達(dá)到波及范圍廣和成本低廉的營銷目的。
影響力最大化初始定義是在所有網(wǎng)絡(luò)節(jié)點中選取最具有影響力的節(jié)點作為初始活躍節(jié)點,使其經(jīng)過影響傳播,網(wǎng)絡(luò)最終被影響的節(jié)點數(shù)最多。但在實際應(yīng)用過程中,處理網(wǎng)絡(luò)影響力的關(guān)鍵包括如下:
(1)在有限的資源下種子節(jié)點的選取問題;
(2)如何在節(jié)點的影響力信息的級聯(lián)下,通過貪心算法求出k個節(jié)點的影響力最大范圍。
傳統(tǒng)的種子節(jié)點選取使用靜態(tài)的啟發(fā)式節(jié)點選擇策略,一般采用度中心性、介數(shù)、緊密度等指標(biāo)進(jìn)行衡量,通過這些指標(biāo)或者組合指標(biāo)來確定節(jié)點的影響力,然后采用影響力排序的方法選取種子節(jié)點,以便實現(xiàn)網(wǎng)絡(luò)傳播最大化的目的;另外一種是動態(tài)的影響力最大化算法,首先構(gòu)建網(wǎng)絡(luò)傳播模型,然后通過貪心算法求出最大傳播范圍的k個種子節(jié)點。
無論采取上述哪種算法,都有本身的缺陷。靜態(tài)啟發(fā)式的算法雖然處理速度較高、計算復(fù)雜度低,但是不能保證種子節(jié)點的傳播影響力最大化;貪心算法由于計算復(fù)雜度太高,所以并不擅長處理大型的復(fù)雜網(wǎng)絡(luò)。
因此,本文在總結(jié)上述兩種算法的優(yōu)點的基礎(chǔ)上,結(jié)合社區(qū)劃分的方法、改進(jìn)PageRank以及KK局部最優(yōu)算法來解決有向加權(quán)復(fù)雜網(wǎng)絡(luò)影響力最大化的問題。
3 基于社區(qū)劃分和改進(jìn)PageRank的影響
力最大化算法
3.1 有向加權(quán)復(fù)雜網(wǎng)絡(luò)模型
本文研究的數(shù)據(jù)是移動通信網(wǎng)絡(luò)的用戶業(yè)務(wù)數(shù)據(jù),因此在介紹算法之前,必須先介紹移動通信網(wǎng)絡(luò)模型。
移動通信網(wǎng)絡(luò)模型可以認(rèn)為是有向加權(quán)網(wǎng)絡(luò),其模型可用G表示,G=(V, E)。其中,V表示網(wǎng)絡(luò)節(jié)點集合,可表示為V={v1, v2, …, vn};E表示網(wǎng)絡(luò)有向邊集合,可表示為E={e1, e2, …, en}V×V。w(vi, vj)表示有向邊(vi, vj)的權(quán)值(或稱連接強(qiáng)度)。
3.2 基于模塊度的社區(qū)劃分方法
眾所周知,復(fù)雜網(wǎng)絡(luò)的節(jié)點之間的信息得以傳播是因為節(jié)點在某種程度上具有相似性?;谀K度劃分社區(qū)的思想是社區(qū)內(nèi)部的節(jié)點相似度較高,而在社區(qū)外部的節(jié)點相似度較低。因此,本文在社區(qū)劃分的基礎(chǔ)上,將社區(qū)的逐漸擴(kuò)散等效于信息傳播的過程,借助于連接緊密的社區(qū)內(nèi)部節(jié)點具有相似性這一思想,信息傳播在連接緊密的相似節(jié)點進(jìn)行傳播。
3.4 KK算法
Kempe和Kleinberg首次采用一種貪心算法來解決社會網(wǎng)絡(luò)影響力最大化的問題,通過KK算法[8]來尋找種子節(jié)點組合。KK算法是一種局部最優(yōu)的算法,通過遍歷每個節(jié)點的影響范圍,然后采用影響力降序的排名算法來挑選當(dāng)前影響力最大范圍的節(jié)點作為種子節(jié)點,但是這種局部改進(jìn)的算法并不能保證最終得到的種子節(jié)點的影響范圍最優(yōu)。因此,本文采用改進(jìn)PageRank算法來選擇k-[ck]個種子節(jié)點,然后通過節(jié)點來激活由模塊度劃分的重要社區(qū),在激活階段利用貪心算法來選取剩余[ck]個種子節(jié)點。
其中,w(u,v)表示用戶v獲得用戶源u的邊權(quán)重。如果w(u,v)大于所設(shè)定的閾值,那么說明用戶v被激活。
根據(jù)上述步驟對劃分的重要社區(qū)進(jìn)行激活節(jié)點的影響范圍計算,再對各個種子節(jié)點的影響范圍進(jìn)行排序,進(jìn)而確定最終的k個種子節(jié)點。
4 實驗分析
本文采用某市移動運(yùn)營商的用戶通話數(shù)據(jù),驗證基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法的有效性。該復(fù)雜網(wǎng)絡(luò)共由5 000個節(jié)點組成,有90 663條有向邊,有向邊表示用戶之間滿足特定的通話關(guān)系和通話時長的條件(一個月內(nèi)大于4次通話,或每次平均通話時長約為30 s)。以用戶之間通話次數(shù)的比例乘以通話時長的比例作為權(quán)值。
首先對該數(shù)據(jù)進(jìn)行社區(qū)劃分,得到8個社區(qū);然后采用PageRank算法對每個社區(qū)進(jìn)行用戶傳播能力排名,再用KK算法選擇剩余種子節(jié)點來激活的社區(qū),最終算出每個社區(qū)的k(k≤10)個種子的影響范圍,得到每個社區(qū)選取的種子數(shù)量如表1所示。
通過上述結(jié)果可知,如果需要對該網(wǎng)絡(luò)選取10個種子,那么根據(jù)表1選取的種子用戶為15、101、19、132、187、55、199、54、34、487。
本文采用度中心性算法進(jìn)行種子節(jié)點的選取,得到的影響節(jié)點數(shù)量與本文設(shè)計的算法進(jìn)行對比,具體結(jié)果如圖1所示。
由圖1可知,采用基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法具有較大的傳播范圍。并且本文提出的算法與度中心性算法在不同規(guī)模的種子節(jié)點上的擴(kuò)散速率是相吻合的,從而驗證了該算法的有效性。
5 結(jié)束語
本文提出了一種基于社區(qū)劃分的移動通信有向加權(quán)復(fù)雜網(wǎng)絡(luò)影響力最大化算法——基于社區(qū)劃分和改進(jìn)PageRank的影響力最大化算法,與之前關(guān)于影響力最大化研究不同的是首先基于模塊度將移動通信網(wǎng)絡(luò)劃分成社區(qū),實現(xiàn)了化整為零的效果,然后采用改進(jìn)PageRank算法評估用戶傳播能力,并以此來選擇k-[ck]個種子節(jié)點,再利用KK算法挑選當(dāng)前帶來最大影響范圍增量的剩余[ck]個種子節(jié)點,以達(dá)到影響力最大化的目標(biāo)。經(jīng)過實驗驗證了該算法的有效性和高效性,通過社區(qū)劃分能夠在一定程度上提高算法的效率,可以很好地適應(yīng)大規(guī)模的社會網(wǎng)絡(luò)環(huán)境。
參考文獻(xiàn):
[1] Luo Z L, Cai W D, Li Y J, et al. A PageRank-Based Heuristic Algorithm for Influence Maximization in the Social Network[C]//Recent Progress in Data Engineering and Internet Technology. Berlin Heidelberg: Springer, 2012: 485-490.
[2] Chen D, Lv L, Shang M, et al. Identifying influential nodes in complex networks[J]. Physica A Statistical Mechanics & Its Applications, 2012,391(4): 1777-1787.
[3] 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 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC: ACM, 2010: 1039-1048.
[4] 郭進(jìn)時,湯紅波,吳凱,等. 基于社區(qū)結(jié)構(gòu)的影響力最大化算法[J]. 計算機(jī)應(yīng)用, 2013,33(9): 2436-2439.
[5] 張益. 一種定量評估復(fù)雜網(wǎng)絡(luò)節(jié)點重要度的算法[J]. 計算機(jī)工程, 2011,37(20): 87-88.
[6] 李建華,汪曉鋒,吳鵬. 基于局部優(yōu)化的社區(qū)發(fā)現(xiàn)方法研究現(xiàn)狀[J]. 中國科學(xué)院院刊, 2015,30(2): 238-247.
[7] 張琨,李配配,朱保平,等. 基于PageRank的有向加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點重要性評估方法[J]. 南京航空航天大學(xué)學(xué)報, 2013,45(3): 429-434.
[8] Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence in a social network[C]//Proceeding of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM New York, 2003: 137-146.
[9] 王雙,李斌,劉學(xué)軍,等. 基于社區(qū)劃分的影響力最大化算法[J]. 計算機(jī)工程與應(yīng)用, 2016,52(19): 42-47.
[10] 吳萍. 移動社交網(wǎng)絡(luò)中的信息傳播最大化問題研究[D]. 濟(jì)南: 濟(jì)南大學(xué), 2015.