type
status
date
slug
summary
tags
category
icon
password
Pagerank算法
PageRank算法是参照论文引用影响力的算法，是属于图论的影响力模型。
简介
在互联网的早期历史中，PageRank 算法被引入作为一种评估网页重要性的方法。简而言之，PageRank 是一个定义在整个网页集合上的函数，为每个网页分配一个正实数，代表该网页的重要性。这些数值组成一个向量，其中较高的 PageRank 值意味着该网页在重要性上的优势，因此在搜索结果中可能会被优先显示。
可以将整个互联网视为一个巨大的有向图，其中每个网页是一个节点，而超链接则是从一个页面指向另一个页面的有向边。基于这个视角，我们可以构建一个随机游走模型，也就是一阶马尔可夫链。在这个模型中，我们假设一个虚拟的网页浏览者会随机地、按照等概率地跟随一个页面上的任何一个超链接到另一个页面，并持续这种随机跳转。在长时间内，这种随机跳转的行为会形成一个稳定的模式，即马尔可夫链的平稳分布。每个网页的 PageRank 值，实际上就是在这个平稳分布中的概率。
PageRank 的核心思想是基于有向图上的随机游走模型，这是一个一阶马尔可夫链。该模型描述了一个随机游走者如何沿着图的边随机移动，从一个节点访问到另一个节点。在满足某些条件的前提下，这个随机游走过程最终会收敛到一个平稳分布。在这个平稳分布中，每个节点被访问的概率即为其 PageRank 值，这个值可以被解释为节点的重要性。值得注意的是，PageRank 是递归定义的，这意味着一个页面的 PageRank 值部分地取决于链接到它的其他页面的 PageRank 值。因此，计算 PageRank 值通常需要迭代方法。
原理
有向图
有向图(directed graph)记作 ，其中V和E分别表示结点和有向边的集合。
随机游走模型
给定一个含有n个结点的有向图，在有向图上定义随机游走（random walk）模型，即一阶马尔可夫链，其中结点表示状态，有向边表示状态之间的转移，假设从一个结点到通过有向边相连的所有结点的转移概率相等。
具体地，转移矩阵是一个n阶矩阵
第i行第j列的元素取值规则为：如果节点j出度为k
在有向图上的随机游走形成马尔可夫链。也就是说，随机游走者每经一个单位时间转移一个状态，如果当前时刻在第i个结点（状态），那么下一个时刻在第j个结点（状态）的概率是这一概率只依赖于当前的状态，与过去无关，具有马尔可夫性。
例：
随机游走在某个时刻t访问各个结点的概率分布就是马尔可夫链在时刻t的状态分布，可以用一个n维列向量表示，那么在时刻t+1访问各个结点的概率分布满足
例：假设初始时刻概率分布为
当进行第一次转移后
经过n次迭代后，收敛即存在，极限向量R表示马尔可夫链的平稳分布
PageRank基本定义
平稳分布R称为这个有向图的 PageRank。
R的各个分量称为各个结点的PageRank值。
表示指向结点的结点集合，表示结点连出的有向边的个数。
如果一个结点没有出度或入度会怎样？
- 等级泄露（Rank Leak）：如果一个网页没有出链，就像是一个黑洞一样，吸收了其他网页的影响力而不释放，最终会导致其他网页的 PR 值为 0。
- 等级沉没（Rank Sink）：如果一个网页只有出链，没有入链（如下图所示），计算的过程迭代下来，会导致这个网页的 PR 值为 0（也就是不存在公式中的 V）。
PageRank一般定义
随机浏览模型
在基本定义的基础上导入平滑项，由于采用平滑项，所有结点的 PageRank 值都不会为 0
一般 PageRank 的定义意味着互联网浏览者，按照以下方法在网上随机游走：任意一个网页上，浏览者或者以概率d决定按照超链接随机跳转，这时以等概率从连接出去的超链接跳转到下一个网页；或者以概率(1−d)决定完全随机跳转，这时以等概率1/n跳转到任意一个网页。 第二个机制保证从没有连接出去的超链接的网页也可以跳转出。这样可以保证平稳分布，即一般 PageRank 的存在，因而一般 PageRank 适用于任何结构的网络。
参考
六度空间
六度空间理论（Six Degrees of Separation），也常被称为“六度分隔理论”或“小世界现象”（“small world” phenomenon），是一个社会心理学的理论。它提出了这样一个观点：任何两个人之间，只需通过五个或更少的中间联系，就可以建立起一种社交联系。换句话说，这个理论认为在这个世界上，任何一个人都可以通过“朋友的朋友”的连锁反应，在最多六步之内与任何其他人建立联系。
实现及验证
实现
随机生成网络
计算pagerank
六度空间
验证
随机生成结点数为n的网络，计算符合六度空间理论的节点百分比
- 作者:Rainnn
- 链接:https://tangly1024.com/article/cc4fe2c8-d929-44f6-821d-264a9f1e5d6e
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。