PageRank算法

PageRank的基本思想

PageRank算法是谷歌搜索引擎中用于评估网页重要性的核心算法之一。该算法由谷歌创始人拉里·佩奇和谢尔盖·布林在1998年提出，并成为谷歌搜索引擎的基础。

PageRank算法的核心思想是，通过分析网页之间的链接关系，将网页作为节点，将所有网络转化为一个有向图。它认为被更多网页指向的网页更重要（比如说博客，大佬的博客有很多友链，我只有少数大佬的友链，说明我的博客很垃圾），从而定义了每个网页的重要程度，即PageRank值，简称PR值。

假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程。假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank值就是平稳概率。

PageRank的一般定义

给定一个含有$n$个结点$v_i,i=1,2,\cdots,n$的任意有向图，则每个节点的PR值一般定义如下式：
$$
PR(v_i)=d(\sum_{v_j \in N(v_i)}\frac{PR(v_j)}{DE(v_j)})+\frac{1-d}{n},i=1,2,\cdots,n.
$$
其中$d$为阻尼系数由经验决定，一般令$d=0.85$，$DE(v_j)$为节点$v_j$的度，$N(v_i)$为$v_i$的邻居节点。并且有$\sum_{i=1}^{n} PR(v_i)=1$.

在实际应用中PR值往往是一个时变的数，由迭代产生每个时刻的PR值。对于第$i$个节点，$t=0$时每个节点的PR值相等为$\frac{1}{n}$。$t>0$时，PR值定义如下：
$$
PR_i(t)=d(\sum_{v_j \in N(v_i)}\frac{\rho_{ij} PR_j(t)}{DE(v_j)})+\frac{1-d}{n},i=1,2,\cdots,n.
$$
其中$\rho_{ij}=DE(v_i)+DE(v_j)$代表了边的权值。这样待迭代至最终就可以生成每个节点的PR值。

参考文献：
CDS-Based Topology Control in FANETs via Power and Position Optimization.
DOI：10.1109/LWC.2020.3009666