网络营销具有哪些特点,苏州seo公司排名,手机音乐网站源码,馆陶网站建设电话文章目录1. PageRank 的定义1.1 基本想法1.2 PageRank 的基本定义1.3 PageRank 的一般定义2. PageRank 的计算2.1 迭代算法2.2 幂法2.3 代数算法PageRank算法是图的链接分析#xff08;link analysis#xff09;的代表性算法#xff0c;属于图数据上的无监督学习方法。
Pag…
文章目录1. PageRank 的定义1.1 基本想法1.2 PageRank 的基本定义1.3 PageRank 的一般定义2. PageRank 的计算2.1 迭代算法2.2 幂法2.3 代数算法PageRank算法是图的链接分析link analysis的代表性算法属于图数据上的无监督学习方法。
PageRank算法最初作为互联网网页重要度的计算方法1996年由Page和Brin提出并用于谷歌搜索引擎的网页排序。 事实上PageRank可以定义在任意有向图上后来被应用到社会影响力分析、文本摘要等多个问题。 PageRank算法基本想法
在有向图上定义一个随机游走模型即一阶马尔可夫链描述随机游走者沿着有向图随机访问各个结点的行为在一定条件下极限情况访问每个结点的概率收敛到平稳分布这时各个结点的平稳概率值就是其PageRank值表示结点的重要度PageRank是递归定义的PageRank的计算可以通过迭代算法进行
1. PageRank 的定义
1.1 基本想法
PageRank是定义在网页集合上的一个函数对网页给出一个正实数表示网页的重要程度整体构成一个向量PageRank值越高网页就越重要在互联网搜索的排序中可能就被排在前面
假设互联网是一个有向图在其基础上定义随机游走模型即一阶马尔可夫链表示网页浏览者在互联网上随机浏览网页的过程假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页并在网上持续不断进行这样的随机跳转这个过程形成一阶马尔可夫链PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank 值就是平稳概率
1.2 PageRank 的基本定义
给定一个包含 nnn 个结点 v1v2…vnv_1v_2…v_nv1v2…vn 的强连通且非周期性的有向图在有向图上定义随机游走模型即一阶马尔可夫链。 随机游走的特点是从一个结点 到有 有向边连出的所有结点的转移概率相等转移矩阵为M。这个马尔可夫链具有平稳分布 R, MRRMRRMRR
平稳分布 R 称为这个有向图的 PageRank。R的各个分量称为各个结点的PageRank值
其中PR(vi),i1,2,⋯,n,P R\left(v_{i}\right), i1,2, \cdots, n,PR(vi),i1,2,⋯,n, 表示结点 viv_{i}vi 的 PageRank 值 R[PR(v1)PR(v2)⋮PR(vn)]PR(vi)⩾0,i1,2,⋯,n∑i1nPR(vi)1PR(vi)∑vj∈M(vi)PR(vj)L(vj),i1,2,⋯,n\begin{array}{c}R\left[\begin{array}{c}P R\left(v_{1}\right) \\ P R\left(v_{2}\right) \\ \vdots \\ P R\left(v_{n}\right)\end{array}\right] \\ \begin{array}{c} \\P R\left(v_{i}\right) \geqslant 0, \quad i1,2, \cdots, n \\ \\ \sum\limits_{i1}^{n} P R\left(v_{i}\right)1\end{array} \\ \begin{array}{l}\\ P R\left(v_{i}\right)\sum\limits_{v_{j} \in M\left(v_{i}\right)} \frac{P R\left(v_{j}\right)}{L\left(v_{j}\right)}, \quad i1,2, \cdots, n\end{array}\end{array}R⎣⎢⎢⎢⎡PR(v1)PR(v2)⋮PR(vn)⎦⎥⎥⎥⎤PR(vi)⩾0,i1,2,⋯,ni1∑nPR(vi)1PR(vi)vj∈M(vi)∑L(vj)PR(vj),i1,2,⋯,n M(vi)M(v_i)M(vi) 表示指向节点 viv_ivi 的节点集合L(vj)L(v_j)L(vj) 表示节点 vjv_jvj 连出的有向边个数 定理 不可约且非周期的有限状态马尔可夫链有唯一平稳分布存在并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。 一般的有向图未必满足强连通且非周期性的条件比如在互联网大部分网页没有连接出去的超链接也就是说从这些网页无法跳转到其他网页。所以PageRank的基本定义不适用
1.3 PageRank 的一般定义
有 n 个结点的任意有向图定义一个一般的随机游走模型即一阶马尔可夫链。 一般的随机游走模型的转移矩阵由两部分的线性组合组成
一部分是有向图的基本转移矩阵M表示从一个结点到其连出的所有结点的转移概率相等另一部分是完全随机的转移矩阵表示从任意一个结点到任意一个结点的转移概率都是1/n线性组合系数为阻尼因子 d0≤d≤1d0≤d≤1d0≤d≤1
这个一般随机游走的马尔可夫链存在平稳分布记作 R。 定义平稳分布向量R为这个有向图的一般PageRank。R由公式 RdMR1−dn1R dMR\frac{1-d}{n} \bf1RdMRn1−d1 决定1\bf 11 是所有分量为 1 的 n 维向量
PR(vi)d(∑vj∈M(vi)PR(vj)L(vj))1−dn,i1,2,⋯,nP R\left(v_{i}\right)d\left(\sum_{v_{j} \in M\left(v_{i}\right)} \frac{P R\left(v_{j}\right)}{L\left(v_{j}\right)}\right)\frac{1-d}{n}, \quad i1,2, \cdots, nPR(vi)d⎝⎛vj∈M(vi)∑L(vj)PR(vj)⎠⎞n1−d,i1,2,⋯,n
一般PageRank的定义意味着互联网浏览者
在任意一个网页上浏览者或者以概率 d 决定按照超链接随机跳转这时以等概率从连接出去的超链接跳转到下一个网页或者以概率1-d决定完全随机跳转这时以等概率1/n跳转到任意一个网页第二个机制保证从没有连接出去的超链接的网页也可以跳转出。这样可以保证平稳分布即一般PageRank的存在
2. PageRank 的计算
包括迭代算法、幂法、代数算法。常用的方法是 幂法
2.1 迭代算法
输入含有 n 个结点的有向图转移矩阵 M阻尼因子 d初始向量 R0 输出有向图的 PageRank 向量 R
令 t0t0t0计算 Rt1dMRt1−dn1R_{t1} dMR_t\frac{1-d}{n}\bf1Rt1dMRtn1−d1如果 Rt1R_{t1}Rt1 与 RtR_tRt 充分接近令 RRt1RR_{t1}RRt1停止迭代否则令 tt1tt1tt1执行步 2
2.2 幂法
输入含有 n 个结点的有向图转移矩阵 M系数 d初始向量 x0计算精度 ε\varepsilonε 输出有向图的 PageRankR
令 t0t0t0选择初始向量 x0x_0x0计算有向图的一般转移矩阵 A AdM1−dnEAdM\frac{1-d}{n}\bf EAdMn1−dEE\bf EE 是所有元素为1的n阶方阵迭代并规范化结果向量 yt1Axty_{t1} Ax_tyt1Axt xt1yt1∣∣yt1∣∣\quad \quad x_{t1} \frac{y_{t1}}{||y_{t1}||}xt1∣∣yt1∣∣yt1当 ∣∣xt1−xt∣∣ε||x_{t1}-x_t|| \varepsilon∣∣xt1−xt∣∣ε 时令 RxtRx_tRxt停止迭代否则令 tt1tt1tt1执行步 3对 R 进行规范化处理使其表示概率分布
2.3 代数算法
代数算法 通过一般转移矩阵的逆矩阵计算求有向图的一般 PageRank 按照PR的一般定义RdMR1−dn1Rd M R\frac{1-d}{n} \mathbf{1}RdMRn1−d1 于是有 (I−dM)R1−dn1(I-d M) R\frac{1-d}{n} \mathbf{1} (I−dM)Rn1−d1 R(I−dM)−11−dn1R(I-d M)^{-1} \frac{1-d}{n} \mathbf{1}R(I−dM)−1n1−d1 这里 I\bf II 是单位矩阵。 当 0d10d10d1 时上面方程的解存在且唯一 可以通过求逆矩阵 (I−dM)−1(I-d M)^{-1}(I−dM)−1 得到有向图的一般 PageRank
