基于小世界網絡的語義檢索

龍 瑞

（鄭州成功財經學院 河南 451200）

0 引言

當前WWW的發(fā)展速度極為驚人，整個網絡正在形成一個前所未有的超級信息數據庫。2007年3月，由EMC公司贊助IDC進行的研究，題為《數字宇宙膨脹：到2010年全球信息增長預測》研究結果稱，2006年全球產生的數字化信息總量達1610億吉比特，其中原創(chuàng)信息為400億吉比特。而到2010年，全球產生的數字化信息總量有望達到9880億吉比特。

然而目前的網絡搜索引擎平均只能檢索25%的可獲取信息，其搜索結果常含有大量無用信息。另一方面，由于數字化信息具有形式復雜和內容分散的特點，其結構的關聯(lián)性和數據的兼容性直接影響著數字化信息資源的有效管理和利用。這就導致傳統(tǒng)數據挖掘技術對數字化信息進行挖掘的效果總是不盡如人意。造成這些問題的一個重要原因是大量的數字化信息只能人工解析，機器自動處理的能力很弱。因此Tim Berners-Lee提出了語義網的思想，即Web上定義的鏈接數據不僅能夠顯示，而且還應該是機器可理解的，也就是說可以被機器自動地處理、集成和重用。

1 語義網的概念

Tim Berners-Lee并沒有就語義網的數學問題進行嚴格定義，通過與萬維網的對比，他給出的描述是：語義網并非一個從無到有、孤立發(fā)展的萬維網，而是對萬維網的擴展與延伸，語義網信息具有定義良好的含義，計算機可以憑借概念的定義申明和邏輯推理規(guī)則尋找到資源對象的含義，從而使得人—機之間和機—機之間合作處理更加有效；數據通過語義網中的定義和鏈接可以以更有效的方式實現各種檢索、重用和集成。

2 小世界網絡模型

2.1 小世界效應

1929年，匈牙利作家F·Karinthy最早提出了“小世界現象”的論斷[3]。他認為，地球上的任何兩個人都可以平均通過一條由六位聯(lián)系人組成的鏈條而聯(lián)系起來。而后，在20世紀60年代，美國哈佛大學社會心理學教授斯坦利·米爾格蘭姆通過設計一個連鎖信件實驗，提出了著名的“六度分割”假說，即“小世界現象”。這體現了一個似乎很普遍的客觀規(guī)律：在如今的信息化時代，人們之間的關系已經完全社會化，任何兩位素不相識的人都可能通過“六度空間”產生必然聯(lián)系或關聯(lián)。

“六度分離”在學術上稱為“小世界現象”或“小世界效應”。小世界效應的精確定義還在討論中，目前一個較合理的解釋是：若網絡中兩點間的平均距離 L隨網絡大?。ňW絡中結點數 N）呈對數增長，即 ～ln L N，且網絡的局部結構上仍具有較明顯的集團化特征，則稱該網絡具有小世界效應。

2.2 小世界網絡

小世界網絡模型是Watts和Strogatz在1998年提出的基于人類社會網絡的網絡模型，它通過調節(jié)一個參數可以從規(guī)則網絡向隨機網絡過渡。

對于小世界網絡的理論研究目前還處于探索階段，大致可分為兩類：一是隨機網絡；二是著名的W—S 小世界網絡模型及轉化類型。根據W—S 的小世界網絡模型，可以認為Internet是一個小世界網絡，它具有小世界網絡的特征。因此，我們在分析Internet網絡特征后，可以運用小世界原理來改善Internet的信息交流過程：利用小世界網絡特征來減少Internet上信息傳播的路徑長度和提高網絡的可靠性；研究Internet的魯棒性和脆弱性，重視網絡關鍵結點在傳播中的作用；并逆向運用小世界原理阻止計算機病毒在Internet上蔓延。對小世界網絡的研究，意義不僅在于它從網絡的抽象角度重視和描述了現實中的小世界現象，而且在于它提供了如何理解從局部特征涌現出系統(tǒng)結構的新的線索。

3 基于小世界網絡的語義檢索

3.1 網絡節(jié)點及其相關定義

本文是基于小世界網絡和語義網理念研究信息檢索的，由以上對小世界網絡的介紹可知，Internet具有小世界網絡的兩個特性：小世界效應 (～ln)L N和集團化特征 C。在研究中，我們把Internet視為小世界網絡，把網頁作為小世界網絡模型中的節(jié)點，網頁的URL、name、type、language等定義為節(jié)點的屬性，而連接節(jié)點的邊則是根據語義的相似或相近度來定義的，這樣就形成了鄰居節(jié)點和相關節(jié)點，下面對這兩類節(jié)點簡單定義：

鄰居節(jié)點：如果兩個節(jié)點iPjP直接相聯(lián)，那么它們互為鄰居；

相關節(jié)點：如果一個節(jié)點iP通過其它節(jié)點kP與一另一個節(jié)點jP相聯(lián)并交互，那么jP被定義為iP的一個相關節(jié)點。

3.2 Ontology中節(jié)點屬性的定義

Ontology是一種能在語義層次上描述知識的概念模型，其目的在于以一種通用的方式來獲取領域中的知識，提供對領域中概念的共同一致的理解，從而實現知識在不同的應用系統(tǒng)之間的共享和重利用[6]。在研究中，以網頁作為節(jié)點，網站和超鏈接形成重要節(jié)點；用語義分析網頁中的數據和信息，根據相似偏好和行為形成節(jié)點簇。Ontology對這些重要節(jié)點和節(jié)點簇進行描述與分類，以形成不同的系統(tǒng)，便于機器理解這些節(jié)點包含的數據和信息，從而提高信息檢索的查全率和查準率；前面我們定義連接節(jié)點的邊是根據語義的相似或相近度，這些連接網頁的邊分為雙向的和單向的；超鏈接是網絡中的捷徑，即小世界網絡中的“斷鍵重連”。下面我們將用實例解析。

4 結束語

本文簡要地介紹了語義網理念和小世界網絡，指出了當前Internet信息檢索的低效性。針對這種狀況，我們提出了基于語義的小世界網絡節(jié)點關聯(lián)的信息檢索，根據Internet具有小世界網絡的特征，用語義定義網絡中的節(jié)點以及節(jié)點根據自身的資源搜索與自己具有相似偏好和行為的節(jié)點形成鄰居節(jié)點和相關節(jié)點，最終形成具有相似語義的節(jié)點簇，提高了信息檢索的查全率和查準率，實現以較小的代價檢索到所需的數據這一目的。

[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.