藏文Web網絡環境下的搜索策略研究

陳新一，夏建華,2，杜玉祥，萬福成，于洪志

(1. 西北民族大學 教育部重點實驗室中國民族語言文字信息技術實驗室，甘肅 蘭州 730030;2. 河海大學 計算機與信息學院智能科技學與技術研究所，江蘇 南京 210098)

?

藏文Web網絡環境下的搜索策略研究

陳新一1，夏建華1,2，杜玉祥1，萬福成1，于洪志1

(1. 西北民族大學 教育部重點實驗室中國民族語言文字信息技術實驗室，甘肅 蘭州 730030;2. 河海大學 計算機與信息學院智能科技學與技術研究所，江蘇 南京 210098)

該文分析了藏文Web網絡的度分布和最大度優先搜索算法存在的問題，提出了搜索效率更高的二分度搜索算法和雙遍歷器的二分度與最大度同步搜索算法。根據社區劃分原理，設計和構建了藏文Web社區環境下的搜索算法，實驗結果表明，其平均搜索步數和平均查詢信息量都優于實驗中其他搜索算法。

藏文Web網絡;度分布;最大度鏈路;雙遍歷器;社區劃分

1 引言

在復雜網絡中，兩個節點之間的連通路徑可能存在多條。源節點能否找到一條較短或者最小耗費路徑，取決于節點對網絡結構信息的了解，目標節點所使用的搜索算法和對整個網絡實際結構的掌握。Milgram在其小世界實驗中使用了簡單的貪婪算法(Greedy Algorithm)搜索目標節點[1]。由于算法過于簡單，只有一部分的節點搜索能在較少的時間內成功搜索到目標節點。在一個較大規模的網絡中，兩個節點之間存在的連通路徑可能有多條且不同的路徑之間的長度差異可能很大。顯然，在網絡規模較大的網絡中，貪婪搜索算法的搜索效率是很低的。本文以藏文Web頁面鏈接關系網絡為依托，構建其網絡結構模型，分析和研究了其結構特性，提出了效率更高的搜索算法。

2 藏文Web網絡的度分布

在一個Web站點中，網站的首頁可能會是站點的中心節點。首頁對站點內的信息進行了分類，并按類別建立鏈接關系和構建各級子頁面，而用戶需要的主要信息會集中在最低層的子頁面中，即節點度較小的頁面中。換句話說，Web網絡的各個頁面是通過鏈接關系互相連接所構成的。當前頁面的鏈接會指向下一級子頁面，此子頁面可以理解為是對上級頁面的解釋和進一步說明，其頁面鏈接關系如圖1(a)所示。

藏文Web網絡是WWW網絡的一部分，區別僅僅在于頁面顯示的文字，因此，藏文Web網絡具有節點度的冪律分布和小世界特性，以及可以實現快速搜索的特性。根據項目的實際需要，本文對中國西藏網、中國西藏新聞網、中國藏學網進行了Web頁面鏈接關系的抓取，構建了網絡模型，分析了其度分布，其節點度分布如圖1(b)所示。

圖1 藏文Web網絡的節點鏈接關系和節點度分布

分析： 根據圖1(a)中Web頁面的鏈接關系，構建藏文Web網絡模型，計算和分析了網絡節點度和度分布, 圖1(b)表明中國西藏網、中國西藏新聞網、中國藏學網的節點度分布符合冪律分布，也就是說，符合Barabasi和Albert提出的無標度網絡模型或BA無標度網絡模型[2],因此，藏文Web網絡具有小世界特性和可搜索性[3-4]。

3 MDS的最大度鏈路問題

最大度搜索策略(Max Degree Search, MDS)由Adamic等人提出[5-6],在Gnutella網絡模型上，進行了MDS有效性的驗證。MDS在知道每個鄰居節點的度情況下，執行搜索過程： 即每次查詢鄰居節點中未存在目標節點時，選擇度最大的鄰居節點作為下一擴展搜索節點，如圖2(a)所示。從源節點s到目標節點t的搜索，MDS實施了4次節點擴展搜索，查詢范圍可以覆蓋網絡99%的節點，換言之，MDS能夠快速搜索到目標節點的機會很大。相反，從目標節點s到目標節點t的最佳搜索步數為2，即實施了2次節點擴展搜索(擴展節點分別為L1和L2，如圖2(b)所示)，就能搜索到目標節點。另外，當從源節點s搜索到目標節點t時，產生信息量會隨著MDS的覆蓋范圍迅速增長，對網絡的吞吐量造成影響，進而影響搜索效率。因此，MDS具有搜索步數多和查詢信息量大缺點。

圖2 MDS算法

在圖2(b)中源節點s到目標節點t的MDS，可以得到一條由度較大的節點構成的一條鏈路，即最大度鏈路。如果源節點，或者源節點鄰居節點，或者下一個擴展節點的鄰居節點為最大度鏈路上的節點，則MDS的搜索路徑必然進入最大度鏈路，直到將整個最大度鏈路搜索結束才可能進入到其他路徑進行搜索，因此，最大度鏈路會使MDS的搜索效率降低。

4 二分度搜索算法

4.1 算法的提出

根據藏文Web網絡的頁面鏈接關系,如圖1(a)，可知一個站點的主要信息或者詳細信息主要分布在網絡的葉子節點(即度較小的節點)。如果把Web網絡看成一個大的圓，則可以將其劃分為節點度較大的區域，Lager Degree Area,簡稱為LDA(由以Web站點的首頁為中心，及其鏈接的二級、三級頁面等度較大的節點組成)和節點度較小的區域,Small Degree Area，簡稱為SDA(由葉子節點及其距離為1，2等度較小的節點組成)。當使用MDS搜索位于SDA的目標節點時，搜索路徑必然會進入LDA，必然導致搜索效率降低。

根據藏文Web網絡的度分布，如圖1(b)，可知度越小，則節點數量越大。因此，要快速搜索到位于SDA的包含用戶需求的主要信息的目標節點，可以充分利用SDA的節點之間或者度SDA的節點與LDA的節點之間的路徑，如圖3，節點s，L1分別選擇了度較小的節點L1和L2作為下一個擴展搜索節點，就能快速搜索到目標節點t，得到一條最佳搜索路徑，所以，在藏文Web網絡的頁面鏈接關系和度分布的基礎上，提出了二分度優先搜索算法，Bisection Degree Search，簡稱為BDS。

4.2 算法思想

先決條件： 當前節點知道所有鄰居節點的度和二分度(最大度與最小度和的二分之一)。

算法思想： 從源節點出發，查詢目標節點是否存在鄰居節點中，如果存在，則停止搜索；否則，選擇度等于或者最近似等于二分之一度的節點作為下一擴展搜索節點，直到搜索到目標節點為止，或者返回不存在目標節點。

4.3 實驗結果與分析

為了驗證MDS存在的不足和二分度優先搜索的搜索效率高的特性，根據藏文Web網絡節點度的冪律分布，在實驗中構建了小規模網絡10個(即節點數100到1 000)和較大規模網絡(即節點數為 1 000到 10 000)的冪律網絡，另設計了三分之一度、三分之二度、五分之一度、五分之二度、五分之三度、七分之一度、七分之三度、八分之一度和九分之一度優先搜索策略，提取了500組不同網絡中500組數據，包括平均搜索步數，平均查詢信息量和平均回跳次數，如圖3～圖5所示。

分析： 結合圖3至圖5，二分度優先搜索算法在平均搜索步數和平均查詢信息量方面，明顯優于其他搜索算法。平均回跳次數越高表明搜索算法進入到SDA越快，反之越慢。雖然二分度搜索算法的回跳次數比三分之二度優先搜索算法多，但偏差并不多。搜索算法的效率高低首先依賴于平均搜索步數，其次平均查詢信息量，最后是平均回跳次數。因此，二分度優先搜索算法比實驗中的其他搜索算法的搜索效率要高(圖5)。

圖3 搜索算法的平均搜索步數比較

圖3(續)

圖4 搜索算法的平均查詢信息量比較

圖5 搜索算法的平均回跳次數比較

5 雙遍歷器的二分度與最大度同步搜索算法

5.1k遍歷器隨機游走

Qin Lv等人結合廣度優先搜索算法和Adamic等人提出的基于無標度網絡的隨機游走搜索算法[5,7-8]，提出了k遍歷隨機游走搜索算法，簡稱為KRW[9]。k遍歷器隨機游走是源節點從鄰居節點中隨機選取k個鄰居節點將查詢消息的k個副本同時傳遞出去。之后，每個遍歷器各自執行單個遍歷器的隨機游走搜索算法。從搜索的平均情況來看，在T步之后，k遍歷器隨機游走算法所能到達的節點數與單個遍歷器在kT步之后到達的節點數大致相等，因此，k遍歷器隨機游走算法的搜索時間大約為標準隨機游走算法的1/k。

5.2 雙遍歷器的二分度與最大度同步搜索算法

通過對k遍歷器隨機游走的分析，以及鑒于二分度搜索算法能快速搜索SDA和最大度搜索算法能快速搜索LDA的特性，提出和設計了基于雙遍歷器的二分度與最大度同步搜索算法(Maximum and Bisection Degree Search,MBDS)。其算法思想： 從源節點開始，從鄰居節點中選擇兩個鄰居節點作為擴展搜索節點，分別執行二分度優先搜索算法和最大度優先搜索算法。根據算法思想，對其進行了實驗和結果分析，如圖6所示，其中，SMDS表示次大度優先搜索算法。

圖6(a)表明： 從搜索算法的主要評價因素(平均搜索步數)的角度，MBDS的搜索效率明顯優于實驗中的其他搜索算法。由于MBDS中的一個遍歷器使用了MDS，所以，MBDS的搜索信息量會增加，正如圖6(b)中顯示MBDS的搜索信息量只介于MDS和SMDS之間，但明顯是低于BDS的搜索信息量。因此，可以證明MBDS的搜索效率是優于實驗中的其他搜索算法。

圖6 MBDS的平均搜索步數和平均搜索信息量比較

6 社區環境下的搜索算法

6.1 算法思想

最大度搜索算法、二分度搜索算法和雙遍歷器的二分度與最大度同步搜索算法都是從當前節點所掌握的局部信息出發來實現搜索。因此，此類搜索算法都帶有一定的搜索盲目性。為了提高搜索效率，本文結合了社區劃分的原理，將藏文Web網絡劃分成社區節點網絡，該網絡是一個簡化的網絡，網絡中的每個節點代替原來整個社區。如果新的社區節點網絡仍然存在多個社區，則可以再將其劃分成多層社區節點網絡，如圖7所示。

圖7 社區節點網絡

說明： 圖7(a)表示未劃分社區的網絡，7(b)表示劃分社區的網絡，7(c)表示將劃分社區的網絡進行簡化得到的社區節點網絡，每個節點代表一個社區，社區中的每個節點成為社區節點的下屬節點，即采用數據結構體表示。

6.2 算法設計

對網絡進行社區劃分，建立社區節點網絡，存儲節點信息到社區信息臨時存儲區，如社區由哪些節點連接鄰居社區等；將每個社區的邊界節點進行一級本地目錄索引，如表1所示，尤其是存儲邊界節點與邊界節點的連接。社區內部建立連接表，以圖7(c)中的社區5為例，其社區內部節點連接表如表2所示。

表1 社區網絡邊界節點表

表2 社區5的內部節點連接表

Web網絡中每個節點都有各自的唯一標識，即

頁面網址。因此，在劃分社區以后，頁面網址會被記錄到社區節點中，即社區節點的下屬節點。

輸入： 源節點s和目標節點t。

輸出： 目標節點的相關信息，否則，返回不存在該目標節點。

步驟1： 根據社區劃分和頁面標識，判定源節點和目標節點是否同屬于一個社區，如果成立，轉向步驟3，否則，轉向步驟2；

步驟2： 如果當前節點所在社區的邊界節點數存在多個時，則查詢社區之間邊界節點的距離，查詢當前節點的最近邊界節點。如果當前節點所在的社區與目標節點的社區是鄰居社區，且當前節點與目標節點社區直連的邊界節點的距離大于源節點的最近邊界點到目標社區外界點的距離，則選擇最近邊界節點進行擴展搜索，如圖7中，設s為3,t為8，則擴展搜索節點為16；當前節點所在的社區與目標節點的社區存在多條連接時，選擇目標社區中節點度較大的與當前節點社區有連接的邊界節點進行擴展搜索；如果源節點所在的社區與外界社區存在唯一的外界連接，則選擇該連接進行擴展搜索，轉向步驟1；

步驟3： 從目標社區的邊界節點中選擇兩個鄰居節點分別執行最大度優先搜索策略和二分度優先搜索策略，即MBDS。當搜索到目標節點，返回目標節點信息。

6.3 實驗結果與分析

實驗結果表明： 如果忽略網絡社區的劃分和社區邊界節點的存儲結構的初始化的時間復雜度和空間復雜度，從平均搜索步數和平均搜索信息量兩個方面考慮，社區環境下的搜索都優于其他搜索算法(圖8)。

圖8 社區環境下搜索算法的平均搜索步數和平均搜索信息量

圖8(續)

7 結論

本文分析藏文Web網絡的相關結構特征，分析了最大度優先搜索算法存在的問題，在未劃分社區的Web網絡中，設計和構建了二分度優先搜索算法和雙遍歷器的二分度與最大度同步搜索算法，實驗結果表明，搜索效率有明顯改善和提高。結合社區劃分的原理，提出了搜索效率更高的社區劃分環境下的搜索算法。

[1] Watts D J, Strogatz S H. Collective Dynamics of Small-world Networks. Nature[J],1998,393: 440-442.

[2] Barabasi A L, Albert R. Emergence of scaling in random networks. Science[J],1999,286(5439):509-512.

[3] Kleinberg J. Navigation in a small world. Nature[J],2000,406:845.

[4] Kleinberg J. The small-world phenomenon: An algorithmic perspective [C]//Proceeding of the 32nd Annual ACM Symposium on Theory of Computing, New York:2000： 163-170.

[5] Adamic L A,Lukose R M, Puniyani A R,Huberman B A. Search in power-law networks[J]. Phys.Rev. E,2001,64:046135.

[6] Adamic L A,Lukose R M, Huberman B A. Local search in unstructured networks.In S.Bornhodt and H. G. Schuster(eds.),Handbook of Graphs and networks[M], Wiley-VCH,Berlin,2003

[7] Noh J D,Rieger H. Random Walks on Complex Networks[J]. Phys. Rev. Lett., 2004,92: 118701.

[8] Tadic B.Exploring complex graphs by random walks[C]//Modeling Complex System,Garrido P L,Marro J(eds.),AIP Conference Proceedings,2002,661:24.

[9] Lv Q,Cao P,Cohen E.et al.. Search and replication in unstructured peer-to-peer networks[C]//Proceedings of the 22nd IEEE International Conference on Distributed Computing(IEEE ICDCS’02);2002: 1-10.

Study on Tibetan Web Community Search

CHEN Xinyi1, XIA Jianhua1,2, DU Yuxiang1, WAN Fucheng1, YU Hongzhi1

(1. MOE Key Laboratory of Chinese national language informational technology, Northwest University for Nationalities, Lanzhou, Gansu 730030, China;2. Institute of Intelligence of Science and Technology, Nanjing, Jiangsu 210098, China)

This paper analyzes the degree distribution of Tibetan Web community and reveals the defects in the maximum degree-first search algorithm. It proposes a more efficient bisection degree search algorithm as well as a hybrid strategy of combining maximum degree and bisection degree search. According to Community division principle, this paper designs and realizes the search algorithm for Tibetan web community. The result shows that the proposed method are better than other search algorithms in terms of average search steps and average query informativeness.

Tibetan Web networks; degree distribution; maximum degree link; double-walker; community division

陳新一(1957—)，學士，教授，主要研究領域為復雜網絡理論與算法。E?mail：cxyxbmd@sina．com夏建華(1984—)，碩士，主要研究領域為信息檢索與自然語言處理。E?mail：xiajh2008@126．com杜玉祥(1988—)，碩士研究生，主要研究領域為數據庫技術、數據挖掘、神經網絡、機器學習。E?mail：loosedosen@gmail．com

1003-0077(2015)01-0183-08

2013-07-02 定稿日期： 2014-10-28

國家科技支撐計劃(2009BAH41B04)；甘肅省自然科學基金(1107RJZA157)；中央高校基本科研業務費專項資金(2014B33014)

TP391

A