信息检索20-链接分析.pptVIP

*PageRank的起源:引用分析(1)引用分析：科技文献中的引用分析一个引用的例子:“Miller(2001)hasshownthatphysicalactivityaltersthemetabolismofestrogens.”可以把“Miller(2001)”看成是两篇学术文献之间的超链接在科技文献领域使用这些“超链接”的一个应用:根据他人引用的重合率来度量两篇文献的相似度，这称为共引相似度在Web上也存在共引相似度：Google中提供的“findpageslikethis”或者“Similar”功能PageRank起源:引用分析(2)另一个应用:引用频率可以用度量一篇文档的影响度最简单的度量指标：每篇文档都看成一个投票单位，引用可以看成是投票，然后计算一篇文档被投票的票数。当然这种方法不太精确。在Web上：引用频率=入链数入链数目大并不一定意味着高质量......主要原因是因为存在大量作弊链接…更好的度量方法：对不同网页来的引用频率进行加权一篇文档的投票权重来自于它本身的引用因子会不会出现循环计算？答案是否定的，实际上可以采用良好的形式化定义PageRank的起源:引用分析(3)更好的度量方法:加权的引用频率PageRank最早起源于1960年代Pinsker和Narin提出的引用分析这就是PageRank的基本思路引用分析不是小事情，在美国，任何教职人员的薪水取决于其发表文章的影响力！上一讲回顾锚文本引用分析PageRankHITS:Hub节点Authority节点01提纲02原始的PageRank公式*R(u)和R(v)是分别是网页u、v的PageRank值，Bu指的是指向网页u的网页集合、Nv是网页v的出链数目。一个网页的PageRank等于所有的指向它的网页的PageRank的分量之和(c为归一化参数)。网页的每条出链上每个分量上承载了相同的PageRank分量。PageRank的特点*一个网页如果它的入链越多，那么它也越重要(PageRank越高)；一个网页如果被越重要的网页所指向，那么它也越重要(PageRank越高)。类比:(1)打电话；(2)微博粉丝简单计算的例子(c=1)R(A)=R(C)R(B)=0.5R(A)R(C)=R(B)+0.5R(A)R(A)+R(B)+R(C)=1解上述方程得：R(A)=R(C)=0.4R(B)=0.2ABC0.40.20.20.40.20.40.2简单计算的例子(c=1)：迭代法求解*ABC0.40.40.2迭代次数R(A)R(B)R(C)01/31/31/311/31/61/221/21/61/331/31/45/12…………收敛2/51/52/5R(A)=R(C)R(B)=0.5R(A)R(C)=R(B)+0.5R(A)R(A)+R(B)+R(C)=1转化成矩阵形式*令R表示所有N个网页的PageRank组成的列向量，令网页间的连接矩阵L={lij}，Pi有链接指向Pj时，lij=1，否则lij=0。对L的每行进行归一化，即用Pi的出度Ni去除得到矩阵A={aij}，aij=lij/Ni，则有(AT表示A的转置矩阵)：R=cATR==c-1R=ATR根据线性代数中有关特征向量和特征值的理论，R是矩阵AT的c-1特征值对应的特征向量R(A)=R(C)R(B)=0.5R(A)R(C)=R(B)+0.5R(A)一个稍微复杂的例子*A=计算过程*R=01Normalized=01则归一化后A=R＝cATR，令c=1，解得01原始PageRank的一个不足Aloop:图中存在一个循环通路，每次迭代，该循环通路中的每个节点的PageRank不断增加，但是它们并不指出去，即不将PageRank分配给其他节点！一个例子一个例子一个例子改进的PageRank公式*随机冲浪或随机游走(RandomWalk)模型：到达u的概率由两部分组成，一部分是直接随机选中的概率(1-d)或(1-d)/N，另一部分是从指向它的网页顺着链接浏览的概率，则有上述两个公式中，后一个公式所有网页PageRank的和为1，前一个公式的PageRank和为N(1-d)+d。可以证明，PageRank是收敛的。计算时，PageRank很难通过解析方式求解，通常通过迭代方式求解。d通常取0.85或PageR