首页 . 管理学 . 情报学 . 信息检索 . 检索相关性 . 检索结果排序 . SALSA

SALSA算法

/stochastic approach for link-structure analysis algorithm/
条目作者余传明

余传明

最后更新 2022-12-23
浏览 157
最后更新 2022-12-23
浏览 157
0 意见反馈 条目引用

网页排序算法。

英文名称
stochastic approach for link-structure analysis algorithm
提出者
R.伦佩尔、S.莫兰
提出时间
2000
所属学科
情报学

由以色列学者R.伦佩尔[注]S.莫兰[注]于2000年在第9届国际互联网大会上提出。它以HITS算法为基础,因此中国有学者将其归并到近似HITS算法的一类。

在SALSA算法中,伦佩尔和莫兰仍然沿用了HITS算法的两个基本概念,对每一个网页赋予两个指标值:权威值(authority)和枢纽值(hub)。权威值越高则该网页与给定的主题越相关,这样的网页称为权威页(authorities);枢纽值高的网页中包含较多指向权威页的链接,这样的网页称为枢纽页(hubs)。同时,SALSA算法更强调Web用户浏览的随机性以及向前浏览网页的直觉知识,借鉴了PageRank算法的随机漫游的思想,同时摒弃了HITS算法中枢纽值与权威值相互增强的方法。

首先,用基于文本的搜索引擎检索得到查询结果,取排名最高的前个网页形成根集,其中一般取值为200。其次,扩充根集,分两步进行:一是将所有中所指向的页面扩充进去,该扩充在数量上没有限制;二是将指向中的每一个页面的链接页面取其中任意个页面,将其扩充到原来的中形成基本集去除无关链接(如内在链接、CGI脚本链接、广告和赞助商的链接等),只保留提供信息的链接,形成集合

从集合中构造二分无向图其中分别为定义的两条马尔可夫链。表示枢纽链(hub),即该链中的网页包含出链,且这些出链指向内其他节点;表示权威链(authority),即该链中的网页包含内其他节点指向的入链;表示枢纽链和权威链的连接规则

通过定义矩阵的方法分别定义枢纽矩阵和权威矩阵,并求其特征向量,即可找出两条马尔可夫链的静态分布。其中权威矩阵中值大的网页即为所求的权威页。

首先,从SALSA算法步骤中可以看出,SALSA算法对HITS算法做了改进。相比于HITS算法,SALSA算法在计算上更轻量。由于SALSA算法和HITS算法都是在查询时被执行,减少计算量可以较大程度地减少搜索引擎的反应时间,提高用户体验。

然后,相比于HITS算法,SALSA算法更不易受TKC(tightly knit community,包含少量高度相互关联的网页拓扑结构)的影响。而在HITS算法中,缺少TKC会在查找权威页时产生消极影响。

  • LEMPEL R, MORAN S.Salsa: the stochastic approach for link-structure analysis.ACM transactions on information systems (tois),2001,19(2):131-160.

相关条目

阅读历史

    意见反馈

    提 交

    感谢您的反馈

    我们会尽快处理您的反馈!
    您可以进入个人中心的反馈栏目查看反馈详情。
    谢谢!