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

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

2、模，值满足：则邻接矩阵M是一个n*n的矩阵，其中某个兀素mi,j的取fl 3 GJ) 6 Graph0 otherwise3#图8.1所示链接结构图，其邻接矩阵如下:-o1110101-1010000011010010M =00001000000000100000001000000001_00000000.万维网链接图GWeb (V, E)Vn,节点数 |V| = n ;V :节点集合，V = V 1 , V2 , V3 ,E :边集合,E = ei , e? , e3 ,em,边数 |E|=m将万维网的整个链接结构图作为对象来研究不仅对理解万维网的各种属性有直接的意义，同时还对搜索引擎领域的

3、相关算法研究也有着重要的帮助。 很多实验和观察促进了万维网链接图结构的研究。针对图 GWeb ( 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月，谷歌索引量 1万亿网页，一定程度上反映了 GWeb (V,

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

6、节点 集合规模的几到几十倍。58.1.2 万维网链接图的连通情况定义：导出子图给定G=(V, E),如果存在另外一个图 &=(/©),满足V包含于V, E，包含 于E,则称G，是G的一个子图。特别地，如果 V/包含于V，且E，包含了在节点 子集V/之间的所有边，则称G，是G的导出子图。定义：强连通子图给定一个有向图， 该有向图的一个强连通子图是指由一部分节点组成的一个 导出子图，对于该子图中其中的任意两个节点u和V，都存在一条路径使得从u可以访问到 v。性质：1、一个有向图中可有多个强连通子图。2、强连通子图之间不存在公有节点；否则可以合二为一。对万维网连接图，每个强连通子图

7、都代表着构成该子图的节点是相互连通 的，通过超链接通过一个网页可访问另一个。定义：弱连通子图给定一个有向图， 该有向图的一个弱连通子图是指由一部分节点组成的一个 导出子图，对于该子图中其中的任意两个节点 u和V，都存在一条无向路径使得 从 u 可以访问到 V。对于万维网链接图， 重点考察其包含的强、 弱连通子图的规模分布情况， 借 此了解整个链接图的拓扑结构和连通情况。2000 年， Broder 的研究成果，万维网链接结构图的强、弱连通子图的规模6分布情况如下图所示300 00010 000SCC distnburion00000oWCC distributionle+07le+06100

8、00010 0001O0G10Q10IComponent distribution *Power lawxponeTi； 2.541 10 100 100000 size of componentu.7#g 8.2万錐网链接图中强、弱连通子图的规模分布情况图中，横轴为连通子图规模，纵轴为连通子图数量；横轴、纵轴使用对数坐标轴。可以看出强连通子图、弱连通子图的规模分布规律基本相同；设连通子图规模为Size，具有规模Size的连通子图的数目Number近似满足；)og(Number) =* 2+ 54 log(Size) + C指数形式表示为：Number = Cz Size-'-11几点

9、结论：规模大的连通子图数目远小于规模小的连通子图数目。规模最大的连通子图所覆盖的网络资源数量，占网络资源总量中相当比例。基于链接结构抓取，很难抓取到网络环境中所有数据， 但通过抓取规模较大的 连通子图可获取最主要部分的数据。规模最大的强连通子图，其节点规模达到560余万，此连通子图在 Broder研究的网页集合总规模中占有近 28%的网页。以此连通子图为中心，考察其他网页与此连通子图的链接关系， 可以对整个 网络页面的链接结构关系有一个清晰的认识。根据Broder的研究结论绘制的万维网链接结构示意图如下图所示。Others 29.9%图万维网链接结构图Core部份规模最大的强连接子图；IN部分

10、所有链接到Core中网页，且同时不被Core中的网页所链接的网页集合；OUT部分所有被Core中的网页所链接，且同时不链接到 Core中网页的网页集合；Others部分剩余的网页集合。万维网链接和连通结构概貌从IN中任何网页，都可以链接到Core中网页，进而可访问OUT中任何网页。IN、Core、OUT之外网页，一部份与IN、OUT有链接关系，另一部分与IN、Core、OUT不相连的孤立点或点集合，规模约为所分析网页总数的8.2%。万维网链接结构以Core为核心，构成了“领结”形式的结构。8.1.3万维网链接图的入度和出度分布万维网链接图的入度、出度分别反映了某节点被其他节点链接，以及链接到

11、其他节点的情况。万维网链接图GWeb (V,E)的入度、出度分布符合幕律；入度为In degree的网页数目 N ( In degree )近似满足：Indegree) = C Indegree-0出度为Outdegree的网页数目 N ( Outdegree )近似满足:N(Outdegree) = C Outdcgree'其中a、B均为值大于零的参数，而 C与&为常数Broder的实验结果如下图所示。le+10In-degree(May 99,Oct 99)disir.Out-dcgrce(May 99,Oct 99)dstr.MUepKltJ:*qEnllle+09 -!

12、t+O8 ：i-e+07 -le-06 - 00 000 -100001000 -ln4iegree(May 99)卩 ower law,exponCTiL 2.09k-defiz«e<Oct 99Power law,exponent 2.09器啓 d jo -JJJLunLlle+JOle+09le+O8le+07le+06 lOOOOO10 00000 J1001001 10 100 100 000Jl(jOut-degncefMay 99 t Power hwxpnnenl 2.72 Out-degree(Oct 99)30 100 1000 out-degree(a)图

13、吐斗 万维网链接图中入度、出度的分布惜况8.2超链接结构分析的基础超链接：两个网页或网页的两个不同部分之间的一种指向关系，源网页是指包含超链接的网页，目标网页是超链接所指向的网页。超链接HTML格式：< A HREF- "http: /www, tsinghus. edu + cW清华大学主页 < /A>超链接的特性如果存在超链接L从页面Psource指向页面Pdestiny,则Psource与Pdestiny满足：特性1 :内容推荐特性页面Psource的作者推荐页面Pdestiny的内容，且利用L的链接文本内容对Pdest iny进行描述。特性2 :主题相关特性

14、被超链接连接的两个页面Psource与 Pdestiny的页面内容涉及类似的主题。特性 1 说明：入链接个数是页面受其他页面推荐程度大小的标志， 入链越多， 该页面受其他 网页作者的推荐越多，其网页内容质量高。入链接个数越少， 说明该页面不被其他网页作者推荐， 意味着页面内容或组织 形式不受欢迎。链接文本起到对网页内容描述的作用， 由于描述来自他人， 通常被认为是对网 页内容更加客观的描述。这就在页面质量与超链接结构图的拓扑关系间建立了联系， 为页面内容质量 评价提供了一种不基于内容的方式。HITS算法、PageRank算法是依据该特性设计的。特性 2 说明与特性 1 相比，特性 2的重要程度

15、、适用性低一些；Psource Pdestiny页面内容相关的可能性要大于随机抽取的两个页面； 超链接表示的不仅是内容相关关系。万维网的超链接关系比特性 1、特性 2 描述的复杂。导航栏链接 源、目标页面的作者相同，不是内容推荐关系，而是方便用户访问的设置。 可以认为符合特性 2，显然不符合特性 1。广告链接 内容推荐特性、主题相关特性都无法得到保证（尤其是主题相关性）。方面变化快、时效性强，对链接结构分析造成了相当的困难。版权、注册链接版权信息、注册信息往往以超链接的形式存在，以便查阅；这类超链接数目大；不符合超链接应具有的两个特性。相当多超链接不符合超链接算法设计中的假设各种链接结构分析算

16、法在真实环境中无法单独被用于网页质量评估 改进算法还是可以为页面质量评估提供参考； 数据清理后的近似理想环境中，还是可以发挥作用。本章，假设万维网结构中的超链接满足以上两个特性。8.3 HITS 算法的基本思路及实现HITS 算法：HITS是Hyperlink-lnduced Topic Search的缩写，基于超链接推演的主题搜索 算法。核心思想；对网页的“内容权威度” 、“链接权威度”进行评价；内容权威度 ( Authority Value )：网页本身内容的受欢迎程度；链接权威度( Hub Value ) ：网页链接到其他受欢迎资源的程度 例：学术论文内容权威度：内容质量比较高、 创新性

17、较强、对学科发展能起到较大的推进作用。链接权威度：对某个特定领域进行了较为详尽的调研， 能够介绍相当数目的内容质量高的其他论文和研究工作。网页内容权威度：与网页提供的内容信息质量有关，被其他网页引用得越多，其内容权威度越网页链接权威度：与网页提供的超链接质量有关，网页链向内容质量高的网页越多，其链接权威度越高。HITS算法所要解决的问题对用户提交的大多数查询，搜索引擎都会返回大量的相关查询结果； 大多数用户倾向查找出结果集合中对获取信息最有价值的那一部分网页;算法的输入：搜索引擎返回的与查询主题在内容上相关的结果集合；算法的输出：对结果集合中网页的内容权威度、链接权威度的评价。HITS算法实施

18、的阶段：1、对用户输人的查询主题，通过搜索，获取内容相关的网页集合，适当扩展网 页集合；2、通过“迭代一收敛”过程，计算网页集合中每个页面的链接权威度与内容权 威度，输出按链接权威度、内容权威度排序的结果列表。给定查询主题，构造主题子图过程：1、用搜索引擎得到查询主题的结果集合R,称为根集(Root Set);2、将R所指向的网页集合以及其他指向R的网页集合包含进来形成集合S,称为基本集合(Base Set。为控制图的节点数量，施加的控制：搜索引擎返回结果数量大，将其限制在一个小的范围t内，如设置t为200;某个网页的链入网页的数量大，将其限制在一个给定的范围d内，如设置d为50。为了消除导航

19、用链接的影响，删除站内链接(即超链接的链源和链宿都在同 一个主机上)。在构造完主题子图之后，可以通过迭代算法来计算出网页的链接权威度、内 容权威度。网页内容权威度、网页链接权威度间为相互加强的关系：具有较高网页链接权威度的网页应该指向较多的网页内容权威度高的网页; 高网页内容权威度的网页应该被多个高网页链接权威度的网页所指向。对网页i，令ai：内容权威度；hi：链接权威度；B(i):网页i的入链接集；F(i):网页1的出链接集；则有：色=丫 bJh=为勺例：页面1的内容权威度、链接权威度14 1 = /心十心+力I 儿=心+化+ ©I操作：计算内容权威度;O操作：计算链接权威度;q：

20、 p对权值进行规范化规范化内容权威度的公式:规范化链接权威度的公式:115迭代地进行I操作、O操作，直到最近两轮迭代的规范化内容权威度、 链接权威 度的差异很小，则认为已收敛。输入A）. G是链接页面的集合，k是一个口然数令辽我示矢量（1. U H 1）6RHWhili | a（_| | | h力$_ | O，do 对（如一“ h）应用I操作级获得新的“； 对（；申儿J应用（）操作号获得新的h 标准化auihority值申获得a 标准化hub值/二得到九End返回（仆加）HITS算法处理的对象个数相对较少，一般也就在几万个以内，计算速度相 对较快。因为它是面向查询的算法，对用户响应的时间要快，

21、所以一般情况下只 是求出次优解就可以了。在Kleinberg的实验中，循环迭代20次,就可使前C个（C取510之间） 网页排序足够地稳定了。16例：针对结构图，计算每个网页的链接权威度、内容权威度解：根据上图构造主题子图V=A,B,C，邻接矩阵E= <A,A> ,A,B> , <A,C> , <B,A> , <B,C> , <C,B> ,表示为1rE =10101o由此得到英转宣矩阵为110_Er =101_110.（口,吗,=E' (h 吕 * h R、h 广),(Aa* hfi» h(')口h* 口

22、厂因此有，%=ftA + 叽.ati =+ hf = flA + 叽h=ClA + WB + etc *=a a十 » /：( = 3初始化吋.令5 = %=ac=hA = hli=h=1.第一次迭代il算心值： 2 Up = 2 ? de 2计算&值:占丸=6申方舟=4 .力g = 2 为简便计算，釆用最大值的规范化方法。规范化S5 = 1，月=1* ac = 1 规范化b_ _ 2 _ 1继续迭代曲至收敛。最后：5 = 1，g = O*732, ac 1hA = l9 论=5 732. Ac =0.26818HITS (Hyperlink-1nduced Topic Se

23、arch)算法(1) 选取网络信息检索系统的结果集合R将尺賦所指向的网页和指向的网页枸成的链接结构图称为G。对于G中的每一个节点心设和分别是其链接权威度和内容权威度，向量H和才分别 为G的链接权威度和内容权威度结果向凰°(2) 设定即：对G中每一个节点心设定其初始值(总)和A的均 为1.(3) For i = 对G中的每一个节点捍，A&)= 另称为I操作)Hu. so'i 对G中的每一个节点心H5)=杓 (称为0操作) 将Hw(n)和AUWG)作规范化处理，使尸=1,工(H|尸=K4)当结果向量目和/未收敛时，返回(3) H和A收敛时，输出算法所计算出的G中每一个 节

24、点贰的和的结果°8.4 PageRank算法的基本思路及实现PageRank 算法：拉里佩奇(Larry Page)等人提出；根据WEB超链接关系对网页重要程度进行估计；2008年1月申请美国专利，同年在论文“ The An atomy of a Large-Scale Hyper textual Web Search Engine 中公开；将从页面A到页面B的超链接作为A向B的一次投票，但不是简单地统计票 数来衡量质量高低，还要考虑投票者因素，较“重要”网页的投票会更受重视。PageRa nk基于“从许多优质网页链接过来的网页，必定还是优质网页”的 思想判定网页的重要性。PageR

25、ank 衡量“网页质量”的方式“质量”定义有很强的主观性；从时效性、页面结构组织、独特性等角度定义；HITS算法的“链接权威度”与“内容权威度”；PageRa nk用户随机浏览互联网时访问到某个页面的概率;随机浏览模型模型描述用户对网页的访问行为；随机体现在：浏览起始点选择的随机性、页内超链接选择的随机性；所用浏览器：无地址栏，无后退、前进按钮；不能输入 URL访问网页，且只能向前浏 览不能回退；提供“随便逛逛”功能，点击“随便逛逛”按钮，挑选一个随机的起点， 开始浏览；可从网页内所含超链接中随机选择一个页面继续进行浏览；沿着超链接前进了一定数目的网页后， 对页面内容不感兴，可使用“随便逛逛”

26、 跳转到另一个网页上进行浏览，如此反复。在浏览过程中，用户访问到某个页面的概率就称为该页面的PageRank。用户离开肖肃匸世页面PageRank计算:网页被用户访问到的可能性有两种。1、使用“随便逛逛”跳转到页面 A假设“随便逛逛”以随机方式推荐网页，互联网上网页总数为N，则用户使用“随便逛逛”访问到网页 A的概率为1/N。2、浏览过程中通过其他网页上超链接访问到页面A假设链接到A的k个网页为Pi, P2 , P3,，Pk。则用户通过Pi访问A 的概率为：PageRank(P i )*P( P i =>A)PageRank(P J：用户访问到P i页面的概率，P( Pi =>A)

27、:用户访问P i页面时，点击链接到A页面的超链接的概率 假设用户浏览Pi时点击页面上各超链接概率相等；21#P(Pi1Outdegree(R)#用户通过Pi，P2，P3,，Pk访问到A的概率为:#J PageRank(P)芋 PageRa nk(P)P二 AOutdegree(R)#假设。不存在不含超链接的网页，用户主动使用“随便逛逛”功能概率为a， 则用户访问到页面A的概率为：PageRank(A)二 a* i Outdegree(R)(1 -a)* ' PageRank(Pi)N冷 Outdegree(R)1a*丄：用户使用“随便逛逛”功能访问到页面 A的概率；N(1-a)* a

28、PageRank：Pi):用户使用超链接访问到页面A的概率； 冷 Outdegree(R)可以看到，对给定的参数 a,页面A的PageRank值由链接到它的各个页面 的PageRank值决定的。如果考虑全万维网页面 PageRank的计算，就会发现是 一个迭代计算过程。PageRank (简化)算法取万维网链接结构图G , G的规模为N，即G中包括N个节点对于G中的每一个节点n,设PR(n)是其PageRank值，而向量PR为GPR =(丄，丄，丄N N N对应的PageRank结果向量。设定,丄即：对G中每一个节点n，设定其初始值PR(O)(n)均为N For k= 1,2,3,，TN对G中

29、的每一个节点n ,(k)* 1“ 、八PR(kJl)(P)(n) = a *(1 - a)-PRNPnOutdegree(P)其中，a为预先设定的参数，Outdegree (P)为页面Pi的出度值。(4) 当结果向量PR未收敛时，返回(3)继续循环；当PR收敛时，算法结束, 输出所计算出的G中每一个节点n的PR(n)的结果。例：如图所示的链接结构图中，各个网页都具有超链接，A页面链向页面B与C,B与C分别链向D页面，而D页面链回A页面。我们可以依照上述PageRank简化算法计算图8. 9的PageRank数值如下：23#24初值：庶=(*，+，+，*),设 a 为 0.2第一次迭代；PR(A

30、) = 0 2 ± + (1 0. 2八(PR(D)/Outdegree(D) 4=0* 05 + 0, 8 0, 254PR(1)(B) = 0. 2 丄 + (I 0. 2) - (PRt0> (A)/Outdegree(A) 41 1 _=0.05 + 0.8 j * y = 0. 15PR(C) = 0,2 丄 + (1 0. 2八(PR(A)/Outdegree<A)> 4=0,05+0.8 # * 二 0.15PR(D) = 0. 2 丄 + (1 0. 2八(PR(0>(B)/Outdegree(B) 4+ PRf0)(C)/Outdegree(

31、C) = 0. 05 + 0. 8 (扌 + 工=0. 4525第二次迭代：PR(A= 0. 2 ± + (1 0. 2八(PRtn(D)/Outdegree(D) 4=0.05 +CM 6 45 = 0*41PR(B= CL 2 3 + (1 0. 2) * (PR(A)/Outdegree(A) 41 10.05 + 0. 8 4 4 = 0. 1542FR(C) = 0* 2 丄 + Q 0. 2八(PR(A)/Outdegree(A)4=0.05 + 0, 8 4丄=0* 154 LFRO (D) = 0展* 丄 +1 CL 2八(PRC0) (B)/Outdegree(B)

32、4+ PR<0>(C>/Outdegree(C) = 0.05 + 0, 8 - (0.15 + 0.15)=0. 29随后迭代的结果表乱1 图乩9对应的PageRank计算结杲PR(A)PR(B)PR(C)PR(D)Y FR第1次迭代0.25000.2500Q* 25000.25001. 0000第2次迭代0.25000. 15000. 15000,4500LOOOO第3次迭代0+41000.15000. 15000.29001. 0000第4决迭代0,28200.21400.21400.2900l.OODQ第5次迭代0, 28200, K280.16280,39241.0

33、000第10次送杜0.30680,1861 10.18S10.3210L 0000第湖次迭代0.31440.17580.17580t 33411. 0000第昭次迭代0,31580.17620r17620,33191.0000第100次迭松0.31560.17620, 17620.3320L 0000由上表可见：进行到第30次迭代，算法结果已经基本收敛；第30次迭代的结果与第100次迭代的结果差别小于千分之一;采用算法迭代30次左右的结果即可以满足需求。迭代中页面PageRank变化，但各页面 PageRank的和等于1 ；PageRank (简化)算法的问题有些网页没有出链接TXT, DOC

34、, JPG,随机浏览进入死胡同只能使用“随便逛逛”相当于为 死胡同”网页和G中的所有网页之间添加了一条虚拟的出链接死胡同”网页的PageRank借助“随便逛逛”平均分配给 G中的所有网页PageRank (标准)算法取万维网链接结构图G , G的规模为N，即G中包括N个节点对于G中的每一个节点n,设PR(n)是其PageRank值，而向量PR为G对应 的PageRank结果向量。 设定PR =(,，)，即：对G中每一个节点n设定其初始值PR(n)N N N N均为-，同时设定临时变量I =(旦，旦,旦,，旦NN N N N For k = 1 , 2,3，M对G中的每一个节点n ,若Outde

35、gree ( n ) > 0，则有：Pr(t (n)-R,ifnP,I(P) = l(P) (Va)*-Outdegree(n)若 Outdegree ( n )=0,则有:PR(k)(门) 育 G,I(P)二 l(P) (1 - a)*-N其中，a为预先设定的参数，Outdegree (P)为页面Pi的出度值。 将临时变量赋值给PR : PR(k)=l临时变量赋初值：(話話話戶 当结果向量PR未收敛时，返回 继续循环；当PR收敛时，算法结束，输出 所计算出的G中每一个节点n的PR（n）的结果。PageRank （标准）算法的问题与改进算法效率低每次遍历节点n时，如果n的出度为0，需要对

36、每一个链接图内的节点进 行操作。相当于为 死胡同”网页和G中的所有网页之间添加了一条虚拟的出链接 改进邻接矩阵原邻接矩阵设链接结构图G的节点规模为n,则邻接矩阵M是一个n*n的矩阵，元素mq取值满足：3dfj)e gotherwise28#改进邻接矩阵设链接结构图G的节点规模为n，改进邻接矩阵A是一个n*n的矩阵，元 素ai,j取值满足:10e GS 4" = 0iotherwise改进邻接矩阵的元素取值如果G中存在边（i, j）,则a,j的取值是1除以节点i对应的出度;如果节点i对应的出度为0,则第i行对应的所有元素取值为1 / n； 为什么1 / n？其他情况下，ai,j的元素取值为0。#如设I