网络搜索链接技术的研究.pdf

《网络搜索链接技术的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、总第198期2010年第12期舰船电子丁程ShipElectronicEngineeringV01．30No．129网络搜索链接技术的研究。官斌(武汉市74223信箱武汉430074)摘要介绍了近几年来互联网络搜索中链接分析技术的进展．并为进一步的研究反对易式出了几个可行的方向。关键词Web搜索；链接分析；PageRank算法；HITS算法；搜索引擎中图分类号TP393ResearchontheLinkAnalysisintheInternetSearchGuanBin(P．()．Box74223．Wuhan430074)AbstractWefirstbrieflyreviewsomemai

2、nlinkanalysistechnologiesforwebsearchinrecentyears。andthenwepointoutseveralpossibledirectionsforthefurtherresearch．KeyWordsWebsearch，linkanalysis。PageRank，HITS，searchengineCImNumb酐TP3931引言随着互联网络的日益迅猛增长，互联网络已成为世界上规模最大的信息源之一。在如此巨大的数据海洋中寻找用户所需要的信息已不是人力所能胜任的工作了，因而搜索引擎已经作为互联网上最有效的信息获取T具而为人们广泛接受。不同于传统的信息

3、检索(图书馆资源检索)，互联网不仅包含了大量的内容信息(包括文字、图像、声音，视频)，而且还包含了复杂的结构信息(如超链接关系，网站的组织结构等等)。对互联网结构信息的利用能够很大程度上决定一个搜索引擎性能的好坏。冈此．链接分析(1inkanalysis)已成为互联网检索领域一个很热的话题．吸引了众多研究者的关注。本文介绍了从1998年以来链接分析技术的进展，并在此基础上指出了进一步的研究方向。2链接分析的兴起：两大经典算法的提出1998年是巨联网搜索历史』：最自

4、纪念意义的一年。链接分析的两大经典算法都于该年提出：HITS和PageRank。正是由于链接分析的运用，是互联网搜索的准确程度有

5、了一个质的飞跃。下面我们简单介绍一下这两个算法。2．1PageRank算法PageRank：2。是由斯坦福大学的两个博士研究生SergeyBrin和LawrencePage于1998年提出。Google即为该论文的原型系统，如今已发展成为世界上最好的搜索引擎。PageRank算法的基本思想相当简单。Pager—ank认为．每个网贞的重要程度是不一样的。如果一个网贞被很多网贞指向，那么该网页很可能非常重要；另外。一个重要的网页所指向的网页也很可能非常重要。PageRank的基本原理可以用马尔可夫随机游走模型来解释。PageRank模仿一个用户在互联网上浏览行为．在当前时刻．该用户以一定的概率q

6、跳转到任意一个网贞。或者以概率1一g跳转到当前网贞所指向的某一网页。该过程可以用一个马尔可夫链来建模．互联网中的每一个网页就是马尔叮丈链中的一个状态。该马尔H，夫链平·收稿日期：2010年7月25【j．修回日期：2r)10q-8月29日作者简介：订斌．男．Ii稃师．研究力‘f{l】：计锋机软f，I臀理。10官斌：网络搜索链接技术的研究总第198期稳时每个状态停留的概率即反映了相应网页的重要程度。下面我们介绍一下PageRank算法的具体实现。如果整个网络有卯个网页。将这个网络看成有行个节点的有向图．图上的每条有向边代表了互联网上一个超链接。该图的邻接矩阵A记为：．fl如果有超链接从网页i指向

7、J，，、一”10其他情形⋯将邻接矩阵的每一行行和归一化，我们可以得到该随机跳转(马尔可夫链)的概率转移矩阵万。为了保证该马尔可夫链能够收敛到一个平稳状态，该马氏链必须满足非周期不可约两条性质。然而对于一个实际的网络，并不一定能够满足这两个条件。这里PageRank算法对概率转移矩阵A进行了平滑处理丙一4+(1一口)U(2)其中U是一个7"／*I"1的矩阵，并且每一个元素都为1／n。其中口是一个经验常数嵋j，建议使用0．85。进行了平滑之后，就能够确保随机跳转的平稳状态存在且唯一。将该马氏链平稳状态每个节点停留概率记为7rf，那么兀就体现了网页的重要程度。兀越大，该网页越重要。死可以由如下公式

8、计算得到丁r万一兀其中(3)尢一[7c1，7c2，⋯，7【。](4)也就是说，整个网络的PageRank向量就是平滑后的概率转移矩阵最大的左特征向量。由于邻接矩阵的规模相当庞大(对于现在的互联网，网页的数量都在十亿的规模)，因此人们一般不是直接求万的特征向量，而是采用如下的幂法迭代7c‘女+1)=7c【‘’万(5)直到收敛为止。2．2HITS算法不同于PageRank算法用一个量来衡量一个网页的重要性，HIT