朱愷騁,　程　華

(華東理工大學信息科學與工程學院,上海 200237)

?

基于重疊節(jié)點的社會網(wǎng)絡最短路徑算法

朱愷騁,程華

(華東理工大學信息科學與工程學院,上海 200237)

通過路徑發(fā)現(xiàn)和分析可以挖掘社會網(wǎng)絡中人與人之間的關系及其連接特性,特別是在犯罪網(wǎng)絡的應用中具有重要意義。通過社區(qū)發(fā)現(xiàn)算法獲得社區(qū)間的重疊節(jié)點,并構造目標網(wǎng)絡的分層網(wǎng)絡模型; 基于社會網(wǎng)絡的高聚集系數(shù)特性及冪律分布拓撲特征,提出了基于重疊節(jié)點的分層網(wǎng)絡路徑發(fā)現(xiàn)(HOLN)算法,以核心節(jié)點距離代替社區(qū)間距,優(yōu)化路徑搜索方向; 優(yōu)先搜索重疊節(jié)點,簡化對節(jié)點的遍歷,實現(xiàn)源與目標間最短路徑的快速發(fā)現(xiàn)。實驗結果表明,本文提出的HOLN算法在計算精度和運行效率上都有令人滿意的表現(xiàn)。

社會網(wǎng)絡; 最短路徑; 重疊節(jié)點; 分層網(wǎng)絡

面向社會網(wǎng)絡的挖掘和分析是目前的研究熱點,通過路徑的發(fā)現(xiàn)和分析可以挖掘社會網(wǎng)絡中人與人之間的關系及其連接特點,特別是在恐怖襲擊網(wǎng)絡、犯罪網(wǎng)絡中的應用中具有重要意義。最短路徑算法是路徑發(fā)現(xiàn)的基礎算法,在一定網(wǎng)絡規(guī)模下具有高精度、高復雜度的特點?；ヂ?lián)網(wǎng)環(huán)境下社會網(wǎng)絡往往具有較大的規(guī)模,導致經(jīng)典算法由于計算復雜度急劇升高難以有效運用,可采用優(yōu)化算法結構的方法降低算法的計算復雜度或采用啟發(fā)式方法限定搜索空間獲得近似計算最短路徑。

CDZ算法[1]基于實際網(wǎng)絡的拓撲特征進行算法結構優(yōu)化,利用了局部中心性和區(qū)域中心點距離的最短路徑近似計算,路徑計算的時間復雜度降為O(e+nlgn),但預處理的時間開銷較大; LBFS算法[2]根據(jù)最優(yōu)覆蓋策略選擇路標集合,廣度優(yōu)先遍歷計算路標子網(wǎng)絡中節(jié)點到路標的路徑,算法運算效率很高,但在最優(yōu)覆蓋策略中利用復雜度較高的Dijkstra算法使得算法消耗的預處理時間隨著網(wǎng)絡規(guī)模的擴大呈線性增長; 基于子圖引導的路徑發(fā)現(xiàn)算法[3]采用分層引導的啟發(fā)式思想縮小交通網(wǎng)絡的搜索空間,降低了算法復雜度,但算法通過網(wǎng)絡中節(jié)點的坐標引導搜索方向,無法運用在抽象網(wǎng)絡中。

根據(jù)分層策略能夠抑制算法隨網(wǎng)絡規(guī)模擴大而非線性增長的特性,本文提出了基于重疊節(jié)點的分層網(wǎng)絡路徑(HOLN)算法。首先將目標網(wǎng)絡分層降解得到分層網(wǎng)絡及重疊節(jié)點; 然后利用社會網(wǎng)絡的高聚集性和冪律分布特征,以核心節(jié)點距離代替社區(qū)間距,通過社區(qū)間距引導搜索方向; 在路徑搜索中對重疊節(jié)點進行優(yōu)先搜索,從而簡化對節(jié)點的遍歷,達到提高搜索效率和精度的目的。

1　基于重疊節(jié)點的分層網(wǎng)絡路徑發(fā)現(xiàn)(HOLN)算法

1.1基于LFM算法的網(wǎng)絡層次劃分

社會網(wǎng)絡是由個人或組織作為節(jié)點構成的一種網(wǎng)絡結構,經(jīng)由社會關系,把個人或組織串聯(lián)起來。社會網(wǎng)絡的社區(qū)結構是根據(jù)節(jié)點之間的距離或相似度劃分的若干個群組,同一個群組內節(jié)點之間的連接比不同群組節(jié)點之間的連接密集,而不同社區(qū)之間往往有重疊節(jié)點[4],是網(wǎng)絡的關鍵“橋梁”,節(jié)點間的最短路徑在跨越不同社區(qū)時經(jīng)過重疊節(jié)點的可能性非常大,因此本文將重疊節(jié)點作為路徑發(fā)現(xiàn)中優(yōu)先搜索的節(jié)點。

LFM算法[5]既能發(fā)現(xiàn)重疊點又能將網(wǎng)絡進行層次結構劃分,因此本文采用LFM算法發(fā)現(xiàn)社區(qū)。LFM算法計算節(jié)點的適應度,其函數(shù)定義為

(1)

(2)

分層網(wǎng)絡構建算法步驟如下:

第1階段,基于LFM的社區(qū)劃分與重疊節(jié)點發(fā)現(xiàn)。

(1) ?v∈V,任取節(jié)點v作為初始社區(qū)G;

(2) 計算社區(qū)G的所有鄰居節(jié)點的適應度,適應度大于0的節(jié)點加入到社區(qū)G中,若社區(qū)G的全部鄰居節(jié)點的適應度都小于0,進行第(4)步;

(3) 計算社區(qū)G內每1個節(jié)點的適應度,若內有適應度小于0的節(jié)點,將該節(jié)點從社區(qū)中移除;

第2階段,社區(qū)發(fā)現(xiàn)后的層次網(wǎng)絡重構。基于第1階段發(fā)現(xiàn)的社區(qū),構建相應的抽象網(wǎng)絡,如圖1所示。按照社區(qū)劃分時節(jié)點加入社區(qū)Gn的順序,從初始節(jié)點v開始,并入社區(qū)中適應度最大的中心節(jié)點,并將原來指向節(jié)點v的連接修正為指向中心節(jié)點,直到社區(qū)中節(jié)點都指向中心節(jié)點,該社區(qū)便以中心節(jié)點為核心聚合成更高層次中的節(jié)點。

兩個階段交替地進行,直到網(wǎng)絡中所有節(jié)點都找到所屬的社區(qū)并聚合,由此得到實際網(wǎng)絡的層次結構及社區(qū)的重疊節(jié)點集合。

圖1　社區(qū)發(fā)現(xiàn)后的網(wǎng)絡重構Fig.1　Network restructure after community discovery

1.2社區(qū)間距計算

真實網(wǎng)絡中大部分節(jié)點在小范圍內相互連接,呈現(xiàn)出高聚集性以及冪律分布特征[6],即存在少量高適應度的中心節(jié)點及大量低適應度的普通節(jié)點[7]。CDZ算法論證了復雜網(wǎng)絡中,任意節(jié)點之間的最短路徑有極大概率經(jīng)過中心節(jié)點。利用該結論,可通過計算節(jié)點到中心節(jié)點的距離獲得節(jié)點間的近似位置,在此基礎上聚合構造的抽象網(wǎng)絡,由社區(qū)對中心節(jié)點之間的距離代替社區(qū)之間的距離,迭代計算得到社區(qū)間距。

(3)

縮放比例Li是低層社區(qū)聚合成高層網(wǎng)絡后社區(qū)半徑之比[8],取每個分層的社區(qū)中適應度最大的節(jié)點作為中心節(jié)點c,定義第1級層次網(wǎng)絡的半徑r1為初始網(wǎng)絡社區(qū)中其余所有節(jié)點到中心節(jié)點的距離和的平均值,即

(4)

每個分層都是上一級網(wǎng)絡以相同的尺度聚合而來,可推得

(5)

定義r0=1,由式(4)、式(5)可得

(6)

式中k是最高級網(wǎng)絡聚合的層數(shù)。圖2為層次網(wǎng)絡聚合示意圖,體現(xiàn)了層次間的關系,第i級層次網(wǎng)絡的中心節(jié)點csi和cti分別對應第i+1級層次網(wǎng)絡中的普通節(jié)點si+1和ti+1。

1.3分層重疊網(wǎng)絡的路徑引導算法

利用社區(qū)間距及重疊節(jié)點信息作為啟發(fā)式引導,采用雙向搜索模式,在當前訪問的正向和反向社區(qū)的鄰居中挑選若干對距離較近的社區(qū)作為下次訪問的對象,使正向和反向搜索快速逼近。

圖2　層次網(wǎng)絡聚合Fig.2　Hierarchical network aggregation

圖3為路徑構造示意圖。圖中s和t為初始點與目標點,p36、p47是社區(qū)間的重疊節(jié)點。HOLN路徑引導算法分為兩個階段:

圖3　路徑構造示意圖Fig.3　Scheme of path structure

(1)選擇社區(qū)對。找出初始點s與目標點t所屬的源、目標社區(qū)對Gs和Gt作為當前社區(qū)對,選取從Gs的鄰居社區(qū)到Gt鄰居社區(qū)的α對距離最近的社區(qū)對,篩選出距離小于其父輩社區(qū)間距β倍的社區(qū),列為下次訪問的社區(qū)對。

(2)構造路徑。以正向搜索為例,步驟如下:

①在分層網(wǎng)絡中判斷當前社區(qū)Gs到下次訪問G2是否存在重疊節(jié)點,若存在,將其標記為點p(若有多個則標為p1,p2,…)并跳到步驟③,若不存在,則執(zhí)行步驟②;

②找出從當前社區(qū)到下次訪問的社區(qū)之間的邊(圖3中的p11、c11和p12、c12),找到它們在父輩社區(qū)中的端點,即p11、p12;

③由Dijkstra算法計算從初始點s到所有標記點的最短路徑,將其與之前獲取的路徑拼接起來,同時將重疊點或非重疊點(由步驟①中是否找到重疊節(jié)點決定)作為下一段路徑的拼接點。

重復步驟①～③進行路徑的構造與拼接。

兩個階段交替進行。算法中反向搜索和正向搜索類似,改為從目標社區(qū)Gt發(fā)出。當正向、反向搜索相遇,即在正向、反向搜索中出現(xiàn)了相同社區(qū)或者直接相鄰的社區(qū)對時,完成最后的路徑拼接,此時終止算法的執(zhí)行,在多條路徑中選擇最短的一條。參數(shù)α保證搜索空間得到一定的收縮,而β可以使算法沿著正確的軌跡收斂,避免因為網(wǎng)絡結構引起距離的躍變。依據(jù)經(jīng)驗并結合實驗分析,選取α=3、β=1.5可同時獲得較好的效率與精度。

2　實驗與分析

2.1數(shù)據(jù)集

本文使用斯坦福大規(guī)模網(wǎng)絡數(shù)據(jù)平臺提供的科學合作作者論文網(wǎng)絡COND和E-mail網(wǎng)絡Letter評測算法有效性。COND包含了濃縮物質物理領域的近21 360篇文獻及133 073個引用關系。E-mail網(wǎng)絡Letter共收集到4 136個用戶及其相互聯(lián)系形成的27 653條邊。由網(wǎng)絡的平均度可得,Letter較COND網(wǎng)絡稀疏。采用隨機網(wǎng)絡Random和根據(jù)Barabási模型生成的無標度網(wǎng)絡Scale-Free作為對比實驗網(wǎng)絡。實驗參數(shù)見表1。

表1　實驗網(wǎng)絡參數(shù)

本文引入LBFS算法[9]、CDZ算法作為對比,從算法精度和算法效率兩個方面比較各算法的性能。算法精度用平均路徑比P(PathRatio)度量,

(7)

2.2實驗與結果分析

CDZ算法選擇網(wǎng)絡總節(jié)點的10%作為中心節(jié)點,通過Dijsktra算法計算中心節(jié)點之間的最短路徑距離; LBFS算法通過最優(yōu)覆蓋策略選擇路標,以路標為根節(jié)點構建最小生成樹將所有節(jié)點納入路標所在的區(qū)域,由廣度遍歷算法計算該區(qū)域中任意兩點間的最短路徑。實驗隨機取20組源與目標節(jié)點對,計算各算法平均路徑比,結果如表2所示。

表2　算法在不同網(wǎng)絡上的PathRatio值

對于COND網(wǎng)絡和Letter網(wǎng)絡,CDZ算法和HOLN算法的近似準確性相對于LBFS方法有明顯提升,且在密集網(wǎng)絡COND中效果更好。這是因為CDZ和HOLN算法利用了實際網(wǎng)絡的高聚集性及冪律分布特征進行結構優(yōu)化,對COND和Letter這類網(wǎng)絡能起到很好的效果,而LBSF算法采用的是貪心策略。在無標度網(wǎng)絡上,HOLN算法使用了引導策略,一定程度上規(guī)避了對中心節(jié)點的完全依賴,最終路徑比P較CDZ算法好,與LBFS接近。因此,HOLN算法在不完全滿足實際網(wǎng)絡特性的網(wǎng)絡上精度尚可,而在實際社會網(wǎng)絡中,其路徑發(fā)現(xiàn)準確程度非常高。

在運算效率上,實驗隨機取1 000組源與目標節(jié)點對,分別計算在不同規(guī)模的無標度網(wǎng)絡上的預處理時間Tinit(HOLN算法計算社區(qū)間距,CDZ算法取全局中心節(jié)點并計算間距,LBSF算法選擇路標并將節(jié)點納入路標區(qū)域)和算法運行時間Tq,實驗結果見圖4、圖5。

從圖4和圖5可以看出,HOLN算法具有非常明顯的性能優(yōu)勢。LBSF算法在網(wǎng)絡規(guī)模較小時,預處理時間開銷最小,但隨著網(wǎng)絡規(guī)模的增大,達到4 000個節(jié)點后,預處理時間開銷超過了HOLN算法。而且LBSF在路徑計算時間的性能上為三者中最差,隨著網(wǎng)絡規(guī)模的增大而快速增加并且沒有明顯的收斂趨勢。

圖4　不同算法的預處理時間Fig.4　Pretreatment computing time of different algorithms

圖5　不同算法的路徑計算時間Fig.5　Path computation time of different algorithms

CDZ算法預處理時間遠大于其余兩者,尤其是在網(wǎng)絡規(guī)模增大后,這是因為CDZ算法直接在原網(wǎng)絡中選擇中心節(jié)點進行距離估算。HOLN算法通過分層策略對原網(wǎng)絡進行降解,實現(xiàn)了高效的社區(qū)間距計算,提高了整個算法的計算性能。

源節(jié)點與目標節(jié)點間可能跨越多個社區(qū),跨越社區(qū)的數(shù)量可能會影響最短路徑算法的準確度。以COND網(wǎng)絡為例,HOLN算法在跨越不同社區(qū)數(shù)量時的性能比較如表3所示。表3中短距是指跨越1～3個社區(qū)的源與目標對,中距是跨越了4～6個社區(qū),長距則跨越了7個以上的社區(qū)。隨著跨越社區(qū)距離的增加,HOLN算法精確度越來越高,源與目標對的距離越遠,第2階段的中心點距離估算所產(chǎn)生的估計誤差越小,當源與目標對的距離很近時,不僅估計的誤差會增大,還可能因網(wǎng)絡結構不良收縮引起距離的躍變使得精確度降低。

由實驗可知,在具有無標度特征的大規(guī)模社會網(wǎng)絡中進行路徑發(fā)現(xiàn),尤其是在密集網(wǎng)絡或遠距節(jié)點對的路徑計算,HOLN算法在精度和效率上都有令人滿意的表現(xiàn)。

表3　HOLN算法在跨越不同社區(qū)數(shù)量時的性能比較

3　結束語

面向大規(guī)模社會網(wǎng)絡中的路徑發(fā)現(xiàn)問題,本文提出了一種基于重疊節(jié)點的分層網(wǎng)絡的近似最短路徑發(fā)現(xiàn)算法,能有效提高路徑發(fā)現(xiàn)的精度和計算性能。其中重疊節(jié)點和分層網(wǎng)絡起到了簡化網(wǎng)絡和減少節(jié)點遍歷的作用; 而社會網(wǎng)絡的高聚集性及冪律分布特征保證了通過中心節(jié)點計算社區(qū)間距的可行性。HOLN算法是一種高效的最短路徑近似算法,隨著社會網(wǎng)絡的多樣化,如何將算法應用到動態(tài)更新的網(wǎng)絡中將成為下一步研究重點。

[1]唐晉韜,王挺,王戟.適合復雜網(wǎng)絡分析的最短路徑近似算法[J].軟件學報,2011,22(10):2279-2290.

[2]TRETYAKOV K,ARMAS-CERVANTES A,GARCA-BAUELOS L,etal.Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs[C]//Proceedings of the 20th ACM Conference on Information and Knowledge Management.Glasgow,United Kingdom:ACM,2011:1785-1794.

[3]宋青.大規(guī)模網(wǎng)絡最短路徑的分層優(yōu)化算法研究[D].上海:上海交通大學,2012:21-30.

[4]PALLA G.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.

[5]LANCICHINETTI A,FORTUNATO S,KERTESZ J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journal of Physics,2008,625(15):19-44.

[6]NEWMAN M E J.Detecting community structure in networks[J].The European Physical Journal B:Condensed Matter and Complex Systems,2004,38(2):321-330.

[7]OSBOURN G C.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Science,2001,98(2):404-409.

[8]NEWMAN M.Networks:An introduction[J].Astronomische Nachrichten,2010,327(8):741-743.

[9]CORNEIL D G,OLARIU S,STEWART L.The LBFS structure and recognition of interval graphs[J].Siam Journal on Discrete Mathematics,2009,23(4):1905-1953.

Shortest Path Algorithm of Social Network Overlapping Nodes

ZHU Kai-cheng,CHENG Hua

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

By path analysis,the relationship and connecting characteristic in social networks can be discovered,especially,in criminal networks.In this paper,the community discovery algorithm is utilized to obtain the overlapping nodes and construct the hierarchical network model of real social network.And then,by considering the high clustering coefficient and power law distribution of social network,this paper proposes an overlapping-nodes-based hierarchic path algorithm,HOLN,in which the core node distances are used to stand for community space and the overlapping nodes are searched preferentially to simplify node traversal.By the comparison experiment in the scientific cooperation network,it is shown that HOLN algorithm can attain satisfactory performance on the both accuracy and efficiency.

social network; shortest path; overlapping nodes; hierarchical network

1006-3080(2016)04-0552-05

10.14135/j.cnki.1006-3080.2016.04.017

2015-11-04

朱愷騁(1991-),男,浙江杭州人,碩士生,研究方向為社會網(wǎng)絡。

通信聯(lián)系人：程 華,E-mail:hcheng@ecust.edu.cn

TP301

A