在微博中應用PageRank算法
這個想法很早就有了，因為我是做搜索引擎背景的，能夠深刻的理解PageRank算法在搜索引擎中的重要性，絕對的核心技術之一。不過，這篇博客，并不打算介紹PageRank算法的原理，而是，讓我們來看看，這個重要的算法，在新浪微博中的應用。
網頁與網頁之間，通過鏈接關系傳遞著重要性。在微博中呢？這個也是成立的。不過在微博中，情況要更復雜一些。所以，我在微博中指出，我并不贊同計算全量的PageRank（即所有人都參與計算）。原因有以下幾點：
- 人的主題屬性和網頁不同。網頁往往只有一個主題，而人的主題屬性比較多，我們可以將主題屬性理解為人的興趣，一般而言，人的興趣，會不止一個。
- 人的興趣會隨著時間不斷變化，而大部分的網頁，誕生之后，主題基本不會發(fā)生變化（但是網頁的PageRank也是要定期重算的，這個主要是因為鏈接關系發(fā)生了變化等等）。
- 除了因為興趣的關注，新浪微博中，還存在好友關系——真實的好友關系。
針對第一點，人的興趣的多樣性，這個是非常明顯的，從每個用戶的標簽、微博內容就可以很直接的看出來。那么，我們要怎么做呢？我的觀點是，針對特定領域內的微博用戶，計算PageRank。這樣可以得到在這個領域內的人的影響力的排名。這個是很有用的，草根們可以用來找專家，獵頭們可以用來找候選人，水平如何，非常直觀的顯示出來。要理解，我上面說的話，我來舉個例子。從標簽開始，微博的用戶為什么打標簽呢（twitter是沒有標簽的，這個是新浪微博數據中的寶藏，盡管說，十個人里，只有一個人有標簽，但是這批數據也是非常寶貴的）。我想大概兩個原因：
- 自己的興趣：電影、音樂、考古等等
- 自己的專長：java、數據挖掘、機器學習、自然語言理解等等
標簽都是用戶自己定義的，有的時候不會十分的準確，這個時候需要一些手段來衡量準確的程度：PageRank就是一個很好的手段。比如，我給自己打一個“考古”的標簽，作為我的興趣，通常來說我會關注一些考古資訊類的微博、或者一些考古權威人士。如果，沒有這些關注，這個興趣就值得懷疑了。再比如，我自己打了“復雜網絡”的標簽，但是我的粉絲中，沒有人對這個感興趣，那么我還能成為這個領域中的專家么？專家是需要大家認可的。所以，主要是從這個角度講，全量的PageRank需求并不那么強烈。
針對第二點，我們要充分的理解社交網絡是變化的，是不斷演變的。很多人都在研究這個演變的規(guī)律、過程。我現在興趣，還沒在這里。但是這個“變化”對我們計算rank有多大的影響呢？其實一個網絡的演變，是分階段。有巨變，有緩慢的變化。巨變的時候，網絡結構變化比較多，然而其他的時候，網絡的結構都相對穩(wěn)定。比如，目前的新浪微博，每天還有用戶在注冊，可能用不了多久就宣告突破5億注冊用戶。但是，在某些領域，網絡的結構已經相對比較穩(wěn)固了，該來的人，差不多都來了。不該來的，他以后來的可能性也不大。所以，這時，計算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的結果是什么：
這只是部分數據，我還做了一些精簡。也能夠看出點效果。比如，我們可以理解為粉絲的質量排名。但如果是某個領域，比如“機器學習”，那我們就可以理解這個領域有哪些專家，并且誰更牛一些。這個更加有用一些。
【注】graphchi目前支持node id到2^31，再大就無法計算。所以我們計算的時候，先要做好準備。
原文鏈接：http://www.cnblogs.com/sing1ee/archive/2012/12/13/2811581.html
