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

1第8章链接结构分析子系统设计及核心算法本章内容：万维网链接结构图及特性；链接结构分析方法的形式化基础；链接结构分析PageRank算法、HITS算法；链接结构分析结果在搜索结果排序中的应用。8.1万维网链接结构图万维网的链接结构可用有向图来描述，网页是节点，超链接是有向边。从源网页指向目的网页的超链接，为源网页的“出链接”，为目的网页的“入链接”。节点A-H表示网页；链接关系用有向边来表示；网页A、B、C之间的双向边，表示三个网页之间相互链接；网页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。3将万维网的整个链接结构图作为对象来研究不仅对理解万维网的各种属性有直接的意义，同时还对搜索引擎领域的相关算法研究也有着重要的帮助。很多实验和观察促进了万维网链接图结构的研究。针对图GWeb(V,E)，研究；V、E的规模；拓扑结构；节点入度、出度分布。图G(V,E）的某节点所关联的边数称为该节点的“度”。对于图GWeb(V,E）而言，某节点的入度就是指以该节点作为目的网页的超链接数（该节点入链接数）；某节点的出度则是指以该节点为源网页的超链接数（该节点出链接数）。8.1.1万维网链接图的规模GWeb(V,E）规模难以统计(1)图中的节点存在形式复杂；非自由访问的网页（网页对用户访问加以限制，如采取登录策略等）；自由访问的网页；传统形式的静态页面；随用户查询需求在服务器端实时生成的动态页面；用Ajax技术生成的URL相同但内容千差万别的页面；(2)超链接的界定，存在诸多困难；“博客日历”，每个日期都是一个超链接。服务器端自动生成的超链接VS网页作者手工编辑添加的链接。GWeb(V,E）的节点集合规模通过域名注册服务商可统计网站、域名数量且较为准确；统计网站涉及的网页数目就会面临上面提到的问题；研究中通常用搜索引擎的索引规模来估算万维网链接图的节点规模；4没被任何一个搜索引擎收录的网页，被用户访问到的可能性微乎其微；2008年7月，谷歌索引量1万亿网页，一定程度上反映了GWeb(V,E）节点集合的规模。GWeb(V,E）的边集合规模估计边集合规模更困难；超链接的添加不需要登记、备案，各大搜索引擎也很少公布统计数据；只能通过实验性万维网语料库的相关数据对GWeb(V,E）的边集合规模有一个概括性的认识；AltaVista语料库，链接关系图包含2.03亿个网页、14.66亿条链接。Clueweb09语料库，链接关系图包含的节点数为1040809705个，对应的出链接数为7944351835个。sogouT语料库，链接关系图包含1.39亿个网页、33.4亿条链接。从这些语料库，可以估计，边集合的规模要大于节点集合的规模，约为节点集合规模的几到几十倍。58.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、一个有向图中可有多个强连通子图。2、强连通子图之间不存在公有节点；否则可以合二为一。对万维网连接图，每个强连通子图都代表着构成该子图的节点是相互连通的，通过超链接通过一个网页可访问另一个。定义：弱连通子图给定一个有向图，该有向图的一个弱连通子图是指由一部分节点组成的一个导出子图，对于该子图中其中的任意两个节点u和v，都存在一条无向路径使得从u可以访问到v。对于万维网链接图，重点考察其包含的强、弱连通子图的规模分布情况，借此了解整个链接图的拓扑结构和连通情况。2000年，Broder的研究成果，万维网链接结构图的强、弱连通子图的规模6分布情况如下图所示。图中，横轴为连通子图规模，纵轴为连通子图数量；横轴、纵轴使用对数坐标轴。可以看出强连通子图、弱连通子图的规模分布规律基本相同；设连通子图规模为Size，具有规模Size的连通子图的数目Number近似满足；指数形式表示为：几点结论：规模大的连通子图数目远小于规模小的连通子图数目。规模最大的连通子图所覆盖的网络资源数量，占网络资源总量中相当比例。基于链接结构抓取，很难抓取到网络环境中所有数据，但通过抓取规模较大的连通子图可获取最主要部分的数据。规模最大的强连通子图，其节点规模达到560余万，此连通子图在Broder研究的网页集合总规模中占有近28%的网页。以此连通子图为中心，考察其他网页与此连通子图的链接关系，可以对整个网络页面的链接结构关系有一个清晰的认识。根据Broder的研究结论绘制的万维网链接结构示意图如下图所示。7Core部份规模最大的强连接子图；IN部分所有链接到Core中网页，且同时不被Core中的网页所链接的网页集合；OUT部分所有被Core中的网页所链接，且同时不链接到Core中网页的网页集合；Others部分剩余的网页集合。万维网链接和连通结构概貌从IN中任何网页，都可以链接到Core中网页，进而可访问OUT中任何网页。IN、Core、OUT之外网页，一部份与IN、OUT有链接关系，另一部分与IN、Core、OUT不相连的孤立点或点集合，规模约为所分析网页总数的8.2%。万维网链接结构以Core为核心，构成了“领结”形式的结构。8.1.3万维网链接图的入度和出度分布万维网链接图的入度、出度分别反映了某节点被其他节点链接，以及链接到其他节点的情况。万维网链接图GWeb(V,E)的入度、出度分布符合幂律；入度为Indegree的网页数目N(Indegree）近似满足：出度为Outdegree的网页数目N(Outdegree）近似满足：8其中α、β均为值大于零的参数，而C与C/为常数。Broder的实验结果如下图所示。8.2超链接结构分析的基础超链接：两个网页或网页的两个不同部分之间的一种指向关系，源网页是指包含超链接的网页，目标网页是超链接所指向的网页。超链接HTML格式：超链接的特性如果存在超链接L从页面Psource指向页面Pdestiny，则Psource与Pdestiny满足：特性1:内容推荐特性页面Psource的作者推荐页面Pdestiny的内容，且利用L的链接文本内容对Pdestiny进行描述。特性2:主题相关特性被超链接连接的两个页面Psource与Pdestiny的页面内容涉及类似的主题。9特性1说明：入链接个数是页面受其他页面推荐程度大小的标志，入链越多，该页面受其他网页作者的推荐越多，其网页内容质量高。入链接个数越少，说明该页面不被其他网页作者推荐，意味着页面内容或组织形式不受欢迎。链接文本起到对网页内容描述的作用，由于描述来自他人，通常被认为是对网页内容更加客观的描述。这就在页面质量与超链接结构图的拓扑关系间建立了联系，为页面内容质量评价提供了一种不基于内容的方式。HITS算法、PageRank算法是依据该特性设计的。特性2说明与特性1相比，特性2的重要程度、适用性低一些；Psource、Pdestiny页面内容相关的可能性要大于随机抽取的两个页面；超链接表示的不仅是内容相关关系。万维网的超链接关系比特性1、特性2描述的复杂。导航栏链接源、目标页面的作者相同，不是内容推荐关系，而是方便用户访问的设置。可以认为符合特性2，显然不符合特性1。广告链接内容推荐特性、主题相关特性都无法得到保证（尤其是主题相关性)。方面变化快、时效性强，对链接结构分析造成了相当的困难。版权、注册链接10版权信息、注册信息往往以超链接的形式存在，以便查阅；这类超链接数目大；不符合超链接应具有的两个特性。相当多超链接不符合超链接算法设计中的假设各种链接结构分析算法在真实环境中无法单独被用于网页质量评估改进算法还是可以为页面质量评估提供参考；数据清理后的近似理想环境中，还是可以发挥作用。本章，假设万维网结构中的超链接满足以上两个特性。8.3HITS算法的基本思路及实现HITS算法：HITS是Hyperlink-InducedTopicSearch的缩写，基于超链接推演的主题搜索算法。核心思想；对网页的“内容权威度”、“链接权威度”进行评价；内容权威度(AuthorityValue)：网页本身内容的受欢迎程度；链接权威度（HubValue)：网页链接到其他受欢迎资源的程度。例：学术论文内容权威度：内容质量比较高、创新性较强、对学科发展能起到较大的推进作用。链接权威度：对某个特定领域进行了较为详尽的调研，能够介绍相当数目的内容质量高的其他论文和研究工作。网页内容权威度：11与网页提供的内容信息质量有关，被其他网页引用得越多，其内容权威度越高。网页链接权威度：与网页提供的超链接质量有关，网页链向内容质量高的网页越多，其链接权威度越高。HITS算法所要解决的问题对用户提交的大多数查询，搜索引擎都会返回大量的相关查询结果；大多数用户倾向查找出结果集合中对获取信息最有价值的那一部分网页；算法的输入：搜索引擎返回的与查询主题在内容上相关的结果集合；算法的输出：对结果集合中网页的内容权威度、链接权威度的评价。HITS算法实施的阶段：1、对用户输人的查询主题，通过搜索，获取内容相关的网页集合，适当扩展网页集合；2、通过“迭代一收敛”过程，计算网页集合中每个页面的链接权威度与内容权威度，输出按链接权威度、内容权威度排序的结果列表。HITS算法在阶段1，建立与查询主题相关的图（主题子图）主题子图12给定查询主题，构造主题子图过程：１、用搜索引擎得到查询主题的结果集合Ｒ，称为根集（RootSet）；２、将Ｒ所指向的网页集合以及其他指向Ｒ的网页集合包含进来形成集合Ｓ，称为基本集合（BaseSet）。为控制图的节点数量，施加的控制：搜索引擎返回结果数量大，将其限制在一个小的范围ｔ内，如设置ｔ为200；某个网页的链入网页的数量大，将其限制在一个给定的范围ｄ内，如设置ｄ为50。为了消除导航用链接的影响，删除站内链接（即超链接的链源和链宿都在同一个主机上）。在构造完主题子图之后，可以通过迭代算法来计算出网页的链接权威度、内容权威度。网页内容权威度、网页链接权威度间为相互加强的关系：具有较高网页链接权威度的网页应该指向较多的网页内容权威度高的网页；高网页内容权威度的网页应该被多个高网页链接权威度的网页所指向。对网页i，令ai：内容权威度；hi：链接权威度；B(i)：网页i的入链接集；F(i)：网页ｉ的出链接集；则有：例：页面1的内容权威度、链接权威度13Ｉ操作：计算内容权威度；O操作：计算链接权威度；对权值进行规范化。规范化内容权威度的公式：规范化链接权威度的公式：14迭代地进行Ｉ操作、Ｏ操作，直到最近两轮迭代的规范化内容权威度、链接权威度的差异很小，则认为已收敛。HITS算法处理的对象个数相对较少，一般也就在几万个以内，计算速度相对较快。因为它是面向查询的算法，对用户响应的时间要快，所以一般情况下只是求出次优解就可以了。在Kleinberg的实验中，循环迭代20次，就可使前Ｃ个（Ｃ取５～１０之间）网页排序足够地稳定了。15例：针对结构图，计算每个网页的链接权威度、内容权威度。解：根据上图构造主题子图Ｖ＝｛Ａ，Ｂ，Ｃ｝，邻接矩阵Ｅ＝｛〈Ａ，Ａ〉，〈Ａ，Ｂ〉，〈Ａ，Ｃ〉，〈Ｂ，Ａ〉，〈Ｂ，Ｃ〉，〈Ｃ，Ｂ〉｝，表示为16178.4PageRank算法的基本