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

朱愷騁,　程　華

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

?

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

朱愷騁,程華

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

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

社會(huì)網(wǎng)絡(luò); 最短路徑; 重疊節(jié)點(diǎn); 分層網(wǎng)絡(luò)

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

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

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

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

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

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

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

(1)

(2)

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

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

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

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

(3) 計(jì)算社區(qū)G內(nèi)每1個(gè)節(jié)點(diǎn)的適應(yīng)度,若內(nèi)有適應(yīng)度小于0的節(jié)點(diǎn),將該節(jié)點(diǎn)從社區(qū)中移除;

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

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

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

1.2社區(qū)間距計(jì)算

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

(3)

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

(4)

每個(gè)分層都是上一級(jí)網(wǎng)絡(luò)以相同的尺度聚合而來(lái),可推得

(5)

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

(6)

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

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

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

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

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

圖3　路徑構(gòu)造示意圖Fig.3　Scheme of path structure

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

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

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

②找出從當(dāng)前社區(qū)到下次訪問(wèn)的社區(qū)之間的邊(圖3中的p11、c11和p12、c12),找到它們?cè)诟篙吷鐓^(qū)中的端點(diǎn),即p11、p12;

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

重復(fù)步驟①～③進(jìn)行路徑的構(gòu)造與拼接。

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

2　實(shí)驗(yàn)與分析

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

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

表1　實(shí)驗(yàn)網(wǎng)絡(luò)參數(shù)

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

(7)

2.2實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

圖4　不同算法的預(yù)處理時(shí)間Fig.4　Pretreatment computing time of different algorithms

圖5　不同算法的路徑計(jì)算時(shí)間Fig.5　Path computation time of different algorithms

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

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

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

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

3　結(jié)束語(yǔ)

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

[1]唐晉韜,王挺,王戟.適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J].軟件學(xué)報(bào),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)絡(luò)最短路徑的分層優(yōu)化算法研究[D].上海:上海交通大學(xué),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-),男,浙江杭州人,碩士生,研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)。

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

TP301

A