Kaisa主讲
公式输入请参考： 在线Latex公式

Internet网络的图结构及概念复习

将Internet网络中网页看做节点，把超链接看做有向边。

---

网页的分类老师提到两类，早期多是静态HTML，属于第一类，典型的就是hao123网站。以下内容来自：http://www.thuir.org/group/~YQLiu/thesis/05Content.pdf
导航类（Navigational）：目标是查找某个特定的站点或者网页。如“上海
市政府网站”、“清华大学招生简章”等（摘自百度网站“搜索风向标”栏目，
下同）。
信息事务类（Informational）：目标是获取可能位于一个或某几个网页上的
信息。如“现代企业制度的形式”、“农村党员队伍状况” 等。
事务类（Transactional）：目标是查找能够处理某些以 Web 为媒介的事务的
网页。如“连连看下载”、“歌词查询”等。

---

In/Out-component：指图中那些节点能够到达当前节点的集合（包含当前节点在内）/指图中从当前节点可以到达那些节点的集合（包含当前节点在内）

Strongly connected components of the graph:强连通分量（SCC）是满足以下性质的节点的集合$S$：

1. 在$S$中的任何一对节点都可以互相到达
2. 没有包含$S$的更大的集合满足上述性质

所有有向图都是基于它的强连通分量的有向无环图。就是将有向图中的所有强连通分量看做一个节点，那么这些新节点组成的新有向图（原来图中的强连通分量）是一个有向无环图（环都变成节点了，当然就变成无环图了呀）
这个结论对于今天要学习的算法还蛮重要。
因此先要学会找强连通分量（隐含上周作业解决方案。。。）：
找出一个图的In/Out-component两个集合，求他们的交集，就是该图的SCC
经过科学家（大佬们）的实验，得出结论：Bowtie Structure of Web

PageRank：给网页的“重要性”排名

创建搜索引擎有三步：
1.使用爬虫类工具爬取网页数据并建库
2.创建倒排索引（inverted index），使得搜索引擎可以快速根据关键词找到包含这个词的网页
3.用PageRank根据重要性对搜索结果进行排序

本次课主要针对第三点进行讲解，早期的搜索引擎对于网页重要性排序有两种方式：
1.不排序，直接出结果
2.根据关键字匹配数量进行排序（网页可以针对这个算法大量注入大量关键字）

对于Pagerank算法：

基本的PageRank算法

PageRank算法利用网络的图结构来评价网页的重要性，这里的图结构是指指向网页的链接，也就是Inlink。PageRank算法有两种假设：
数量假设：指向该网站的数量越多，重要性越高
质量假设：指向该网站越权威，重要性越高（每个链接权重不一样）
PageRank模型的描述如下：
网页$i$的rank（重要度）是$r_i$，有$d_i$个outlinks，那么每个链接获得$\frac{r_i}{d_i}$权重的投票；
网页$j$的rank（重要性） $r_j$是它的inlinks的投票权重的总和，$r_j$定义如下：
$$r_j=\sum _{i\to j}\frac{r_i}{d_i}\text{\hspace{1em}(1)}$$
例子：

上图中三个节点$r_a,r_b,r_c$的重要性可以列出如下线性方程组：
$$\{\begin{array}{l}{r}_a=r_c+r_b/2\\ r_b=r_b/2+r_a/2\\ r_c=r_a/2\end{array}$$
当然还有一个额外的约束：
$$r_a+r_b+r_c=1$$
解出来为：$r_a=\frac{2}{5},r_b=\frac{2}{5},r_c=\frac{1}{5}$
当节点较少的时候，还可以消元法解一下，如果计算互联网上上亿个节点就需要用特殊的优化方法：

PageRank的矩阵表达

Column stochastic (列随机) 矩阵$M$(每一个列上的元素之和为1，暗暗符合上面的图中约束条件，当然还有行随机矩阵和双随机矩阵)，我们假设网页$j$有$d_j$个外链接，假设第$j$个外链接是指向$i$网页，那么：
$$M_{ij}=\frac{1}{d_j}$$
将某个网页$i$的重要度$r$看做一个向量，且满足所有网页的重要度和为1：${\sum }_i{r}_i=1$，那么公式1的矩阵表达如下：
$$r=M\cdot r\text{\hspace{1em}(2)}$$

---

根据特征向量的定义可知：若
$$Ax=\lambda x$$
则$x$为矩阵$A$的特征值为$\lambda$的特征向量
把公式2写成：
$$1\cdot r=M\cdot r$$
则重要度向量$r$是矩阵$M$对应特征值为1的特征向量

---

PageRank的矩阵表达实例

先把上面的图拉下来：

写出上图的(列随机) 矩阵$M$
$$\begin{array}{cccc}& r_a& r_b& r_c\\ r_a& 0& 1/2& 1\\ r_b& 1/2& 1/2& 0\\ r_c& 1/2& 0& 0\end{array}$$
根据公式2：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{ccc}0& 1/2& 1\\ 1/2& 1/2& 0\\ 1/2& 0& 0\end{array}\right]\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]$$
展开就是对应的方程组：
$$\{\begin{array}{l}{r}_a=r_b/2+r_c\\ r_b=r_a/2+r_b/2\\ r_c=r_a/2\end{array}$$

从Markov的角度来看PageRank

这块听懂了定义，最后的平稳分布没懂的可以看这里(https://blog.csdn.net/qq_34652535/article/details/85343518)
定义：

考虑一个网上的随机冲浪者在时间t，在网页i在时间t+1，沿着网页i的outlinks uniformly at random（就是按出度均匀分布概率1/dj），到达网页i指向的另一网页j
无限重复以上的步骤

冲浪者在图中随机游走的过程就是一个马尔科夫链，记向量$p(t)$为冲浪者时间步$t$到达网页$i$的概率
$p(t)$可以看做所有网页的一个概率分布
M就相当于马尔科夫中的状态转移矩阵，因此在$t+1$时刻，冲浪者位置：
$$p(t+1)=M\cdot p(t)$$

当随机游走到达以下状态时
$$p(t+1)=M\cdot p(t)=p(t)$$
$p(t)$为该随机游走的平稳分布
对比公式2，可知：$r$就是在网络图上随机游走的平稳分布。

Power Iteration Method

上面讲完我们知道了，现在要找重要度向量，实际上就是要求转移矩阵M的特征值为1的特征值向量。求这个特征向量的方法就是Power Iteration Method，该方法是求绝对值最大的特征值向量的方法：
假设图中有N个网页，且将网页看做节点，把超链接看做有向边。使用Power Iteration求特征向量$r$的步骤为：
1.初始化（随机选点）：$r^{(0)}=[\frac{1}{N},\cdots ,\frac{1}{N}{]}^T$
2.Iteration循环（相当开始随机游走）：$r^{(t+1)}=M\cdot r^{(t)}$
3.循环终止条件（达到平稳分布）：$|r^{(t+1)}-r^{(t)}{|}_1<ϵ$
其中：
$$r_j^{(t+1)}=\sum \frac{r^{(t)}}{d_i}$$
下面就用这个方法来重新算一下上面三个网页的例子：

三个网页，每个网页作为起始点的概率为$\frac{1}{N}=\frac{1}{3}$
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1/3\\ 1/3\\ 1/3\end{array}\right]$$
下面开始乘转移矩阵（https://zs.symbolab.com/solver/matrix-multiply-calculator）：
$$\left[\begin{array}{ccc}0& 1/2& 1\\ 1/2& 1/2& 0\\ 1/2& 0& 0\end{array}\right]$$
开始第1次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1/2\\ 1/3\\ 1/6\end{array}\right]$$
第2次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1/3\\ 5/12\\ 1/4\end{array}\right]$$
第3次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}11/24\\ 3/8\\ 1/6\end{array}\right]$$
第4次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}17/48\\ 5/12\\ 11/48\end{array}\right]$$
第5次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}7/16\\ 37/96\\ 17/96\end{array}\right]$$
第6次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}71/192\\ 79/192\\ 7/32\end{array}\right]$$
第7次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}163/384\\ 25/64\\ 71/384\end{array}\right]$$
第8次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}73/192\\ 313/768\\ 163/384\end{array}\right]$$
第9次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}213/512\\ 605/1536\\ 73/384\end{array}\right]$$
第10次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1189/3072\\ 311/768\\ 213/1024\end{array}\right]$$
第11次：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1261/3072\\ 811/2048\\ 1189/6144\end{array}\right]$$
$$\left(\begin{array}{c}\frac{4811}{12288}\\ \frac{4955}{12288}\\ \frac{1261}{6144}\end{array}\right)$$
$$\left(\begin{array}{c}\frac{3333}{8192}\\ \frac{4883}{12288}\\ \frac{4811}{24576}\end{array}\right)$$
$$\left(\begin{array}{c}\frac{4847}{12288}\\ \frac{19765}{49152}\\ \frac{3333}{16384}\end{array}\right)$$
$$\left(\begin{array}{c}\frac{39763}{98304}\\ \frac{13051}{32768}\\ \frac{4847}{24576}\end{array}\right)$$
…
最后应该是：
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}2/5\\ 2/5\\ 1/5\end{array}\right]$$

缺点

无法处理以下两种情况：
1.网页只有入度没有出度Dead End
第一种情况中，在经过若干时间步随机游走之后，会使得网页重要性向量趋向于0（leaky rank现象）。原因是在随机游走的时候，不断乘上的转移矩阵是列随机矩阵，其每列和为1，而由网页只有入度没有出度，会导致转移矩阵中某列和为0，因此会使得最后相乘结果为0。
2.网页即使有出度也是指向其本身Spider Traps
第二种情况中，转移矩阵本来就是比较稀疏的，导致网页重要性向量不平滑，由于Spider Traps的存在，会加剧这种不平滑的现象，使得这些指向自己的节点的重要性加大。
第一种情况Dead End是一个大问题；第二种情况Spider Traps不会对收敛性产生影响，但收敛到的PageRank不是我们想要的

解决方法：teleport（随机跳转）

进阶版本的PageRank

在每个时间点t，随机冲浪者有两个选择：沿着一个随机的边去它的相邻网页，概率=𝛽Teleport（随机跳转）到任意一个随机选择的其他网页，概率=1-𝛽𝛽一般在0.8-0.9之间

可以看到，Teleport可以有1-𝛽的概率跳出Dead End或者Spider Traps，当然每个网页被随机跳转到的概率是一样的。
例如下面三个网页（C节点是Dead End），
其转移矩阵为：
$$\begin{array}{cccc}& r_a& r_b& r_c\\ r_a& 0& 1/2& 0\\ r_b& 1/2& 1/2& 0\\ r_c& 1/2& 0& 0\end{array}$$
加入Teleport后，转移概率矩阵就变成了：
$$\begin{array}{cccc}& r_a& r_b& r_c\\ r_a& 0& 1/2& 1/3\\ r_b& 1/2& 1/2& 1/3\\ r_c& 1/2& 0& 1/3\end{array}$$
注意新的转移矩阵还是列随机矩阵。
这里就得到了PageRank的形式[Brin-Page,1998]：
$$r_j=\sum _{i\to j}\beta \frac{r_i}{d_i}+(1-\beta )\frac{1}{N}$$
要对Dead End节点进行预处理，两种方式，第一种是直接在转移矩阵中去掉Dead End节点，另外是直接将其转移概率设置为1/N。上式写成矩阵方式：
$$A=\beta M+(1-\beta )[\frac{1}{N}{]}_{N\times N}\text{\hspace{1em}(3)}$$

Teleport例子

就用这个方法来重新算一下上面三个网页的例子：

$$M=\left[\begin{array}{ccc}0& 1/2& 1\\ 1/2& 1/2& 0\\ 1/2& 0& 0\end{array}\right],[\frac{1}{N}{]}_{N\times N}=\left[\begin{array}{ccc}1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\end{array}\right]$$
假设取$\beta =0.8$，将上面的东东代入公式3可得：
$$0.8M+(1-0.8)[\frac{1}{N}{]}_{N\times N}=0.8\left[\begin{array}{ccc}0& 1/2& 1\\ 1/2& 1/2& 0\\ 1/2& 0& 0\end{array}\right]+0.2\left[\begin{array}{ccc}1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\end{array}\right]$$
$$=\left[\begin{array}{ccc}\frac{1}{15}& \frac{7}{15}& \frac{13}{15}\\ \frac{7}{15}& \frac{7}{15}& \frac{1}{15}\\ \frac{7}{15}& \frac{1}{15}& \frac{1}{15}\end{array}\right]$$
也就是图变成了：

其中红色箭头是原来转移矩阵中没有边的部分。
然后就是一样的，三个网页，每个网页作为起始点的概率为$\frac{1}{N}=\frac{1}{3}$
$$\left[\begin{array}{c}{r}_a\\ r_b\\ r_c\end{array}\right]=\left[\begin{array}{c}1/3\\ 1/3\\ 1/3\end{array}\right]$$
开始在左边乘A，一直乘到收敛为止

PageRank计算效率分析

可以看到上面的计算过程中的关键步骤为：
$$r^{t+1}=A\cdot r^t$$
A相对于M来说，M是初始的转移矩阵，是比较稀疏的，存储起来还行，但是加上瞬移后，变成A后就是密集矩阵了，每个位置都有值，假如我们有上亿个网页，这个玩意的存储和计算都是问题。
下面是推导过程：

---

$$r_j=\sum _{i\to j}\beta \frac{r_i}{d_i}+(1-\beta )\frac{1}{N}$$
$$A=\beta M+(1-\beta )[\frac{1}{N}{]}_{N\times N}$$

开始：
$$\begin{array}{rl}r& =A\cdot r,\text{where }{A}_{ij}=\beta M_{ij}+\frac{1-\beta }{N}\\ r_i& =\sum _{j=1}^N{A}_{ij}\cdot r_j\\ & =\sum _{j=1}^N\left[\beta M_{ij}+\frac{1-\beta }{N}\right]\cdot r_j\\ & =\sum _{j=1}^N\beta M_{ij}\cdot r_j+\sum _{j=1}^N\frac{1-\beta }{N}{r}_j,由于\sum r_j=1\\ & =\sum _{j=1}^N\beta M_{ij}\cdot r_j+\frac{1-\beta }{N}\\ & =\beta \sum _{j=1}^N{M}_{ij}\cdot r_j+\frac{1-\beta }{N}\\ r& =\beta M\cdot r+[\frac{1-\beta }{N}{]}_N\end{array}$$
其中$[\frac{1-\beta }{N}{]}_N$是N个元素都为$\frac{1-\beta }{N}$的向量

---

可以看到结果不需要用稠密矩阵A，而是用稀疏矩阵M来求解r（M中的Dead End要进行处理，有Dead End转移矩阵每列和会小于1 ，因此要对该列进行重新归一化。）

最终版本的完整算法

输入：网络图$G$和瞬移参数$\beta$，图中可以出现Dead Ends和Spider Traps
输出：网页的重要程度PageRank向量$r$
1.设置在第一个时间不的初始化PageRank向量：$r_j^{(0)}=\frac{1}{N},t=1$
2.开始循环，直到${\sum }_j|r_j^{(t)}-r_j^{(t-1)}|<ϵ$：
$$\begin{gathered} \forall j:{r^{\prime }}_j^{(t)}=\sum _{i\to j}\beta \frac{r_i^{(t-1)}}{d_i} \\ \text{if }j\text{ 入度为0: }{r^{\prime }}_j^{(t)}=0 \end{gathered}$$
$$\begin{gathered} \forall j:r_j^{(t)}={r^{\prime }}_j^{(t)}+\frac{1-S}{N} \\ S=\sum _j{r^{\prime }}_j^{(t)} \end{gathered}$$
t=t+1

基于主题的Topic-specific PageRank

原始的pagerank算法只能提供通用的importance score。
目标：不只是根据importance score来评估网页，而是加上该网页离某个主题的距离，例如运动、娱乐、历史等。
就是要考虑各种权重。

方法

改变随机转移的网页集合
·原始PageRank：任意网页
·基于主题的PageRank：和该主题有关的事先选择好的网页集合（teleport set）
有偏随机游走（Bias the Random Walk）
·冲浪者随机转移到在主题有关的teleport set $S$中的一个网页
·每一个不同的teleport set $S$，会得到一个对应的PageRank向量$r_s$

矩阵表达

只需要改变原始PageRank中的随机转移的部分
$$A_{ij}=\{\begin{array}{ll}\beta M_{ij}+\frac{(1-\beta )}{|S|}& \text{ if }i\in S\\ \beta M_{ij}+0& \text{ otherwise }\end{array}$$
可以这样理解，随机冲浪者不再随机跳转到所有网页了，而是随机跳转到所有网页的某个子集合$S$，这个子集合和某个主题有关。