曾 成，孫雅倩，徐玉珠，張達敏

(貴州大學大數(shù)據(jù)與信息工程學院，貴州貴陽 550025)

復雜網絡搜索中較為經典的算法有基于隨機游走(Random Walk，RW)搜索策略和最大度(High Degree Seeking，DS)搜索策略［1－3］。文獻［4］研究出了一種新的搜索策略，即最大－最小度搜索(Max－Min degree seareh，MM)策略，此策略高效地改良和擴充了最大度搜索策略，將網絡中的所有節(jié)點根據(jù)其度的大小分成兩塊，一塊是最大度效果占優(yōu)的節(jié)點，其會選擇最大度搜索策略，而其余節(jié)點就會選擇MM搜索策略。此策略可根據(jù)網絡中度的分布改變其系數(shù)來完成從最大度到隨機游走的變換，因此在無標度網絡中較為高效。此策略雖優(yōu)，但其卻并未考慮復雜網絡中有著的小世界性質，也忽略了其他表現(xiàn)網絡特性的參數(shù)，如常見的聚類系數(shù)和最小距離等。

本文借鑒文獻［4］的思路，引入了聚類系數(shù)和最小距離，結合了最小聚類系數(shù)搜索策略和貪婪算法，提出一種高效的局部搜索策略，旨在BA無標度網絡上有更好的搜索效果。

1 理論分析

因聚類系數(shù)小的節(jié)點有更高的度，且其鄰居節(jié)點之間有連接的概率也較小，所以在小世界網絡上最小聚類系數(shù)搜索策略比最大度搜索策略的性能要好。在小世界網絡中，短程所連接的兩個節(jié)點的鄰居節(jié)點之間有連邊的概率較大，因此，度大的節(jié)點并不意味著聚類系數(shù)就小。但長程所連接的兩個節(jié)點的鄰居節(jié)點之間有連邊的概率較小。因此，含有長程連接且度大的節(jié)點聚類系數(shù)較小［5－7］?？傊?，點的聚類系數(shù)越高就意味著其鄰居節(jié)點之間有連接的可能性越大，即此節(jié)點有更高的重要性。聚類系數(shù)的計算公式為

這里ki是節(jié)點i的度，節(jié)點j和節(jié)點l是節(jié)點i的鄰居節(jié)點，ajl是節(jié)點i的鄰居節(jié)點之間實際存在的邊數(shù)。例如ajl=1表示節(jié)點i的鄰居節(jié)點j和l之間有一條邊相連;ajl=0表示節(jié)點i的鄰居節(jié)點之間j和l之間沒有邊相連。圖1是網絡中節(jié)點的聚類系數(shù)分布的示意圖。

圖1 網絡中節(jié)點聚類系數(shù)的分布

從圖中可發(fā)現(xiàn)，節(jié)點C的聚類系數(shù)最小，但其確是此網絡的局部中心節(jié)點，其他聚類系數(shù)大的節(jié)點均是網絡的局部邊緣節(jié)點。例如，聚類系數(shù)最大的節(jié)點(A、B、D、E、J、G、F、H、I)均是網絡的邊緣節(jié)點。所以，可得出結論:節(jié)點的聚類系數(shù)和重要性成反比，即聚類系數(shù)越小，重要性越高;換句話說，聚類系數(shù)越小的節(jié)點就越容易成為網絡的局部中心節(jié)點，聚類系數(shù)越大的節(jié)點就越有可能成為網絡的局部邊緣節(jié)點。

網絡中一個最簡單基本的搜索策略就是貪婪算法。定義di為當前節(jié)點的鄰居節(jié)點i到目的節(jié)點的距離，如圖2所示。定義ki為當前節(jié)點的鄰居節(jié)點i的度。貪婪算法選擇di最小的鄰居節(jié)點。這樣離目標節(jié)點最近的點便更加有可能接收信息［8］。盡管如此，貪婪算法在度分布不均勻的無標度空間網絡上并非是最優(yōu)的搜索策略。文獻［9～10］指出利用網絡的非均勻特性設計出的算法優(yōu)于不利用該特性設計出的算法。確實，選擇一個聚類系數(shù)較小的鄰居節(jié)點，即使該節(jié)點離目標節(jié)點很遠，但該節(jié)點存在長程連接的概率仍較大，在下一次傳遞信息時，可將信息沿著長程連接傳遞，接收到信息的節(jié)點有可能離目標節(jié)點較近。例如，在圖3中，源節(jié)點將信息傳遞給節(jié)點2比節(jié)點1要好，因節(jié)點2有一個長程連接，信息傳遞給節(jié)點2后該節(jié)點將信息沿著長程連接傳遞，則節(jié)點4就可以收到信息［11］。

圖2 貪婪算法節(jié)點搜索圖

圖3 最小聚類系數(shù)節(jié)點搜索圖

從圖3中可看到，節(jié)點4比節(jié)點1的鄰居節(jié)點離目標節(jié)點更近。定義網絡中兩個節(jié)點u和v之間的距離d(u，v)為兩節(jié)點之間的歐幾里得距離，設u的坐標為(i，j)，v的坐標為(k，i)，則有

通過上述分析可知，若選擇一個聚類系數(shù)較小的鄰居節(jié)點，則該節(jié)點存在長程連接的概率較大，便有可能更快地找到目標節(jié)點。因此，可思考在無標度空間網絡上結合貪婪算法和最小聚類系數(shù)搜索策略的優(yōu)點，將信息傳遞給聚類系數(shù)較小且離目標節(jié)點較近的鄰居節(jié)點，從而快速地找到目標節(jié)點［12－13］。

2 最小聚類系數(shù)最短距離搜索算法

既然節(jié)點的聚類系數(shù)用ci表示，節(jié)點到目的節(jié)點的距離用di表示，則文中可將這兩個量結合到一起，用ci×di便可設計出最小聚類系數(shù)最小距離搜索策略。該搜索策略在傳遞信息的每一步將信息傳遞給ci×di最小的鄰居節(jié)點，則就可將信息傳遞給聚類系數(shù)較小且離目標節(jié)點較近的鄰居節(jié)點。這種搜索策略在尋找兩個節(jié)點之間的路徑步驟如下:

步驟1 開始選取目標節(jié)點t和源節(jié)點s，且將源節(jié)點s作為當前節(jié)點。

步驟2 從當前節(jié)點s開始，查詢當前節(jié)點s的鄰居節(jié)點是否有目標節(jié)點t。若沒有目標節(jié)點t，則當前節(jié)點選擇ci×di最小的節(jié)點為當前節(jié)點;若有目標節(jié)點t，則搜索終止。

步驟3 每一個節(jié)點只能被訪問一次，若某一節(jié)點被訪問兩次，則搜索失敗。

步驟4 重復步驟2和步驟3，直到當前節(jié)點為目標節(jié)點的任一個鄰居節(jié)點為止。

該搜索策略是最大度搜索策略和貪婪算法的結合，該搜索算法在傳遞信息給鄰居節(jié)點時，不僅考慮鄰居節(jié)點的度，且還要考慮鄰居節(jié)點到目的節(jié)點的距離本文的目的是要設計一個在無標度空間網絡模型上搜索效率高的分散式搜索算法。該算法利用網絡的局部信息來將信息從源節(jié)點s沿著網絡中旳邊傳遞到目的節(jié)點t。每一個節(jié)點均已知目的節(jié)點的位置信息、鄰居節(jié)點的位置信息和鄰居節(jié)點的度。利用這些信息、源節(jié)點和收到信息的每一個節(jié)點，根據(jù)搜索策略，將信息傳遞給其的鄰居節(jié)點，直到信息到達目的節(jié)點為止。

3 仿真結果

為了不失一般性選擇由Barabasi與Albert提出的B－A模型作為網絡基本構造，模型產生方法與文獻［14］相同，其節(jié)點的度分布p(k)具有冪律特性，即p(k) ～k－γ，γ =3，k為節(jié)點度，γ 為冪律指數(shù)。

建立網絡模型后，文中隨機選擇500對節(jié)點作為源節(jié)點和目的節(jié)點來模擬搜索策略。源節(jié)點和每一個收到信息的節(jié)點均按照不同的搜索策略將消息傳遞給自身的鄰居節(jié)點。當信息傳遞到目標節(jié)點的任何一個鄰居節(jié)點時，搜索過程結束。為了避免信息傳遞給已收到過信息的鄰居節(jié)點，文中采取的方法是當節(jié)點收到信息時，將該節(jié)點做一個訪問標記。若一個節(jié)點被訪問過兩次，則該搜索過程失敗。為了分析和比較各搜索策略的搜索性能，對每一種搜索策略，統(tǒng)計其平均路徑長度、成功率、平均搜索時間、網絡覆蓋時間、步數(shù)和訪問節(jié)點數(shù)關系的不同搜索性能。比較了不同的搜索策略在網絡規(guī)模為5 000時的搜索性能的優(yōu)劣程度。

圖4是搜索步數(shù)與累積訪問節(jié)點個數(shù)之間的關系圖?？梢钥闯觯谧畛醯?0步中最小聚類系數(shù)算法已覆蓋了網絡中近65%的節(jié)點，優(yōu)于最小聚類系數(shù)最小距離算法。但隨著步數(shù)的增加，后者覆蓋效果逐漸變好，達到全網絡覆蓋比最大度算法少了近2 000步。

圖4 使用3種算法步數(shù)與訪問節(jié)點數(shù)的關系

圖5所示是隨著網絡規(guī)模的增大，所有搜索策略的平均路徑長度均變長，且最小聚類系數(shù)最小距離搜索策略的平均路徑長度要比最小聚類系數(shù)和隨機游走及貪婪算法的要短。但當網絡規(guī)模增加到一定程度時，最小聚類系數(shù)搜索策略的平均路徑長度要比隨機游走搜索策略的長，這是因為隨機搜索策略的成功率低。

圖5 相對路徑長度與網絡規(guī)模的關系

通過圖6可發(fā)現(xiàn)，隨著網絡規(guī)模的增大，最小聚類系數(shù)最小距離搜索策略的成功率最高，隨機游走搜索策略的成功率最低。隨機游走搜索策略減小了網絡查詢的流量，實現(xiàn)起來也比較方便。但隨機游走搜索策略在選擇鄰居節(jié)點時缺乏偏好性。因此，隨機游走搜索策略的平均搜索步數(shù)較高，搜索的成功率和搜索效率均較低。

圖6 成功率與網絡規(guī)模的關系

圖7比較了在BA無標度的網絡中最小聚類系數(shù)最小距離策略與最小聚類系數(shù)搜索策略和貪婪算法的搜索效果。圖7(a)為隨機選取200對節(jié)點間搜索時間的平均值與網絡規(guī)模的關系，可看出無論是從搜索步數(shù)還是覆蓋步數(shù)而言，最小聚類系數(shù)最小距離搜索策略均是最優(yōu)的，且這種優(yōu)勢隨著網絡的增大而愈加明顯。

4 結束語

文中建立了一個一般性的BA無標度網絡模型。在此基礎上，提出了最小聚類系數(shù)最小距離搜索策略。該搜索策略在搜索過程中的每一步，源節(jié)點和收到信息的節(jié)點會將信息傳遞給聚類系數(shù)最小，且離目的節(jié)點較近的鄰居節(jié)點。隨后，將最小聚類系數(shù)最小距離搜索策略、最小聚類系數(shù)搜索策略、隨機搜索策略和貪婪算法應用到BA無標度網絡上。通過比較與分析可以發(fā)現(xiàn)，在不同情況下，最小聚類系數(shù)最小距離搜索策略的平均路徑長度要比其他搜索策略短，成功率要比其他搜索策略高。因此，得出結論最小聚類系數(shù)最小距離搜索策略更適用于BA無標度網絡。

圖7 3種算法搜索效果比較圖

［1］ 汪小帆，李翔，陳關榮．復雜網絡理論及其應用［M］．北京:清華大學出版社，2006．

［2］ Adamic L A，Adar E．How to search a social network［J］．Social Networks，2005，67(1):35 －37．

［3］ Jae Dong Noh，Heiko Rieger．Random walks on complex networks［J］．Physical Review Letters，2004，92(11):70 － 77．

［4］ 王大驕，汀小帆．無標度網絡的最大－最小度搜索算法［J］．計算機仿真，2007，24(9):161 －194．

［5］ Newman M E J，Watts D J．Renormalization groupanalysis of the small－ world network model［J］．Physics Letters A，1999，263(10):341 －346．

［6］ Boguna M，Krioukov D，Claffy K．Navigability of complex networks［J］．Nature Physics，2009，5(8):74 －80．

［7］ Newman M E J．The structure and function of complex networks［J］．Society for Industrial and Applied Mathematics Review，2003，45(5):167 －256．

［8］ 馮立雪．結合最大度與最小聚類系數(shù)的復雜網絡搜索策略研究［D］．北京:北京交通大學，2011．

［9］ Adamic L A，Lukose R M，Puniyani A R，et al．Search in power－ lawnetworks［J］．Physical Review:E，2001，64(5):91－97．

［10］ Thadakamalla H P，Albert R，Kumara S R T．Search in weighted complexnetworks［J］．Physical Review:E，2005，72(9):111－119．

［11］ Guimera R，Mossa S，Turtschi A，et al．The worldwide air transportation network:Anomalous centrality，community structure，and cities global roles［J］．Proceedings of the National Academy of Sciences，2005，102(11):7794 －7799．

［12］ Albert R，Barabasi A L．Statistical mechanics of complex networks ［J］．Reviews of Modern Physics，2002，74(1):47－55．

［13］ Galstyan A，Musoyan V，Cohen P．Maximizing influence propagation in networks with community structure［J］．Physical Review E，2009，79(345):314 －319．

［14］ Barabasi A L，Albert R．Emergence of scaling in random networks［J］．Science，1999，286(7):509－512．