链接结构.pdfVIP

分析 Web 链接结构 李宇 20 世纪 90 年代兴起的 Word Wide Web （WWW ）已经成为了人类有史以来的最 大规模的信息宝库：几乎一切人类知识都以 Web 的方式呈现在了互联网上。如 何在如此大规模的信息中进行快速有效的搜寻？是否能够从中挖掘出更多的隐 藏信息来更好的了解人类社会？成为摆在人们面前的一道难题。 本文试图对基于链接分析的相关 Web 挖掘技术作一个介绍。接下来的文章将如 此组织：第一部分介绍链接结构分析形成的理论基础；第二和第三部分分别介绍 两种著名的链接结构分析技术 PageRank 和 HITS ；第四部分试图分析在现有的链 接分析技术上存在的问题；最后给出人们在原有的理论上做出的改善。 1. 链接结构分析的理论基础 链接结构分析形成的理论基础是形成于 1950 年左右的社会网络理论。 社会网络理论建立起一种称之为社会网络的模型：它是一个有向图，图中的点代 表论域中的实体，有向边代表实体之间的关系。例如 IR 领域中的对论文做引用 分析就可以建模为这样一张社会网络图上：图中的点代表每一篇论文（即实体）， 论文之间如果存在引用关系则存在一条有向边，从引用者指向被引用者（即实体 与实体之间的关系）。 社会网络模型由于是以图的形式表现，那么它可以以一个矩阵的形式被定义出 来。即存在 n 个实体的社会网络可以用一个 n ×n 的矩阵E 来表示，E [i,j ]=1 当且 仅当实体 i 到实体j 存在一个关系。 以论文引用分析为例，在社会网络图上可以定义如下的概念 Prestige 威望（Prestige ）是第一个在社会网络图上定义的概念，它反映了某篇论文的重 要程度。某篇论文 v 的威望通常是通过其在社会网络图上的引用了它的论文的威 望来衡量的，即 p [v] ∑E [u,v]p [u] ∑E T [v,u]p [u] u u 公式 1 按照公式 1 ，我们可以从一个初始的威望向量 p ，根据社会网络计算出引用发生 之后的威望向量p’ ，如公式 2 所示 p E T p 公式 2 Centrality 在社会网络的可以定义中心（Centrality ）的概念。它表示出社会网络图中最重要 的那些点。定义中心需要先明确距离，两个实体 u 到 v 的距离d(u,v)可以定义为 从实体 u 沿边行走到达 v 经过的边数的最小值。接下来可以定义实体 u 的半径为 r (u) max v d (u,v) 。这样，整个图的中心就是那些具有最小半径值的点，即 min u r (u) 。在论文引用的例子里面，这些中心点就恰好代表了这个领域中最有 影响力的论文。 Co-citation 如果论文 u 同时引用了论文v 和 w ，那么就称v 和 w 被 u 同引用。如果论文v 和 w 被很多论文同引用，就证明它们之间的联系紧密。同引用性（Co-citation ）正 是一个社会网络图上表达论文是否被同引用的概念。 (E T E )[v, w] ∑E T [v,u]E [u, w] ∑E [u,v]E [u, w] | {u : (u,v) ∈E , (u, w) ∈E } | u u 公式 3 从公式 3 中我们发现，我们可以通过E T E 轻松的得到社会网络图中任何两篇论文 之间的同引用性。 社会网络理论可以应用在很多领域，除开论文引用分析，只要是能够建立其社会 网络模型的领域都可以应用社会网络理论，比如对娱乐明星及其之间的关系建模 可以发现其中的合作关系，又比如对商业交易进行建模，可以用来发现其中主导 市场的产业的企业等等。在 Web 出现后，人们将社会网络的理论又一次应用到 了Web 的链接结构分析中，用来挖掘Web 中所隐藏的信息。关于社会网络的理 论，可以参考[3]。 2. PageRank