定州网站设计,南宁建设集团招聘信息网站,游戏充值网站怎么做,wordpress语言代码参考资料#xff1a;改变世界的谷歌PageRank算法
pagerank算法用于计算节点重要度
思想
如果网页被更多的入度(被引用)#xff0c;则网页更重要。 被重要网站引用比被普通网站引用更加凸显重要性。 所以考虑一个网站是否重要#xff0c;需要看引用它的网站是否重要#…参考资料改变世界的谷歌PageRank算法
pagerank算法用于计算节点重要度
思想
如果网页被更多的入度(被引用)则网页更重要。 被重要网站引用比被普通网站引用更加凸显重要性。 所以考虑一个网站是否重要需要看引用它的网站是否重要这就成了一个递归的问题。
理解pagerank的五个角度
迭代求解线性方程组 例子 这里看上去有三个方程三个未知数其实只有2个方程。 虽然高斯消元可以求解但是可扩展性较差。 节点j的rank值 r j r_j rj是考虑所有到 j j j的节点的rank值各自除以它的出度再求和。 迭代求解 迭代左乘M矩阵
迭代的过程用矩阵表示(左边的矩阵的i行j列 A i j 有非零值 A_{ij}有非零值 Aij有非零值表示存在第j个节点到第i个节点的有向边) 左边的矩阵称为列概率矩阵(列转移矩阵/列替代矩阵column stochastic matrix) 右边的向量叫pagerank向量 矩阵的特征向量
迭代公式 r M ⋅ r rM \cdot r rM⋅r其实可以看作是 1 ⋅ r M ⋅ r 1 \cdot rM \cdot r 1⋅rM⋅r 从这个角度看pagerank向量就是M矩阵的特征值为1的特征向量。 对于Column Stochastic矩阵由Perreon-Frobenius定理最大的特征值就是1且存在唯一的主特征向量(特征值1对应的特征向量)向量所有元素求和为1。 通过幂迭代的方式可以快速求解pagerank向量。 随机游走
随机游走-计数求和-归一化为概率得到的就是pagerank向量。
马尔科夫链 求解pagerank 收敛性分析 1. 是否收敛-收敛收敛到同一个结果
Ergodic Theorem
根据Ergodic Theorem对于不可约(irreducible)和非周期(aperiodic)的马尔可夫链 1.存在一个唯一的稳定的马尔科夫分布 2.并且所有初始分布收敛到同一个分布
可约(reducible)马尔可夫链和不可约马尔可夫链
可约是存在孤立的状态 不可约是所有状态都可达
周期马尔可夫链和非周期马尔可夫链 2.结果是不是代表重要度-两类问题
Spider trap问题
所有的出度边都在group里面导致这个group吸收了所有的重要度
dead end问题
没有出度重要度最终为0 对于这两种情况即使收敛了也不是合理的网络重要度。
例子 解决办法
spider trap问题的解决办法 dead end的解决办法 最终解决办法 pagerank的升级-mapreduce的工作 pagerank算法用于计算节点相似度-用于推荐系统
给定一个bipartite graph用于表示用户和商品的交互 目标寻找与指定节点最相似的节点 假设被同一个用户访问过的节点更可能是相似的
pagerank随机游走视角的启发
pagerank的一种解释是随机游走并有概率随机传送到网络中的任意一个节点继续游走 Topic-Specific PageRank(也称为personalized pagerank)随机游走并有传送到指定的一些节点继续游走 random walks with restarts随机游走并有传送到指定的一个节点继续游走
随机游走访问次数-相似性的度量
给定一个节点集query_nodes模拟一个随机游走
记录访问次数在概率 α \alpha α下在query_nodes中重启walk有高访问次数的节点则和query_nodes中的点有更高的相似性
伪代码 优点 代码实战
参考资料https://www.bilibili.com/video/BV1Wg411H7Ep/?p16spm_id_frompageDriver
