基于重疊節點的社會網絡最短路徑算法

朱愷騁,　程　華

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

?

基于重疊節點的社會網絡最短路徑算法

朱愷騁,程華

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

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

社會網絡; 最短路徑; 重疊節點; 分層網絡

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

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

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

1　基于重疊節點的分層網絡路徑發現(HOLN)算法

1.1基于LFM算法的網絡層次劃分

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

LFM算法[5]既能發現重疊點又能將網絡進行層次結構劃分,因此本文采用LFM算法發現社區。LFM算法計算節點的適應度,其函數定義為

(1)

(2)

分層網絡構建算法步驟如下:

第1階段,基于LFM的社區劃分與重疊節點發現。

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

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

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

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

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

圖1　社區發現后的網絡重構Fig.1　Network restructure after community discovery

1.2社區間距計算

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

(3)

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

(4)

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

(5)

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

(6)

式中k是最高級網絡聚合的層數。圖2為層次網絡聚合示意圖,體現了層次間的關系,第i級層次網絡的中心節點csi和cti分別對應第i+1級層次網絡中的普通節點si+1和ti+1。

1.3分層重疊網絡的路徑引導算法

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

圖2　層次網絡聚合Fig.2　Hierarchical network aggregation

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

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

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

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

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

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

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

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

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

2　實驗與分析

2.1數據集

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

表1　實驗網絡參數

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

(7)

2.2實驗與結果分析

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

表2　算法在不同網絡上的PathRatio值

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

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

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

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

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

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

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

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

表3　HOLN算法在跨越不同社區數量時的性能比較

3　結束語

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

[1]唐晉韜,王挺,王戟.適合復雜網絡分析的最短路徑近似算法[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]宋青.大規模網絡最短路徑的分層優化算法研究[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-),男,浙江杭州人,碩士生,研究方向為社會網絡。

通信聯系人：程 華,E-mail:hcheng@ecust.edu.cn

TP301

A