基于小世界网络的语义检索

龙 瑞

（郑州成功财经学院 河南 451200）

0 引言

当前WWW的发展速度极为惊人，整个网络正在形成一个前所未有的超级信息数据库。2007年3月，由EMC公司赞助IDC进行的研究，题为《数字宇宙膨胀：到2010年全球信息增长预测》研究结果称，2006年全球产生的数字化信息总量达1610亿吉比特，其中原创信息为400亿吉比特。而到2010年，全球产生的数字化信息总量有望达到9880亿吉比特。

然而目前的网络搜索引擎平均只能检索25%的可获取信息，其搜索结果常含有大量无用信息。另一方面，由于数字化信息具有形式复杂和内容分散的特点，其结构的关联性和数据的兼容性直接影响着数字化信息资源的有效管理和利用。这就导致传统数据挖掘技术对数字化信息进行挖掘的效果总是不尽如人意。造成这些问题的一个重要原因是大量的数字化信息只能人工解析，机器自动处理的能力很弱。因此Tim Berners-Lee提出了语义网的思想，即Web上定义的链接数据不仅能够显示，而且还应该是机器可理解的，也就是说可以被机器自动地处理、集成和重用。

1 语义网的概念

Tim Berners-Lee并没有就语义网的数学问题进行严格定义，通过与万维网的对比，他给出的描述是：语义网并非一个从无到有、孤立发展的万维网，而是对万维网的扩展与延伸，语义网信息具有定义良好的含义，计算机可以凭借概念的定义申明和逻辑推理规则寻找到资源对象的含义，从而使得人—机之间和机—机之间合作处理更加有效；数据通过语义网中的定义和链接可以以更有效的方式实现各种检索、重用和集成。

2 小世界网络模型

2.1 小世界效应

1929年，匈牙利作家F·Karinthy最早提出了“小世界现象”的论断[3]。他认为，地球上的任何两个人都可以平均通过一条由六位联系人组成的链条而联系起来。而后，在20世纪60年代，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆通过设计一个连锁信件实验，提出了著名的“六度分割”假说，即“小世界现象”。这体现了一个似乎很普遍的客观规律：在如今的信息化时代，人们之间的关系已经完全社会化，任何两位素不相识的人都可能通过“六度空间”产生必然联系或关联。

“六度分离”在学术上称为“小世界现象”或“小世界效应”。小世界效应的精确定义还在讨论中，目前一个较合理的解释是：若网络中两点间的平均距离 L随网络大小（网络中结点数 N）呈对数增长，即 ～ln L N，且网络的局部结构上仍具有较明显的集团化特征，则称该网络具有小世界效应。

2.2 小世界网络

小世界网络模型是Watts和Strogatz在1998年提出的基于人类社会网络的网络模型，它通过调节一个参数可以从规则网络向随机网络过渡。

对于小世界网络的理论研究目前还处于探索阶段，大致可分为两类：一是随机网络；二是著名的W—S 小世界网络模型及转化类型。根据W—S 的小世界网络模型，可以认为Internet是一个小世界网络，它具有小世界网络的特征。因此，我们在分析Internet网络特征后，可以运用小世界原理来改善Internet的信息交流过程：利用小世界网络特征来减少Internet上信息传播的路径长度和提高网络的可靠性；研究Internet的鲁棒性和脆弱性，重视网络关键结点在传播中的作用；并逆向运用小世界原理阻止计算机病毒在Internet上蔓延。对小世界网络的研究，意义不仅在于它从网络的抽象角度重视和描述了现实中的小世界现象，而且在于它提供了如何理解从局部特征涌现出系统结构的新的线索。

3 基于小世界网络的语义检索

3.1 网络节点及其相关定义

本文是基于小世界网络和语义网理念研究信息检索的，由以上对小世界网络的介绍可知，Internet具有小世界网络的两个特性：小世界效应 (～ln)L N和集团化特征 C。在研究中，我们把Internet视为小世界网络，把网页作为小世界网络模型中的节点，网页的URL、name、type、language等定义为节点的属性，而连接节点的边则是根据语义的相似或相近度来定义的，这样就形成了邻居节点和相关节点，下面对这两类节点简单定义：

邻居节点：如果两个节点iPjP直接相联，那么它们互为邻居；

相关节点：如果一个节点iP通过其它节点kP与一另一个节点jP相联并交互，那么jP被定义为iP的一个相关节点。

3.2 Ontology中节点属性的定义

Ontology是一种能在语义层次上描述知识的概念模型，其目的在于以一种通用的方式来获取领域中的知识，提供对领域中概念的共同一致的理解，从而实现知识在不同的应用系统之间的共享和重利用[6]。在研究中，以网页作为节点，网站和超链接形成重要节点；用语义分析网页中的数据和信息，根据相似偏好和行为形成节点簇。Ontology对这些重要节点和节点簇进行描述与分类，以形成不同的系统，便于机器理解这些节点包含的数据和信息，从而提高信息检索的查全率和查准率；前面我们定义连接节点的边是根据语义的相似或相近度，这些连接网页的边分为双向的和单向的；超链接是网络中的捷径，即小世界网络中的“断键重连”。下面我们将用实例解析。

4 结束语

本文简要地介绍了语义网理念和小世界网络，指出了当前Internet信息检索的低效性。针对这种状况，我们提出了基于语义的小世界网络节点关联的信息检索，根据Internet具有小世界网络的特征，用语义定义网络中的节点以及节点根据自身的资源搜索与自己具有相似偏好和行为的节点形成邻居节点和相关节点，最终形成具有相似语义的节点簇，提高了信息检索的查全率和查准率，实现以较小的代价检索到所需的数据这一目的。

[1]美国EMC.《数字宇宙膨胀：到2010年全球信息增长预测》2007.3

[2]T.Berner-Lee， J.Henller， and O.Lassila.The SemanticW eb[J].Scientific American，May 2001.

[3]Braun T.Hungarian priority in network theoty[M].Science，2004：1745.

[4]Travers J，M ilgram S.An experimental study of the small world problem[M].Sociometry，1969：425——443.

[5]Watts DJ，Strongatz SH.Collective dynam ics of small-world networks[J].Nature，1998，393：440-442.

[6]刘耀.领域Ontology自动构建研究[D].北京大学博士后出站报告，2007.