Massive-Data-Process-Lab2-PageRank-on-the-Wikipedia-Corpus

实验目标

实现PageRank,将Wikipedia转换为链接图,然后对其进行PageRank,运行多次直到结果收敛,返回所有文章的PageRank值

语料库

  • Wikipedia提供的包含Wikipedia站点所有文章的xml文件,其中包括重定向以及消歧义页面
  • Links to other wikipedia articles are of the form “[[Name of other article]]”.

实验步骤

  1. graphBuiler: 构建链接关系图
  2. pageRankItr: 迭代计算页面的rank
  3. pageRankViewer: 将结果文件转换为text format, 并且按照page rank score排序

扩展

  • 在实验中我们使用了TextInputFormat clas, 考虑是否有其他方式处理xml文档
  • Implement variably weighted links. Explain your heuristic and convince us that its working.
  • Run PageRank over the Nutch crawl or your InvertedIndexer over Wikipedia and then combine both
    data sets into a rudimentary search engine.

实现

链接关系图的构建

首先构建链接关系图,切割后的数据一行为一个Page。因此直接采用TextInputFormat即可。

map阶段

一次读入一行数据,使用正则表达式从中解析出title以及outlink, 输出(title, outlink)

1
2
private static final Pattern LINKPATTERN = Pattern.compile("\\[\\[(.+?)\\]\\]");
private static final Pattern TITLEPATTERN = Pattern.compile("<title>(.+)</title>");

为了后续处理方便,在连接图的构建过程中将空格,标点等字符转换为了'_', outlink的格式多样,"[[outlink|others]]",这类型的外链只保留’|’前的内容

reduce阶段

同一个title链出的页面聚合在一起,outlink拼接即可,同时为了方便后续PageRank计算,输出时同时把PageRank初始值(1.0)输出,输出(title, "1.0\t" + outlink list);

最终得到的链接关系图约5.2G

PageRank计算

Map阶段:

一行一行读入,输入格式为(page, (cur_rank, url_list)

  • url_list中的每一个link, 输出中间结果(link, cur_rank/url_list.length)
  • 输出(page, "!")标记当前页面是Wikipedia页面,供reduce阶段使用
  • 输出原始链接关系,供reduce阶段使用(page, (cur_rank, url_list)

Reduce阶段:

输入为(page, (cur_rank, url_list), (page, val), (page, "!")等多类型数据,其中val是指向该page的页面分给该页面的rank值,(page, “!”)标记了该页面存在于链接关系图中,记录rank时需要记录,否则不记录该页面的rank,这样使得最终的rank列表页面数与连接图页面数一致

  • 将所有val相机,阻尼系数d = 0.85, 迭代计算PageRank值$$PR(u) = (1-d) + d*\sum_{v \in B(u)}PR(v)$$其中$PR(u)$表示页面u的PageRank值,v指向页面u, $B(u)$是连接到页面u的所有页面集合。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    for (Text value: values) {
    String str = value.toString();
    // LOG.warn(key + " " + str + " " + pagerank);
    if(str.equals("!")) {
    exist = true;
    continue;
    }
    String []k_v = str.split("\t");
    if(k_v.length > 1) {
    out_link = k_v[1];
    }
    else {
    pagerank += Double.parseDouble(k_v[0]);
    }
    }
    // 页面不存在则丢弃
    if(!exist) return;

    pagerank = pagerank * d + (1 - d);
  • 输出迭代结果(page, (new_rank, url_list))

  • 一共迭代10轮

RankSort排序

将结果安装PageRank值排序,map阶段输入(page, (rank, url_list)), 输出格式为(rank, page)

即以rank值作为key, 利用MapReduce的shuffle阶段完成排序操作,默认排序是顺序排序,因此需要自定义排序规则实现倒序排序

1
2
3
4
5
6
7
8
9
10
11
 public static class FloatWritableComparator extends FloatWritable.Comparator {
@Override
public int compare(WritableComparable a, WritableComparable b) {
return -super.compare(a, b);
}

@Override
public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
return -super.compare(b1, s1, l1, b2, s2, l2);
}
}

扩展

Xml文档的处理

法1:XMLInputFormat

以XMLInputFormat形式读入输入文件,其方法是继承自TextInputFormat,然后处理好迭代多行的文本内容逻辑,以tag切分数据片,每切分一个完整的tag内容写入到Buffer中

法2:将XML文件转为SequenceFile

SequenceFile是Hadoop API 提供的一种二进制文件,它将数据以<key,value>的形式序列化到文件中。这种二进制文件内部使用Hadoop 的标准的Writable 接口实现序列化和反序列化。

因此需要实现对xml文件的tag解析以及存储,最终将xml文件转换为SequenceFile

加权PageRank

算法描述

在某一主题范围内,如果有许多网页链向某一网页或者有很多高影响的网页指向该页面,则该页面比较重要,在本加权PageRank算法中,页面的重要度取决于指向该页面的连接数以及该页面链出的页面数,即出入度影响页面的权重。其计算公式如下:
$$ PR(u)=(1-d)+d\sum_{v \in B(u)}PR(v)W_{(v,u)}^{in}W_{(v,u)}^{out} $$
其中,$W(v,u)^{out}$是指链接(v,u)的出链权重, $W(v,u)^{in}$是指链接(v,u)的入链权重,其计算公式如下:
$$W_{(v,u)}^{in}=\frac{I_u}{\sum_{p \in R(v)}I_p}$$
$$W_{(v,u)}^{out}=\frac{O_u}{\sum_{p \in R(v)}O_p}$$

$I_u,I_p$分别是网页u,网页p的入链数,$O_u,O_p$分别是网页u,网页p的出链数。

实现

采用出入度加权算法之后,计算PageRank时需要将页面的出入度考虑在内,因此在构建连接关系图之后,计算PageRank之前,需要先统计每个页面的出入度。

这里分两步完成

  • 链接关系倒排:

    • MAP阶段:输入(url, url_list), 输出(url, "!\t" + url_list.length),即输出其出度,否则对u in url_list, 输出(u, url), 即输出倒排链接关系对

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      // 没有出度
      if(k_v.length < 3 || k_v[2].length() == 0) {
      // LOG.warn("map1 " + page + " !\t0");
      context.write(new Text(page), new Text("!\t0"));
      return;
      }

      String out_link = k_v[2];
      out_link = out_link.replaceAll("@", "_");
      String []all_out_link = out_link.split(",");

      int out_degree = all_out_link.length;

      for (String link: all_out_link) {
      context.write(new Text(link), new Text(page));
      }

      context.write(new Text(page), new Text("!\t" + out_degree));
    • Reduce阶段:统计页面的出入度,(page, "!\t" + num)格式的得出page的outdegree, 对(page, parentPage)得出其链接关系,据此统计其入度即可,最后输出(outlink, (indegree, outdegree, parentPage))或者(parentPage, (indegree, outdegree, "!", num))

  • 统计出入度,还原链接关系图:

    • Map阶段: 输入格式为前一步的reduce输出,根据读入的数据,输出(parent, ("!", indegree@outdegree))或者(parent, outlink@indegree@outdegree)
    • Reduce阶段:将同key下的链接串起来输出,还原链接关系即可
  • PageRank计算: 考虑出入度之后,PageRank计算也需要更新,在PageRank的map阶段,输入(URL, (rank, url_list)), 对 u in url_list, 输出(u, rank/url_list.length * indegree(u)/sum(degree) * outdegree(u)/sum(degree))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for(int i = 0; i < all_out_link.length; ++i) {
    String []link_arr = all_out_link[i].split("@");
    sum_indegree += Integer.parseInt(link_arr[1]);
    sum_outdegree += Integer.parseInt(link_arr[2]);
    in_degree[i] = Integer.parseInt(link_arr[1]);
    out_degree[i] = Integer.parseInt(link_arr[2]);

    }

    for(int i = 0; i < all_out_link.length; ++i) {
    Double my_rank = avg_rank * ((double)in_degree[i]/sum_indegree) *((double)out_degree[i]/sum_outdegree);
    context.write(new Text(all_out_link[i]), new Text(my_rank.toString()));
    }

计算结果

非加权PageRank结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
9529.62 Wikipedia:Persondata
7545.4595 United_States
5987.736 Category:Living_people
3621.945 Wikipedia:Deletion_review
2773.274 Wikipedia:Templates_for_discussion/Log/2010_September_10
2383.2075 England
2267.7446 United_Kingdom
2217.742 Race_and_ethnicity_in_the_United_States_Census
2140.0762 Canada
2091.2627 Template:Orphaned_non-free_revisions
1902.5581 Germany
1872.2252 India
1855.1145 France
1819.9362 Animal
1607.0189 Help:Reverting
1603.3832 Australia
1553.8312 World_War_II
1449.9705 Japan
1348.8551 Category:Unprintworthy_redirects
1299.4221 London

出入度加权PageRank结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1380.1716   Template:Orphaned_non-free_revisions@30019@7
947.3123 Wikipedia:File_Upload_Wizard@8722@43
733.5275 Wikipedia:Templates_for_discussion/Log/2010_September_10@41951@163
536.2137 United_States@573674@1360
415.73993 Wikipedia:FurMe@25192@55
412.24493 Protein_Data_Bank@4511@74
340.89578 Help:Reverting@48182@69
322.3545 Wikipedia:Deletion_review@752655@34
280.8142 Wikipedia:High-risk_templates@4194@23
205.92093 Category:Fb_team_templates@584@14
193.67151 England@207733@1647
193.24915 India@132738@1290
188.27377 Category:Radio_station_logos@5344@4
167.8264 Germany@164873@1189
154.31766 Wikipedia:Non-free_content/templates@15982@323
153.8296 Category:Film_poster_images@13650@15
151.34845 France@180649@1849
135.47894 Russia@74494@1848
134.8195 Category:Albums_by_artist@13822@54
134.0424 Wikipedia:Persondata@897003@78

总结

  • 实现的扩展:
    • MapReduce下XML输入文件的处理
    • 基于出入度的加权PageRank算法
  • 学会了MapReduce下PageRank的计算方法,并进一步掌握了加权PageRank算法,对页面的链接关系、主题相关度等对页面价值评价影响有了更深入的认识
  • 未加权的PageRank值前10中有不少是语言名,这是因为这些页面的入度非常高(几乎每个Wikipedia页面都有语言选择的超链接),而考虑出入度加权之后,前10中非语言类页面则更多了,可以直观感受到出入度加权之后的PageRank值更加合理

参考资料

打赏