基于小世界理论的工程信息网络检索的探究

王石奇，赵正旭

（石家庄铁道大学 信息科学与技术学院，河北 石家庄 050043）

在信息爆炸的时代，面对浩瀚如海的大量数据，如何使用户快速精准地获得所需信息，是信息人员考虑并不断研究的方向。对一个数据集做“索引”，就是为了提高对这个数据集检索的效率。正如我们拿到一本新书查看感兴趣的内容时，并不是逐页翻找，而是会先在目录中大致了解要找的信息存在的具体页数，这时书的“目录”正是这本书内容的“索引”。由此可推见对数据集建立索引的重要性［1］。

索引建立之后，搜索过程便是对索引进行检索的过程。在索引中针对关键词进行搜索，得出包含所搜关键词的页面。鉴于并不是每次都搜索大规模网页页面，而是只在索引中进行检索，因此庞大的数据可在很短时间内完成搜索。基于内容的检索服务的核心就是检索模型，正是检索模型决定了信息组织的模式以及查找方法。检索模型包含用户查询的表示、查询匹配策略以及匹配相似性的计算。在查询过程中，我们将查询请求递交至索引，得到对应于所划分独立词的结果集合，再根据查询树的结构对结果集进行重组从而得到总的结果集，对这个总结果集按重要度以及相关性进行排序后，便将最终搜索结果递交给用户查看。因此，结果集的排序质量尤为重要，对排序算法进行不断改进则是我们的研究重点。

1 检索机制

在计算机世界中进行搜索并非难事。由于任何一个对象存在都会留下一定痕迹，只要有这一点微弱的相关联系，哪怕搜寻目标信息位于浩大的数据池中、分布式的系统里、甚至是远在地球另一边的网络服务器中，都可以通过一定的指向信息快速获取。这个搜索核心就是索引。信息索引就是在数据库进行存储数据时，为了更快捷方便地查询或更新相关数据信息，按照一定的时间顺序、属性信息或者对象之间的相关联系，对信息进行排序的一种数据结构。

1.1 搜索定位步骤

通常信息的搜索定位由以下步骤组成：信息收集与预处理、关键词或者主题词的分析以及索引检索处理技术。准备阶段由一种可自由运行的称为“网络爬虫”的程序来进行信息的搜集和存储，同时对所得信息进行预处理。网络爬虫程序在互联网上游走，由网页间的链接关系来不断地进行新地址的搜索，从而完成所有相关网页的搜集和存储工作，并能保证搜集信息的数量及效率［2］。对搜集到信息的预处理包括关键词的提取、重复网页的消除、链接分析和网页重要程度的计算。索引处理阶段首先要建立网页文档信息相关特征，用户根据所属特征记录来快速地检索查询。搜索机制建立检索项索引时一般采用倒排文档的方式，其包括用户检索项、检索项的文档地址及重要度等信息，按照与查询关键词的相关度计算对搜索结果进行排序处理以反馈给用户。

1.2 索引建立

面对海量的网页信息，一个好的分析程序可以将网页中各部分的内容、结构及形式化特点提取出来作为引征值，通过调整各个关键信息对文档贡献的权值来优化查询结果，提高返回值精度。建立索引时，将网络爬虫搜索到的网页进行批量输入到网页分析程式中，并首先对批量网页进行预处理，在经过网页分析程序之后得到hits表。hit可以记录某个词在文档中出现的频次、位置、字体、类型等信息。在网页分析程式中分析文档集合时也同时查看词典现有索引信息，把词典中尚不完善的关键词加入字典内存，对词典总体信息进行及时补充，再启用新索引进行检索。对hits列表合并的同时，按照文档的ID进行排序存储形成前向索引，在查询过程中对结果进行合并时，会用到向前索引这一中间结果，因此需要对索引结果进行存储。按词的ID对前向索引进行重新排序，从而获得需要的倒排文档，与此同时，新的索引信息也被写入词典中［3］。倒排索引作为检索系统的核心，优化的管理可极大地缩短搜索引擎响应时间，确保查询和更新同步进行。

1.3 通用搜索算法

最通用的网络搜索引擎是利用蜘蛛（Spider）算法来建立数据库和搜索机制。Spider程序通过网络上的各种链接自动获取大量网页内容，并按一定的规则分析整理形成数据库。搜索程序以某一特定URL为起点对相关联的Web文档进行浏览访问。访问过程将被记录有关网页文档信息，搜索机制将调用在站点取回的文档所包含的关键信息，依此建立文档索引，同时程序对访问文档所包含的超链接进行新的搜索。可以看出，当新文档被取回，访问信息建立索引，新的超链接又继续被挖掘，如此循环下去，便可完成对大规模网页文档信息的收集工作。蜘蛛算法具体可以描述为：

（1）按照宽度优先抓取的策略从初始或待取URL列表中提取URL；

（2）利用超文本传输协议将URL指向的新网页下载到本地资源库；

（3）提取新网页的关键信息，建立索引文档；

（3）在已获取列表中添加原有URL，并提取新的超级链接；

（4）过滤无价值的或无法索引的网页链接；

（5）将过滤后的URL加入到待取URL列表中，重复以上步骤［4］。

1.4 排列算法及实现

在键入查询条件进行查询时会看到返回很多结果，其前后排列顺序就是根据排列算法来决定的。Rank（排序）是检索过程中最核心的一个模块。在搜索时，对于输入的一条查询关键词或句，搜索引擎将在索引中的查询结果存入文件列表，再计算所查询关键词与文件列表之间的相关度，根据相关度的大小值将文件列表排序，并返回给用户。基本算法是查询关键字在文档出现的次数、关键字在HTML文件中出现的不同位置，分析其结果来赋予文件不同的权值weight，根据计算所得score值，再按照score值的大小顺序排列进行输出即可。图1为Rank算法的流程图，图1中我们把每个单词的基准分数记为initscore，单词在网页中出现频数为totaltimes，increment为该词每出现一次增加的分数［5］。

图1 Rank算法基本流程图

在整合信息或查询信息的过程中，信息过载的现象不乏有之。查询返回的网页链接量是巨大的，但是真正用户进行浏览的却并不多，因此后台对返回结果进行排序，提高网页召回率和质量，将最符合用户要求的页面和链接进行返回，是应该考虑的，同时这也是提高数据定位质量和搜索引擎性能的关键技术之一。

2 小世界

2.1 小世界网络概念

有种类型的复杂网络同时具有典型的规则网络与随机网络同时相似的性质，而这个属性将此类网络与其他网络区分开来，命名为“小世界网络”。“小世界现象”是在社会科学研究中被首度发现的。最为著名的“小世界现象”的例子是由美国科学家Milgram提出的“六度分离（six－degree－of－separation）理论”。Milgram完成了一个著名的实验，他在随机挑选的一些人之间进行信件的传递，通过利用熟人一一传送，很多表面上看起来距离很远的陌生的人实际上可以构成间接关系，最后传达的信件达到预期数量。经统计，陌生人所构成的网络被几条通过熟人的短链连接起来，而这个链的总长度不超过6，这种特征称作“六度分离”。这证明了在这样的一个巨大网络中，两个距离看似很远的节点是可以相连的。这一特征在规则网络中不具有，却是随机网络的一个重要特征。

以规则网络为基础，在规则网络的底层网络中以一定的概率随机挑选两个节点，将两节点连接形成捷径，从而使规则网络向随机网络逐步过渡。当连接增加到一定程度时，形成具有高度的局部集团化和较短的全局平均路径长度的网络，即小世界网络形态。经过许多种试验分析与论证现已证明，万维网以及很多现实中的社会网络、电力网络、生态网络等都属于“小世界网络”。

2.2 小世界网络特性

针对小世界的网络模型，Watts定义了小世界网络的三个特性，描述如下。

第一个特征量是度与度分布。与某个节点相关联的边的条数即为该节点的度，度分布是指正个网络中所以节点具有的度的分布。第二个特性是平均最短路径。平均最短路径描述的是连接两个节点的最短路径长度，整个网络中所有两节点之间最短路径的平均值作为网络的平均最短路径，能很好地描述出网络的连通性。第三个特性是聚类系数。全网聚类系数表示了网络的集聚程度，即群落特性。聚类系数表示了网络中两个节点之间通过一定路径连接在一起的可能性程度。假设网络中节点i与k条边相连，那么这k个节点之间实际存在的边数E与可能存在的边数k（k－1）/2的比就是节点i的聚类系数，对网络中所有节点的聚类系数求平均值就得到全网的聚类系数C［6］。Watts曾对后边两个特点做出说明，高度结构化的网络有较长路径和较大的集聚度，随机网络则有较短路径和很小的集聚度。小世界网络就同时具有与随机网络相近的短路径长度和高聚合度的特征。

3 引入小世界原理的索引机制

为了更高的提升索引的性能，在对数据进行预处理的时候，选择采用更加有效的方法进行处理，结合小世界网络中链接相似性特征，对后台返回值进行过滤［5］。

3.1 链接相似性

在查询网页的相关度时，通常要用到某一网页与其他网页的链接相似性关系。我们将分析网页自身提取到网页p链出的URL记为OUp；又将搜索引擎通过网页的URL进行链接查询，得到多个指向网页p的链入URL，记为IUp。我们将包含网页p的链出，链入和p自身的URL的集合记为Up。在大量的网页中，任意两个网页之间的聚集度可以用链接相似性来衡量，链接相似度表示如下：

σlI（p，pi）与σlO（p，pi）分别表示某网页与第i网页的链入链出的相似度，通过对两者相同的链接URL集合和全部的URL集合做除运算来得到有关相似度的值，对链入链出的相似度取均值可得网页的整体链接相似度。σl值表征了两个网页在所属网页集合中的聚集度，其中σl∈［0，1］。σl大于0时，即两个网页的URL集合有交集，说明p1、p2之间存在无向路径且路径长度不大于2。σl值越大表明两页聚集程度越高，存在直接路径的可能性越大。

3.2 排列算法的改进

我们通过应用蜘蛛算法获取到URL集合，代入到上面提到的小世界相似链接性表达式中进行处理。我们知道，前期分析网页p的源代码得到链出URL，通过程序将这些URL发送给搜索系统以既定的搜索算法进行查询，再将返回的网页链入地址代入式1、2、3中，进行网页链接度σlp（p，pi）的计算。为了求得某网页在全网中的整体链接相似度，还需要代入下式中进行计算。

公式（4）是将某个网页与其他所有网页的链接相似度求均值，得到在全网中的链接相似度的大小。将上式结果带入score（l）＝score＊σlp中，其中n为结果的个数，score为排序算法中的排序分值。链接相似性越大，说明p与其他网页有直接链接的可能性越大，p页的价值越高。图2为使用小世界网络此法相似性方法实现过滤的流程图。

由于搜索得到的网页具有在链接上聚集的特性，在此应用了Web的小世界链接拓扑结构，把链接相似性引入到Rank算法中。在网页的URL之间进行链接相似度计算，得到网页链接度的大小，引入此值将score进行重算，影响衡量网页质量的权值，从而对原Rank算法中的返回信息进行重排。可以看出，对网页的链入与链出集合作相应运算可有效了解到网页聚集度情况，在全部网页中聚集度较大的网页可利用价值较高。按照这个原理，对原有的Rank算法进行了改进，在原有排序结果的基础上进行二次顺序调整。即对搜索到的URL链接程度再次进行分析排序，将得到最相关的URL排列到最前面，从而节省用户搜索时间，提高搜索精度，能达到优化的目的。

图2 排列算法改进流程

4 结论

用户在众多检索结果中找到自己所需信息是一件费时费力的事情。用户逐层浏览查询信息的层次一般只有少数几个页面，而对排列居后的或经过多次链接后的返回信息很少再继续深度查阅。我们针对信息过载的现象，通过在索引中进行检索，筛选不满足条件的数据，对返回信息进行排序，将参考价值比重较大的信息排至靠前位置，方便用户在短时间内查找到自己想要的信息，达到提高查询效率的效果。本文根据小世界网络的特点，利用了小世界相似性方法分析了检索结果的链接聚集度，对搜索结果的排序进行了改进，把最符合用户查询要求的

URL排到最前部分，以节约用户时间。只对相似性方法排序中的链接进行了改进，在对后台建立索引的语义及词性分析上还待进一步研究。此外，工程信息除了布于网络上之外，还大量存储于本地设备中，如何利用小世界特性对本地网络中的大量信息进行保存和查询更新，以及查询所使用的语言工具等，是下一步研究的重点。

［1］李亚楠，王斌，李锦涛.给互联网建立索引：基于词关系网络的智能查询推荐［J］.软件学报.2011，22（9）：1771－1784.

［2］李群.主题搜索引擎聚类算法的研究［D］.北京：北京林业大学.2011.

［3］贾崇，陈玉昌，鲁明羽.一种支持高效检索的即时更新倒排索引方法［J］.数据库与信息处理.2003，（29）：198－201.

［4］张兴华.搜索引擎技术及研究［J］.现代情报.2004，（4）：142－145.

［5］韩红芳，沈雪勤.基于小世界网络的搜索引擎算法研究［D］.天津：河北工业大学.2004.

［6］赵正旭，郭阳，刘贾贾，龙瑞.万维网的小世界效应探讨［J］.石家庄铁道大学（自然科学版）.2010，23（2）：1－6.