信息检索-链接分析.ppt

第20讲 链接分析
Link Analysis
2017/10/31
提纲
上一讲回顾
锚文本
引用分析
PageRank
HITS: Hub节点&Authority节点
*
PPT课件
上一讲回顾
锚文本
篇文档都看成一个投票单位，引用可以看成是投票，然后计算一篇文档被投票的票数。当然这种方法不太精确。
在Web上： 引用频率=入链数
入链数目大并不一定意味着高质量...
... 主要原因是因为存在大量***链接…
更好的度量方法： 对不同网页来的引用频率进行加权
一篇文档的投票权重来自于它本身的引用因子
会不会出现循环计算？答案是否定的，实际上可以采用良好的形式化定义
*
PPT课件
*
PageRank的起源: 引用分析(3)
更好的度量方法: 加权的引用频率
这就是PageRank的基本思路
PageRank 最早起源于1960年代Pinsker和Narin提出的引用分析
引用分析不是小事情，在美国，任何教职人员的薪水取决于其发表文章的影响力！
*
PPT课件
上一讲回顾
锚文本
引用分析
PageRank
HITS: Hub节点&Authority节点
提纲
*
PPT课件
原始的PageRank公式
R(u)和R(v)是分别是网页u、v的PageRank值，Bu指的是指向网页u的网页集合、Nv是网页v的出链数目。
一个网页的PageRank等于所有的指向它的网页的PageRank的分量之和(c为归一化参数)。网页的每条出链上每个分量上承载了相同的PageRank分量。
*
PPT课件
PageRank的特点
一个网页如果它的入链越多，那么它也越重要(PageRank越高)；
一个网页如果被越重要的网页所指向，那么它也越重要(PageRank越高) 。
类比: (1) 打电话； (2)微博粉丝
*
PPT课件
简单计算的例子(c=1)
R(A)=R(C)
R(B)=(A)
R(C)=R(B)+(A)
R(A)+R(B)+R(C)=1
解上述方程得：
R(A)=R(C)=
R(B)=
A
B
C







*
PPT课件
简单计算的例子(c=1)：迭代法求解
A
B
C



迭代次数
R(A)
R(B)
R(C)
0
1/3
1/3
1/3
1
1/3
1/6
1/2
2
1/2
1/6
1/3
3
1/3
1/4
5/12
…
…
…
…
收敛
2/5
1/5
2/5
R(A)=R(C)
R(B)=(A)
R(C)=R(B)+(A)
R(A)+R(B)+R(C)=1
*
PPT课件
转化成矩阵形式
令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)=(A)
R(C)=R(B)+(A)
*
PPT课件
一个稍微复杂的例子
A=
*
PPT课件
计算过程
则归一化后A =
R =
Normalized =
R＝cATR，令c=1，解得
*
PPT课件
原始PageRank的一个不足
A loop:
图中存在一个循环通路，每次迭代，该循环通路中的每个节点的PageRank不断增加，但是它们并不指出去，即不将PageRank分配给其他节点！
*
PPT课件
一个例子
*
PPT课件
一个例子
*
PPT课件
一个例子
*
PPT课件
改进的PageRank公式
随机冲浪或随机游走(Random Walk)模型：到达u的概率由两部分组成，一部分是直接随机选中的概率(1-d)或(1-d)/N，另一部分是从指向它的网页顺着链接浏览的概率，则有
上述两个公式中，后一个公式所有网页PageRank的和为1，前一个公式的PageRank和为N(1-d)+d 。
可以证明，PageRank是收敛的。计算时，PageRank很难通过解析方式求解，通常通过迭代方式求解。
或
*
PPT课件
PageRank面对的Spamm