更新时间:2023-03-29 15:13
超链分析的基本原理是在某次搜索的所有结果中,被其他网页用超链指向得越多的网页,其价值就越高,就越应该在结果排序中排到前面。
超链分析主要利用数学(主要是统计学和拓扑学)和情报学方法,对网络链接的自身属性、链接对象、链接网络等各种现象进行分析,以便揭示其数量特征和内在规律的一种研究方法。在超链分析中,常将web看成一个有向图进行研究,用G=(V,E)表示,其中:
(1)V:由网页构成的节点集合,p,q∈V,p≠q;
(2)E:由网页间的超链接构成的有向边集合:p→q∈E;
(3)p→q:节点p有一条超链接指向q,其中,p为q的链入网页,称为链源,a为p的链出网页,称为链宿;
(4)出链:p指向其它节点的超链接;
(5)入链:其它节点指向p的超链接;
(6)F(p):节点p所指向的节点集合;
(7)B(p):指向p的节点集合;
(8)节点出度:节点的出链数量;
(9)节点入度:节点的入链数量;
可以这样考虑链接p→q的意义:网页p告诉那些已经访问了网页p的用户,他们可以沿着网页p所创建的超链接对网页q进行访问。这样两个网页之间的超链接可能表明p和q两者具有相关的兴趣主题。p→q表明p对q内容的某种程度的认可:可以说,超链接是p承认q权威性的一种方法。事实上,这个超链接给q的内容提供了某种评价,而这种评价是q的作者没法控制的。
这样,网页作者通过链接的创建和指向选择,为用户提供了有价值的信息引导,使他们能够访问到与原网页主题相关的其它网络资源。这是一个对网页进行评论的自然过程。通过对web图进行观察,节点间存在着类似引文分析的关系:
超链分析算法建立在两个假设之上:
PageRank算法最早由L·Page和S·Brinls为Google原型所提出的一种与查询无关的算法。该算法将超链分析的两个假设进行了引中,并作为其基本思想:
PageRank计算网页A权威度的公式:
公式说明:
阻尼系数d的引入是为了降低了这个概率。阻尼系数d定义为用户不断随机点击链接的概率,所以,它取决于点击的次数,被设定在0和1之间。d的值越高,连续点击链接的概率就越大。因此,用户停止顺链点击并随机冲浪至另一页面的概率在公式中用常数(1-d)表示,这也就是页面本身所具有的权威值。
HITS算法最早由Kleinberg在参与IBM的Clever项目时提出的一种依赖于查询的超链分析算法,该算法的基本思想是:
给定一个宽主题查询Q,HITS算法的基本步骤为:
超链分析作为一种研究超文本环境极为重要的工具,在互联网研究领域具有极其重要的理论研究价值和广泛的应用背景。同时,超链分析的研究从总体上说尚处于一个起步的阶段,已有的研究工作正为这个领域提出越来越多需要解决的问题。以下是目前进行的几个热点研究方向:
在TREC测试集上结合文本进行超链分析研究,可以提高检索的质量,提高幅度可达10%以上,基于熵的超链分析改进就是典型结合示例。
自然语言理解技术可以促进搜索技术的发展。和概念、本体、语义网等技术相结合是超链分析技术的一个新的热点。
Web上不是每个超链都包含了有用的信息,比如广告,站点导航,赞助商,用于友情交换的超链,对于超链分析不仅没有帮助,而且还影响结果。如何有效的去除这些无关超链,也是超链分析算法的一个关键点。
一般的爬行器是根据网页之间的链接信息来采集网页,不考虑网页质量的好坏。如果只想采集高质量的网页,就要按照网页质量的高低依次来进行采集,使得尽可能多地获得高质量的网页。网页链接分析为判断网页的质量提供一种手段。搜索引擎Google就是充分利用PageRank算法来提高Google爬行器的爬行性能。
当用户向搜索引擎提交查询式的时候,搜索引擎返回的结果及其排序依赖于查询式处理器和搜索引擎所使用的算法。从用户的角度看,希望将最相关、最重要的结果放在前面。采用超链分析的排序我们称之为“连通性排名”(Connectivity-Based Ranking)。连通性排名可以分为查询独立模式(Query Independent Schemes)和查询依赖模式(QueryDependent Schemes),前者使用的是著名的PageRank算法,后者使用的是HITS算法。
目前搜索引擎的搜寻结果还不能令人满意。因为用户在提交一个查询式的时候,返回的结果可能属于不同的领域,而用户一般关注的只是其中一个领域。考虑这种情况,有些学者向利用超链分析理论对检索结果进行聚类,将聚类后的结果提供给用户来浏览。
以网页为检索对象,以超链分析为核心算法的网络信息检索,打破了线性存储的限制,为用户提供了比传统的信息检索范围更广泛的检索空间。在搜索引擎的网页爬行方面,超链分析方法可以优化爬行策略,如认为搜索引擎应尽量返回和查询主题相关的权威网页,因此在爬行中应有一个积累和评价机制。在算法中,可以按照深度优先或广度优先的算法从一批起始网页开始收集,当网页提取回来后,采用相应的递归算法来计算出网页的中心值和权威值,以逐步确定该主题的权威网页集合。这样,在爬行时更具针对性、性能更高效。在搜索引擎检索结果的评价和排序方面也是超链分析方法的重要应用领域。
由于资源索引数据库的容量十分庞大,若用户输入一个关键词,有可能会有成千上万条记录相匹配,搜索引擎对如此庞大的结果如何排序,如何把最相关的几十条记录显示出来算法通过网页权威值的运算,给每个网页一个独立于查询的评价数值,搜索引擎就据此对结果集中的记录进行提取和排序,从而大大减轻了用户信息过滤的负担。百度等搜索引擎就采用了超链接分析技术来对检索结果排序。
网页作者在创建链接的过程中并不是随意和无序的,通常会对自身的主题内容和链接需求进行评价,以其通过信息流动来获得网络的认可。虽然超链接创建的边际成本几乎为零,但通常会顾及自身质量和用户期望,他们通常会有选择地优先考虑那些他们认为是重要性或是权威性较高的网页。因此具有相近社会背景或是学科背景的网页会通过超链接逐渐聚集在一起,形成一个个的主题集合。在众多的资源发现技术中,算法占有重要的作用,如实验室的系统、系统研究中心的几户项目都是以算法为核心的。
通过节点和超链接可以方便的扩展主题空间,从而使用户就某一主题形成具有社会学属性的社区提供了平台。可以说,在极度分散和无序的环境中,存在着成千上万的虚拟社区,有些己经以非常清晰的形式表现出来如门户网站中的层次目录结构,但更多的是潜在地、未被发现或定义的。在社区发现的理论研究上主要结合社会网络分析方法,认据此提出了超链接网络理论。在社区的形成机制上主要有等人的随机拷贝机制、等人的偏好性依附机制,他们认为由于超链接的创建包含了人的判断,使得原本离散的、无计划的创建过程并不是随机,而是通过有目的的超链接积累,从局部到全局的逐步构建的过程。
在web中常常有这样的现象,受欢迎的网页点击率一般较高,相应的入链数量也较多。从直观上看,超链分析可以作为判断网页重要性和网络生命力的重要因素之一,这些在超链分析算法产生和改进方面都产生了深刻的影响,如基于随机冲浪模型的PageRank就将“网页的权威性和它的入链数量成正比,入链数量越多就更具权威性”作为重要的实现条件之一,并以此来计算衡量网页权威性的权威值而基于中心一权威的HITS算法则以主题关联为出发点,以中心值和权威值的计算来全面衡量网页存在价值和生命力。以网络社会学为基础的超链接网络理论,则立足于网页作者的社会学属性,将作者的主观判断和理性选择作为评价网络资源的基础。通过评价有助于优化网页设计,尤其是通过提高链接的有效性,如减少悬空链接或死链接来提升自身的认可程度。此外,还可以根据网络链接结构,来析站点的联系程度、集中度,通过网络结构的布局分析合理配置资源,以保证信息传输的顺畅和用户期望的实现。
另一个在网络资源评价研究领域占有十分重要地位的是网络计量学,而超链分析也是其重要研究工具之一,以用来发现核心网站。相对于引文分析法的“影响子”,web网页的影响因子可以简单的对应为该网页的入链数量。虽然这种简单的度量方法在实际应用有诸多限制,如,它通常会使一些具有宽主题的网页获得很高的分值,但这可以通过网站计分法和线性代数方法对此进行改进,如百度创始人李彦宏1996年提出的“人气质量定律”那样,用链接分析法进行统计网站被链接和访问次数,可以作为评价网站和网络信息资源质量的一个指标,再加上相应的链接文字分析,就可以脱离对词频统计的依赖对搜索结果进行的按相关性排序。
用户在搜索关于某些内容的有效信息时,最大的特点是各异性。利用超链分析技术,用户将接受一种根据某种标准进行网页排名的信息服务,从而演变成为各网站想尽办法追求网页排名的商业活动。
海量的网页被收集回来,用姓名、电话、单位名称或网名都可以搜索到许多含有此关键字的信息,这些信息有不少侵权、侵犯隐私、泄露机密的信息,尤其是大量论坛的贴子被收录,不少贴子言论含有攻击的成分。所以如何及时处理掉这些链接又是搜索引擎急需解决的问题。