在微博中应用PageRank算法
这个想法很早就有了，因为我是做搜索引擎背景的，能够深刻的理解PageRank算法在搜索引擎中的重要性，绝对的核心技术之一。不过，这篇博客，并不打算介绍PageRank算法的原理，而是，让我们来看看，这个重要的算法，在新浪微博中的应用。
网页与网页之间，通过链接关系传递着重要性。在微博中呢？这个也是成立的。不过在微博中，情况要更复杂一些。所以，我在微博中指出，我并不赞同计算全量的PageRank（即所有人都参与计算）。原因有以下几点：
- 人的主题属性和网页不同。网页往往只有一个主题，而人的主题属性比较多，我们可以将主题属性理解为人的兴趣，一般而言，人的兴趣，会不止一个。
- 人的兴趣会随着时间不断变化，而大部分的网页，诞生之后，主题基本不会发生变化（但是网页的PageRank也是要定期重算的，这个主要是因为链接关系发生了变化等等）。
- 除了因为兴趣的关注，新浪微博中，还存在好友关系——真实的好友关系。
针对第一点，人的兴趣的多样性，这个是非常明显的，从每个用户的标签、微博内容就可以很直接的看出来。那么，我们要怎么做呢？我的观点是，针对特定领域内的微博用户，计算PageRank。这样可以得到在这个领域内的人的影响力的排名。这个是很有用的，草根们可以用来找专家，猎头们可以用来找候选人，水平如何，非常直观的显示出来。要理解，我上面说的话，我来举个例子。从标签开始，微博的用户为什么打标签呢（twitter是没有标签的，这个是新浪微博数据中的宝藏，尽管说，十个人里，只有一个人有标签，但是这批数据也是非常宝贵的）。我想大概两个原因：
- 自己的兴趣：电影、音乐、考古等等
- 自己的专长：java、数据挖掘、机器学习、自然语言理解等等
标签都是用户自己定义的，有的时候不会十分的准确，这个时候需要一些手段来衡量准确的程度：PageRank就是一个很好的手段。比如，我给自己打一个“考古”的标签，作为我的兴趣，通常来说我会关注一些考古资讯类的微博、或者一些考古权威人士。如果，没有这些关注，这个兴趣就值得怀疑了。再比如，我自己打了“复杂网络”的标签，但是我的粉丝中，没有人对这个感兴趣，那么我还能成为这个领域中的专家么？专家是需要大家认可的。所以，主要是从这个角度讲，全量的PageRank需求并不那么强烈。
针对第二点，我们要充分的理解社交网络是变化的，是不断演变的。很多人都在研究这个演变的规律、过程。我现在兴趣，还没在这里。但是这个“变化”对我们计算rank有多大的影响呢？其实一个网络的演变，是分阶段。有巨变，有缓慢的变化。巨变的时候，网络结构变化比较多，然而其他的时候，网络的结构都相对稳定。比如，目前的新浪微博，每天还有用户在注册，可能用不了多久就宣告突破5亿注册用户。但是，在某些领域，网络的结构已经相对比较稳固了，该来的人，差不多都来了。不该来的，他以后来的可能性也不大。所以，这时，计算PageRank，得到的排序结果，还是能够应用一段时间的。不过，这个我建议，还是要定期重新计算一下，而且要比网页的重新计算更加频繁。
针对第三点，我们考虑的主要就是社交圈子的挖掘了。在这里不多说。
说了很多，绕远了。那用什么来计算呢？高效的计算PageRank有不少方法，有单机的工具包、还有基于MapReduce模型的、基于spark的。我这里向大家介绍一个工具：Graphchi 非常强大，号称比spark还要猛，hadoop类似的，就直接pass。
上面唠叨了很多在微博中应用PageRank的道理。下面我使用graphchi计算一下3000w人的PageRank，一个近乎全量的PageRank。
简单介绍一下grapchi的使用：
- 下载graphchi：wget http://graphchi.googlecode.com/files/graphchi_src_v0.1.7b.tar.gz
- tar zxvf graphchi_src_v0.1.7b.tar.gz
- cd graphchi_v0.1.7b
- make example_apps/pagerank
- bin/example_apps/pagerank file your_graph_file <num_of_iterations>
上面的your_graph_file可是两种格式：
- EdgeListFormat：src dist1 value1
- AdjacencyListFormat：src 4 dist1 dist2 dist3 dist4
一些有用的参数，命令如下：
bin/myapps/myprogram file GRAPH-FILE config1 configvalue1 config2 configvalue2
后面的配置项很方便，可以不用在运行时设置filetype等，常用的有：
- file 后面是图数据文件
- filetype 后面是图存储类型 edgelist或者adjacencylist
- execthreads 计算的线程数
- membudget_mb 加载图数据可使用的内存大小
示例如下：
bin/example_apps/pagerank file ../pg/part1_sort.txt 3 filetype edgelist execthreads 8 membudget_mb 4096
准备好数据和工具，开始run————让我们看看，这随机采样的3000w人中，PageRank的结果是什么：
这只是部分数据，我还做了一些精简。也能够看出点效果。比如，我们可以理解为粉丝的质量排名。但如果是某个领域，比如“机器学习”，那我们就可以理解这个领域有哪些专家，并且谁更牛一些。这个更加有用一些。