PageRank算法与Influence Propagation
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了PageRank算法与Influence Propagation，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4888字，纯文字阅读大概需要7分钟。
内容图文
PageRank算法
PageRank基本理念
PageRank算法的目的是：标记网页的重要性的一种方法，用以衡量网页的质量的好坏，来调整搜索的排序结果，PageRank算法借鉴学术界论文重要性的评估方法：谁被引用的次数多，谁就越重要
核心思想：
（1）如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
（2）如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高
- 算法原理
几个基本概念：
- 入链：页面A增加了指向页面B的超链接，则B有来自于A的入链，或用户直接通过url进入B，则为url到B的入链
- 出链：页面A增加了指向页面B的超链接，则A出链到B
- 无出链/只对自己出链：页面不再指向新的页面或只指向自己
- PR值：一个网页的PR值，概率上理解就是此网页被访问的概率，PR值越高其排名越高
网页都有出入链
所有的网页都有出链和入链，图是强连通的，从任一点出发可以遍历整个图，为了简化计算
我们可以假设当一个用户停留在某页面时，他跳转到页面所指向的其他页面的概率是相同的
即上图中页面B有两个出链，则从B跳转到A和B跳转到D的概率为相同，为1/2
计算页面A的PR值：PR(A) = PR(C) + PR(B)/2
如此我们可以用转移矩阵来描述页面之间跳转的概率
其中 
的值表示用户从页面j跳转到页面i的概率
假设初始时刻每个页面有一个初始的PR值为1/N（假设出初始时刻所有的页面的权重是相同的），这里就是1/4，得到PageRank的一个向量
则表示了经过一次迭代（页面转移）后各个页面的更新后的PR值
持续迭代这个过程，最终收敛
存在没有出链的网页
上述的案例的前提是网页是强连通的，事实上真实的网络并不是强连通的， 其中会存在一些没有出链的节点， 也可以叫做 dead ends
如上图所示，网页C是没有出链。因为C没有出链，所以对A,B,D网页没有PR值的贡献。在转移矩阵中对应的转移概率均为0， 这样会导致上述计算过程最终收敛为0。
为了解决这个问题，可以假设dead end对所有的页面都有出链
存在仅对自己有出链的（spider trap）
可以预见，如果把真实的Web组织成转移矩阵，那么这将是一个极为稀疏的矩阵，从矩阵论知识可以推断，极度稀疏的转移矩阵迭代相乘可能会使得向量v变得非常不平滑，即一些节点拥有很大的rank，而大多数节点rank值接近0。而一种叫做Spider Traps节点的存在加剧了这种不平滑。
节点C有出链所以不是Dead Ends，但是它只链向自己（注意链向自己也算外链，当然同时也是个内链）。这种节点叫做Spider Trap，如果对这个图进行计算，会发现C的rank越来越大趋近于1，而其它节点rank值几乎归零。
为了克服这种现象，假定当一个用户在某个页面停留的时候，出了根据当前页面的出链进行跳转，还有一定的概率随机的跳转到其他任意的页面（通过url跳转等）不管这两个页面是否有链接
加入这种随机转移概率后，迭代公式发生变化
通常β的值取值较小（如0.2、0.15等），e为单位向量
如果按这个公式迭代算下去，会发现Spider Traps的效应被抑制了，从而每个页面都拥有一个较为合理的pagerank。
- 相关证明
如前所述， pagerank用户在经过很长——理论上为无穷长——时间的漫游后访问各网页的几率分布， 即 
， 来确定网页排序的。 这个定义要想管用， 显然要解决两个问题：
- 极限 是否存在？
- 如果极限存在， 它是否与 p0 的选取无关？
我们可以做一下转换
则v的n+1次迭代的结果仅与第n次迭代结果相关，于是计算PR值的过程就变成了一个 Markov 过程，随机过程理论中有一个所谓的马尔可夫链基本定理 (fundamental theorem of Markov chains)， 它表明在一个马尔可夫过程中， 如果转移矩阵是素矩阵， 那么上述前两个问题的答案就是肯定的，如果这个 Markov 过程收敛，那么 
存在，且与P0的选取无关。
Influence Propagation
影响力传播主要在于研究社交网络，并寻求一个影响力最大化的问题，在市场营销，广告发布等方面会有一定的应用。
影响力传播模型：
将社交网络描述成一个图G(V,E)，其中V是网络中用户节点的集合，E是用户与用户之间关系的描述。网络中的节点存在两种状态：激活、未激活。当一个节点激活时，它对于它所指向的节点具有影响力。当一个节点周围有越来越多的节点被激活时，则它被激活的概率也上升。每个节点只能由未激活状态转换成激活状态，不能反向转化
影响力最大化要解决的问题是：如何选取k个种子节点进行信息传播，并使最终被激活的节点最多
- 独立级联模型（IC模型）
- 初始活跃节点集合S，其中点v在t时刻激活，则它对其邻居w进行一次影响传播的尝试，成功的概率为Pvw
- 当节点w在t时候有多个邻居节点处于被激活状态，则多个邻居节点以任意顺序尝试激活节点w，如w被成功激活，则在t+1时刻，w状态变为激活状态，并对其邻居节点进行影响
- 当一个节点处于被激活状态，且已经尝试激活其邻居节点后，节点处于激活状态，但已无影响力，当网络中的不存在有影响力的的活跃节点时，迭代结束
问题：
- 只考虑节点v与出边邻居w的关系，不考虑其他节点对于w造成的影响
- 由于概率模型，激活过程不确定，同样的种子、同样的网络，运行多次结果不一致
- 线性与之模型（LT模型）
- 对于节点v存在一个阈值θv，用以描述这个节点被影响的难易程度，θv越小，则表示该节点越容易被影响，只有当节点v的所有的邻居节点对v造成的影响大于这个阈值，v才会被激活
- 用bwv表示节点w对于节点v的影响的权重，
，表示节点v的所有处于活跃状态的邻居节点对于节点v的影响力之和
- 在t时刻节点v有一些邻居节点被激活，对v产生影响，当邻居节点对于v的影响力之和大于v激活阈值，则v在t+1时刻转为激活状态，条件：
- 当网络中没有节点能够被激活时，迭代结束
LT模型的激活过程确定， 节点a对节点v的影响在尝试激活失败后被积累，对于其他节点对于v的尝试激活有贡献
参考文档：
http://blog.jobbole.com/23286/
https://wenku.baidu.com/view/b5ae3e50960590c69fc37674.html
https://blog.csdn.net/rubinorth/article/details/52215036
https://blog.csdn.net/u012421852/article/details/80290411
内容总结
以上是互联网集市为您收集整理的PageRank算法与Influence Propagation全部内容，希望文章能够帮你解决PageRank算法与Influence Propagation所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。