藏文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