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

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

?

藏文Web網(wǎng)絡(luò)環(huán)境下的搜索策略研究

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

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

該文分析了藏文Web網(wǎng)絡(luò)的度分布和最大度優(yōu)先搜索算法存在的問題，提出了搜索效率更高的二分度搜索算法和雙遍歷器的二分度與最大度同步搜索算法。根據(jù)社區(qū)劃分原理，設(shè)計和構(gòu)建了藏文Web社區(qū)環(huán)境下的搜索算法，實驗結(jié)果表明，其平均搜索步數(shù)和平均查詢信息量都優(yōu)于實驗中其他搜索算法。

藏文Web網(wǎng)絡(luò);度分布;最大度鏈路;雙遍歷器;社區(qū)劃分

1 引言

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

2 藏文Web網(wǎng)絡(luò)的度分布

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

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

圖1 藏文Web網(wǎng)絡(luò)的節(jié)點鏈接關(guān)系和節(jié)點度分布

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

3 MDS的最大度鏈路問題

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

圖2 MDS算法

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

4 二分度搜索算法

4.1 算法的提出

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

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

4.2 算法思想

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

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

4.3 實驗結(jié)果與分析

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

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

圖3 搜索算法的平均搜索步數(shù)比較

圖3(續(xù))

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

圖5 搜索算法的平均回跳次數(shù)比較

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

5.1k遍歷器隨機游走

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

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

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

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

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

6 社區(qū)環(huán)境下的搜索算法

6.1 算法思想

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

圖7 社區(qū)節(jié)點網(wǎng)絡(luò)

說明： 圖7(a)表示未劃分社區(qū)的網(wǎng)絡(luò)，7(b)表示劃分社區(qū)的網(wǎng)絡(luò)，7(c)表示將劃分社區(qū)的網(wǎng)絡(luò)進行簡化得到的社區(qū)節(jié)點網(wǎng)絡(luò)，每個節(jié)點代表一個社區(qū)，社區(qū)中的每個節(jié)點成為社區(qū)節(jié)點的下屬節(jié)點，即采用數(shù)據(jù)結(jié)構(gòu)體表示。

6.2 算法設(shè)計

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

表1 社區(qū)網(wǎng)絡(luò)邊界節(jié)點表

表2 社區(qū)5的內(nèi)部節(jié)點連接表

Web網(wǎng)絡(luò)中每個節(jié)點都有各自的唯一標(biāo)識，即

頁面網(wǎng)址。因此，在劃分社區(qū)以后，頁面網(wǎng)址會被記錄到社區(qū)節(jié)點中，即社區(qū)節(jié)點的下屬節(jié)點。

輸入： 源節(jié)點s和目標(biāo)節(jié)點t。

輸出： 目標(biāo)節(jié)點的相關(guān)信息，否則，返回不存在該目標(biāo)節(jié)點。

步驟1： 根據(jù)社區(qū)劃分和頁面標(biāo)識，判定源節(jié)點和目標(biāo)節(jié)點是否同屬于一個社區(qū)，如果成立，轉(zhuǎn)向步驟3，否則，轉(zhuǎn)向步驟2；

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

步驟3： 從目標(biāo)社區(qū)的邊界節(jié)點中選擇兩個鄰居節(jié)點分別執(zhí)行最大度優(yōu)先搜索策略和二分度優(yōu)先搜索策略，即MBDS。當(dāng)搜索到目標(biāo)節(jié)點，返回目標(biāo)節(jié)點信息。

6.3 實驗結(jié)果與分析

實驗結(jié)果表明： 如果忽略網(wǎng)絡(luò)社區(qū)的劃分和社區(qū)邊界節(jié)點的存儲結(jié)構(gòu)的初始化的時間復(fù)雜度和空間復(fù)雜度，從平均搜索步數(shù)和平均搜索信息量兩個方面考慮，社區(qū)環(huán)境下的搜索都優(yōu)于其他搜索算法(圖8)。

圖8 社區(qū)環(huán)境下搜索算法的平均搜索步數(shù)和平均搜索信息量

圖8(續(xù))

7 結(jié)論

本文分析藏文Web網(wǎng)絡(luò)的相關(guān)結(jié)構(gòu)特征，分析了最大度優(yōu)先搜索算法存在的問題，在未劃分社區(qū)的Web網(wǎng)絡(luò)中，設(shè)計和構(gòu)建了二分度優(yōu)先搜索算法和雙遍歷器的二分度與最大度同步搜索算法，實驗結(jié)果表明，搜索效率有明顯改善和提高。結(jié)合社區(qū)劃分的原理，提出了搜索效率更高的社區(qū)劃分環(huán)境下的搜索算法。

[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—)，學(xué)士，教授，主要研究領(lǐng)域為復(fù)雜網(wǎng)絡(luò)理論與算法。E?mail：cxyxbmd@sina．com夏建華(1984—)，碩士，主要研究領(lǐng)域為信息檢索與自然語言處理。E?mail：xiajh2008@126．com杜玉祥(1988—)，碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)庫技術(shù)、數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)、機器學(xué)習(xí)。E?mail：loosedosen@gmail．com

1003-0077(2015)01-0183-08

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

國家科技支撐計劃(2009BAH41B04)；甘肅省自然科學(xué)基金(1107RJZA157)；中央高?；究蒲袠I(yè)務(wù)費專項資金(2014B33014)

TP391

A