第8章 链接结构分析子系统设计及核心算法

1、第 8 章 链接结构分析子系统设计及核心算法本章内容：² 万维网链接结构图及特性；² 链接结构分析方法的形式化基础；² 链接结构分析Page Rank 算法、HITS 算法；² 链接结构分析结果在搜索结果排序中的应用。8.1 万维网链接结构图万维网的链接结构可用有向图来描述，网页是节点，超链接是有向边。从源网页指向目的网页的超链接，为源网页的“出链接”，为目的网页的“入链接”。l 节点 A-H 表示网页；l 链接关系用有向边来表示；l 网页 A、B、C 之间的双向边，表示三个网页之间相互链接；l 网页F与G各自有一个指向自身的有向边。链接结构关系图的邻接

2、矩阵描述。邻接矩阵是用来描述图中节点邻接关系的一种方式，设n为链接结构图 Graph 的节点规模，则邻接矩阵 M 是一个n*n的矩阵，其中某个元素 mi,j的取值满足：图 8.1 所示链接结构图，其邻接矩阵如下：万维网链接图GWeb (V, E) V：节点集合，V = v1 , v2 , v3 ， ， vn，节点数|V| = n ; E ：边集合， E = e1 , e2 , e3 ， ，em，边数|E|=m 。将万维网的整个链接结构图作为对象来研究不仅对理解万维网的各种属性有直接的意义，同时还对搜索引擎领域的相关算法研究也有着重要的帮助。很多实验和观察促进了万维网链接图结构的研究。针对图 G

3、Web ( V , E )，研究；² V、E的规模；² 拓扑结构；² 节点入度、出度分布。图G ( V , E）的某节点所关联的边数称为该节点的“度”。对于图 GWeb ( V , E）而言，某节点的入度就是指以该节点作为目的网页的超链接数（该节点入链接数）；某节点的出度则是指以该节点为源网页的超链接数（该节点出链接数）。8.1.1 万维网链接图的规模GWeb (V, E）规模难以统计(1) 图中的节点存在形式复杂；² 非自由访问的网页（网页对用户访问加以限制，如采取登录策略等）；² 自由访问的网页；² 传统形式的静态页面；²

4、; 随用户查询需求在服务器端实时生成的动态页面；² 用 Ajax 技术生成的 URL 相同但内容千差万别的页面；(2) 超链接的界定，存在诸多困难； “博客日历”，每个日期都是一个超链接。服务器端自动生成的超链接VS网页作者手工编辑添加的链接。GWeb ( V , E）的节点集合规模² 通过域名注册服务商可统计网站、域名数量且较为准确；² 统计网站涉及的网页数目就会面临上面提到的问题；² 研究中通常用搜索引擎的索引规模来估算万维网链接图的节点规模；² 没被任何一个搜索引擎收录的网页，被用户访问到的可能性微乎其微；² 2008年7月，谷

5、歌索引量1万亿网页，一定程度上反映了GWeb (V, E）节点集合的规模。GWeb ( V , E）的边集合规模² 估计边集合规模更困难；² 超链接的添加不需要登记、备案，各大搜索引擎也很少公布统计数据；² 只能通过实验性万维网语料库的相关数据对GWeb (V , E）的边集合规模有一个概括性的认识；² AltaVista 语料库，链接关系图包含 2.03 亿个网页、14.66 亿条链接。 ² Clueweb09 语料库，链接关系图包含的节点数为 1040 809705个，对应的出链接数为7944351835个。² sogouT语料库

6、，链接关系图包含1.39 亿个网页、33 . 4亿条链接。从这些语料库，可以估计，边集合的规模要大于节点集合的规模，约为节点集合规模的几到几十倍。8.1.2 万维网链接图的连通情况定义：导出子图给定 G=(V, E)，如果存在另外一个图 G/=(V/,E/)，满足V/包含于V，E/包含于E，则称G/是G的一个子图。特别地，如果V/包含于V，且E/包含了在节点子集V/之间的所有边，则称G/是G的导出子图。定义：强连通子图给定一个有向图，该有向图的一个强连通子图是指由一部分节点组成的一个导出子图，对于该子图中其中的任意两个节点u和v，都存在一条路径使得从u可以访问到v。性质：1、一个有向图中可有多

7、个强连通子图。2、强连通子图之间不存在公有节点；否则可以合二为一。对万维网连接图，每个强连通子图都代表着构成该子图的节点是相互连通的，通过超链接通过一个网页可访问另一个。定义：弱连通子图给定一个有向图，该有向图的一个弱连通子图是指由一部分节点组成的一个导出子图，对于该子图中其中的任意两个节点u和v，都存在一条无向路径使得从u可以访问到v。对于万维网链接图，重点考察其包含的强、弱连通子图的规模分布情况，借此了解整个链接图的拓扑结构和连通情况。2000年，Broder的研究成果，万维网链接结构图的强、弱连通子图的规模分布情况如下图所示。l 图中，横轴为连通子图规模，纵轴为连通子图数量；l 横轴、纵

8、轴使用对数坐标轴。l 可以看出强连通子图、弱连通子图的规模分布规律基本相同；l 设连通子图规模为Size，具有规模Size的连通子图的数目Number近似满足；指数形式表示为：几点结论：l 规模大的连通子图数目远小于规模小的连通子图数目。l 规模最大的连通子图所覆盖的网络资源数量，占网络资源总量中相当比例。l 基于链接结构抓取，很难抓取到网络环境中所有数据，但通过抓取规模较大的连通子图可获取最主要部分的数据。规模最大的强连通子图，其节点规模达到560余万，此连通子图在 Broder研究的网页集合总规模中占有近28%的网页。以此连通子图为中心，考察其他网页与此连通子图的链接关系，可以对整个网络页

9、面的链接结构关系有一个清晰的认识。根据Broder的研究结论绘制的万维网链接结构示意图如下图所示。Core部份规模最大的强连接子图；IN部分所有链接到Core中网页，且同时不被Core中的网页所链接的网页集合；OUT部分所有被Core中的网页所链接，且同时不链接到Core中网页的网页集合；Others部分剩余的网页集合。万维网链接和连通结构概貌l 从IN中任何网页，都可以链接到Core中网页，进而可访问OUT中任何网页。l IN、Core、OUT之外网页，一部份与IN、OUT有链接关系，另一部分与IN、Core、OUT不相连的孤立点或点集合，规模约为所分析网页总数的8.2%。l 万维网链接结构

10、以Core为核心，构成了“领结”形式的结构。8.1.3 万维网链接图的入度和出度分布万维网链接图的入度、出度分别反映了某节点被其他节点链接，以及链接到其他节点的情况。万维网链接图 GWeb (V,E)的入度、出度分布符合幂律；入度为Indegree 的网页数目 N ( Indegree ）近似满足：出度为Outdegree 的网页数目 N ( Outdegree ）近似满足：其中、均为值大于零的参数，而C与 C/为常数。Broder的实验结果如下图所示。8.2 超链接结构分析的基础超链接：两个网页或网页的两个不同部分之间的一种指向关系，源网页是指包含超链接的网页，目标网页是超链接所指向的网页。

11、超链接HTML格式：超链接的特性如果存在超链接L从页面Psource指向页面Pdestiny，则Psource与 Pdestiny满足：特性1 :内容推荐特性页面Psource的作者推荐页面Pdestiny的内容，且利用L的链接文本内容对Pdestiny进行描述。特性2 :主题相关特性被超链接连接的两个页面Psource与Pdestiny的页面内容涉及类似的主题。特性1说明：l 入链接个数是页面受其他页面推荐程度大小的标志，入链越多，该页面受其他网页作者的推荐越多，其网页内容质量高。l 入链接个数越少，说明该页面不被其他网页作者推荐，意味着页面内容或组织形式不受欢迎。l 链接文本起到对网页内容

12、描述的作用，由于描述来自他人，通常被认为是对网页内容更加客观的描述。这就在页面质量与超链接结构图的拓扑关系间建立了联系，为页面内容质量评价提供了一种不基于内容的方式。HITS 算法、PageRank算法是依据该特性设计的。特性2说明l 与特性1相比，特性2的重要程度、适用性低一些；l Psource、Pdestiny页面内容相关的可能性要大于随机抽取的两个页面；l 超链接表示的不仅是内容相关关系。万维网的超链接关系比特性1、特性2描述的复杂。导航栏链接l 源、目标页面的作者相同，不是内容推荐关系，而是方便用户访问的设置。l 可以认为符合特性2，显然不符合特性1。广告链接l 内容推荐特性、主题相

13、关特性都无法得到保证（尤其是主题相关性)。l 方面变化快、时效性强，对链接结构分析造成了相当的困难。版权、注册链接l 版权信息、注册信息往往以超链接的形式存在，以便查阅；l 这类超链接数目大；l 不符合超链接应具有的两个特性。相当多超链接不符合超链接算法设计中的假设l 各种链接结构分析算法在真实环境中无法单独被用于网页质量评估l 改进算法还是可以为页面质量评估提供参考；l 数据清理后的近似理想环境中，还是可以发挥作用。本章，假设万维网结构中的超链接满足以上两个特性。8.3 HITS 算法的基本思路及实现HITS算法：HITS是Hyperlink-Induced Topic Search的缩写，

14、基于超链接推演的主题搜索算法。核心思想；l 对网页的“内容权威度”、“链接权威度”进行评价；l 内容权威度 ( Authority Value )：网页本身内容的受欢迎程度；l 链接权威度（Hub Value ) ：网页链接到其他受欢迎资源的程度。例：学术论文内容权威度：内容质量比较高、创新性较强、对学科发展能起到较大的推进作用。链接权威度：对某个特定领域进行了较为详尽的调研，能够介绍相当数目的内容质量高的其他论文和研究工作。网页内容权威度：与网页提供的内容信息质量有关，被其他网页引用得越多，其内容权威度越高。网页链接权威度：与网页提供的超链接质量有关，网页链向内容质量高的网页越多，其链接权威

15、度越高。HITS 算法所要解决的问题l 对用户提交的大多数查询，搜索引擎都会返回大量的相关查询结果；l 大多数用户倾向查找出结果集合中对获取信息最有价值的那一部分网页；l 算法的输入：搜索引擎返回的与查询主题在内容上相关的结果集合；l 算法的输出：对结果集合中网页的内容权威度、链接权威度的评价。HITS 算法实施的阶段：1、对用户输人的查询主题，通过搜索，获取内容相关的网页集合，适当扩展网页集合；2、通过 “迭代一收敛”过程，计算网页集合中每个页面的链接权威度与内容权威度，输出按链接权威度、内容权威度排序的结果列表。HITS算法在阶段1，建立与查询主题相关的图（主题子图）主题子图给定查询主题，

16、构造主题子图过程：、用搜索引擎得到查询主题的结果集合，称为根集（Root Set）；、将所指向的网页集合以及其他指向的网页集合包含进来形成集合，称为基本集合（Base Set）。为控制图的节点数量，施加的控制：l 搜索引擎返回结果数量大，将其限制在一个小的范围内，如设置为200；l 某个网页的链入网页的数量大，将其限制在一个给定的范围内，如设置为50。为了消除导航用链接的影响，删除站内链接（即超链接的链源和链宿都在同一个主机上）。在构造完主题子图之后，可以通过迭代算法来计算出网页的链接权威度、内容权威度。网页内容权威度、网页链接权威度间为相互加强的关系：l 具有较高网页链接权威度的网页应该指向

17、较多的网页内容权威度高的网页；l 高网页内容权威度的网页应该被多个高网页链接权威度的网页所指向。对网页i，令ai：内容权威度；hi：链接权威度；B(i)：网页i的入链接集；F(i)：网页的出链接集；则有：例：页面1的内容权威度、链接权威度操作：计算内容权威度；O操作：计算链接权威度；对权值进行规范化。l 规范化内容权威度的公式：l 规范化链接权威度的公式：迭代地进行操作、操作，直到最近两轮迭代的规范化内容权威度、链接权威度的差异很小，则认为已收敛。HITS算法处理的对象个数相对较少，一般也就在几万个以内，计算速度相对较快。因为它是面向查询的算法，对用户响应的时间要快，所以一般情况下只是求出次优

18、解就可以了。在Kleinberg的实验中，循环迭代20次，就可使前个（取之间）网页排序足够地稳定了。例：针对结构图，计算每个网页的链接权威度、内容权威度。解：根据上图构造主题子图，邻接矩阵，表示为8.4 PageRank算法的基本思路及实现 PageRank算法：l 拉里·佩奇（Larry Page）等人提出；l 根据WEB超链接关系对网页重要程度进行估计；l 2008年1月申请美国专利，同年在论文“The Anatomy of a Large-Scale Hyper textual Web Search Engine”中公开；l 将从页面A到页面B的超链接作为A向B的一次投票，但不

19、是简单地统计票数来衡量质量高低，还要考虑投票者因素，较“重要”网页的投票会更受重视。PageRank基于“从许多优质网页链接过来的网页，必定还是优质网页”的思想判定网页的重要性。PageRank衡量“网页质量”的方式l “质量”定义有很强的主观性；n 从时效性、页面结构组织、独特性等角度定义；n HITS算法的“链接权威度”与“内容权威度”；l PageRank用户随机浏览互联网时访问到某个页面的概率；随机浏览模型 l 模型描述用户对网页的访问行为；l 随机体现在：浏览起始点选择的随机性、页内超链接选择的随机性；l 所用浏览器：n 无地址栏，无后退、前进按钮；不能输入URL访问网页，且只能向前

20、浏览不能回退；n 提供“随便逛逛”功能，点击“随便逛逛”按钮，挑选一个随机的起点，开始浏览；l 可从网页内所含超链接中随机选择一个页面继续进行浏览；l 沿着超链接前进了一定数目的网页后，对页面内容不感兴，可使用“随便逛逛”跳转到另一个网页上进行浏览，如此反复。在浏览过程中，用户访问到某个页面的概率就称为该页面的PageRank。页面PageRank计算：网页被用户访问到的可能性有两种。、使用“随便逛逛”跳转到页面A假设“随便逛逛”以随机方式推荐网页，互联网上网页总数为N，则用户使用“随便逛逛”访问到网页A的概率为1/N。、浏览过程中通过其他网页上超链接访问到页面A假设链接到A的个网页为 P，P

21、，P，P。则用户通过P访问A的概率为：PageRank()*P( P=>A)PageRank()：用户访问到页面的概率，P( P=>A)：用户访问页面时，点击链接到A页面的超链接的概率。假设用户浏览P时点击页面上各超链接概率相等；用户通过P，P，P，P访问到A的概率为：或假设。不存在不含超链接的网页，用户主动使用“随便逛逛”功能概率为a，则用户访问到页面A的概率为：用户使用“随便逛逛”功能访问到页面A的概率；：用户使用超链接访问到页面A的概率；可以看到，对给定的参数a，页面A的PageRank值由链接到它的各个页面的PageRank值决定的。如果考虑全万维网页面PageRank的计

22、算，就会发现是一个迭代计算过程。PageRank（简化）算法(1) 取万维网链接结构图G , G的规模为N，即G中包括N个节点。对于 G 中的每一个节点n，设 PR（n）是其PageRank值，而向量为G对应的PageRank结果向量。(2) 设定，即：对G中每一个节点n，设定其初始值PR(0)(n)均为。(3) For k= 1,2,3，TN对G中的每一个节点n , 其中，a为预先设定的参数，Outdegree (Pi)为页面Pi的出度值。(4) 当结果向量未收敛时，返回（3）继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的PR(n）的结果。例：如图所示的链接结构图中，各个网页

23、都具有超链接，A页面链向页面B与C,B与C分别链向D页面，而D页面链回A页面。我们可以依照上述PageRank 简化算法计算图8. 9的PageRank数值如下：随后迭代的结果。由上表可见：l 进行到第30次迭代，算法结果已经基本收敛；l 第30次迭代的结果与第100次迭代的结果差别小于千分之一；l 采用算法迭代30次左右的结果即可以满足需求。l 迭代中页面PageRank变化，但各页面PageRank的和等于1；PageRank（简化）算法的问题 l 有些网页没有出链接 Ø TXT, DOC, JPG, Ø 随机浏览进入死胡同 l 只能使用“随便逛逛”Ø 相当于

24、为“死胡同”网页和G中的所有网页之间添加了一条虚拟的出链接 Ø “死胡同”网页的PageRank借助“随便逛逛”平均分配给G中的所有网页 PageRank（标准）算法(1) 取万维网链接结构图G , G的规模为N，即G中包括N个节点。对于G中的每一个节点n，设PR(n)是其PageRank值，而向量为G对应的PageRank结果向量。(2) 设定，即：对G中每一个节点n设定其初始值PR(0)(n)均为，同时设定临时变量。(3) For k = 1 , 2 , 3 ， ，M 对G中的每一个节点n , 若 Outdegree ( n ) > 0 ，则有：若Outdegree ( n

25、 )=0，则有：其中，a为预先设定的参数，Outdegree (Pi)为页面Pi的出度值。 将临时变量赋值给：(k)= 临时变量赋初值：(4) 当结果向量未收敛时，返回(3)继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的PR(n）的结果。PageRank（标准）算法的问题与改进 l 算法效率低 Ø 每次遍历节点n时，如果n的出度为0，需要对每一个链接图内的节点进行操作。 Ø 相当于为“死胡同”网页和G中的所有网页之间添加了一条虚拟的出链接 l 改进邻接矩阵 原邻接矩阵设链接结构图G的节点规模为n，则邻接矩阵M是一个n*n的矩阵，元素 mi,j取值满足：改进邻

26、接矩阵设链接结构图G的节点规模为n，改进邻接矩阵A是一个n*n的矩阵，元素ai,j取值满足：改进邻接矩阵的元素取值l 如果G中存在边（i，j），则ai,j的取值是1除以节点i对应的出度；l 如果节点i对应的出度为0，则第i行对应的所有元素取值为1 / n； 为什么1 / n？l 其他情况下，ai,j的元素取值为0。如设I=（1，1，1，1)，则迭代过程可以表示为：问题：l 实际中，n的数值巨大，A往往是稀疏矩阵；l 用适用于稀疏矩阵运算的加速算法来改善；PageRank（加速）算法输人：万维网链接结构图G（节点规模为N）的链接关系特征文件D，参数a，迭代次数M ; D的结构： 只记录改进邻接矩阵中的非零元素 Page A -> Page B