网页排名图(graph)算法PageRank

  • 关键问题

    • 怎么用MR表示图数据
    • 怎么用MR遍历图

      PageRank算法

  • 设计思想： 被优质网页所链接网页，多半也是优质的。 PR值与链接网页数量与质量方面成正比。

    简化矩阵模型

  • PageRank值计算公式

    • image.png ，Bi为所有链接到网页i的集合，Lj为网页j的对外链接。
    • 理解：对于j网页，将其Rank值均分为Lj份，给它指向的值；该算法是个迭代过程，对于i节点而言，从指向它的节点处获取rank值，又将自己当前的rank值分给它指向的节点，维持动态平衡。

image.png eigenvalue：特征值

  • 达到 R = HR状态，即动态平衡。
  • 存在问题
    • Rank Leak：某网页没有出度的链接产生Rank泄露。(因为总会从该网页消耗一部分Rank值
      • 将无出度节点递归从图中去掉，计算完后再加上
      • 从该节点指回 指向它的边
    • Rank Sink： 某网页没有入度链接。该节点的Rank值会逐步趋向于0，无法排名。

      随机浏览模型

  • 设计思想：对于上网者而言，每一次所打开网页的操作都是随机的，既可能通过当前网页链接跳转，也可能直接输入网页地址进行浏览，考虑用户浏览行为。
  • 图表示：
    • image.png
    • 红色概率(1-p)用户随机跳转，蓝色概率p通过当前网页链接跳转

[设计思想其实很有意思，之前做FGSM算法时，曾了解过DI2-FGSM算法，其所进行的改进为：在样本输入模型之前，以一定概率p对其进行随机resize，padding操作，可以提高白盒攻击成功率]

  • 矩阵表示
    • H’ = dH + (1-d)[1/N] [d为阻尼因子，通常设置为0.85]
    • 同理，要找到一个 R = H’R [R为列向量，代表PageRank值]
  • PageRank公式

image.png
1-d为随机跳转到一个新网页的概率，d为按照超链接浏览概率

MapReduce实现PageRank[课设可用，重点]

迭代终止条件：

  • PR值不改变
  • 排序不改变

  • 迭代固定次数

    Phase1：GraphBuilder

  • 数据集：每行一个网页名，以及其所链接的全部网页名。

  • Target：建立各网页之间的链接关系
  • Map：输出, PR_init为该网页的初始值

  • Reduce: 不需要做任何处理

    Phase2: PageRankIter

  • 迭代计算PR值。该循环写在作业提交外层，即在单机上进行判断

  • Map：产生两种对
    • Rank值分发: for each u in link_list, emit
    • 维护图结构：emit
  • Reduce
    • 为当前URL的出度点
    • 计算之和，并乘上d，加上(1-d)/N，得到new_rank
    • emit (url, (new_rank, url_list))

再把该reduce值重新拿回PageRankiter进行迭代，传url_list的目的是为了符合PageRankiter的输入

  • 伪代码

image.png

Phase3: RankViewer

输出排序结果。排序可通过框架自身的排序处理，重载key的比较函数。