這個(gè)想法很早就有了，因?yàn)槲沂亲鏊阉饕姹尘暗?，能夠深刻的理解PageRank算法在搜索引擎中的重要性，絕對(duì)的核心技術(shù)之一。不過(guò)，這篇博客，并不打算介紹PageRank算法的原理，而是，讓我們來(lái)看看，這個(gè)重要的算法，在新浪微博中的應(yīng)用。

網(wǎng)頁(yè)與網(wǎng)頁(yè)之間，通過(guò)鏈接關(guān)系傳遞著重要性。在微博中呢？這個(gè)也是成立的。不過(guò)在微博中，情況要更復(fù)雜一些。所以，我在微博中指出，我并不贊同計(jì)算全量的PageRank（即所有人都參與計(jì)算）。原因有以下幾點(diǎn)：

1. 人的主題屬性和網(wǎng)頁(yè)不同。網(wǎng)頁(yè)往往只有一個(gè)主題，而人的主題屬性比較多，我們可以將主題屬性理解為人的興趣，一般而言，人的興趣，會(huì)不止一個(gè)。
2. 人的興趣會(huì)隨著時(shí)間不斷變化，而大部分的網(wǎng)頁(yè)，誕生之后，主題基本不會(huì)發(fā)生變化（但是網(wǎng)頁(yè)的PageRank也是要定期重算的，這個(gè)主要是因?yàn)殒溄雨P(guān)系發(fā)生了變化等等）。
3. 除了因?yàn)榕d趣的關(guān)注，新浪微博中，還存在好友關(guān)系——真實(shí)的好友關(guān)系。

針對(duì)第一點(diǎn)，人的興趣的多樣性，這個(gè)是非常明顯的，從每個(gè)用戶的標(biāo)簽、微博內(nèi)容就可以很直接的看出來(lái)。那么，我們要怎么做呢？我的觀點(diǎn)是，針對(duì)特定領(lǐng)域內(nèi)的微博用戶，計(jì)算PageRank。這樣可以得到在這個(gè)領(lǐng)域內(nèi)的人的影響力的排名。這個(gè)是很有用的，草根們可以用來(lái)找專家，獵頭們可以用來(lái)找候選人，水平如何，非常直觀的顯示出來(lái)。要理解，我上面說(shuō)的話，我來(lái)舉個(gè)例子。從標(biāo)簽開(kāi)始，微博的用戶為什么打標(biāo)簽?zāi)兀╰witter是沒(méi)有標(biāo)簽的，這個(gè)是新浪微博數(shù)據(jù)中的寶藏，盡管說(shuō)，十個(gè)人里，只有一個(gè)人有標(biāo)簽，但是這批數(shù)據(jù)也是非常寶貴的）。我想大概兩個(gè)原因：

1. 自己的興趣：電影、音樂(lè)、考古等等
2. 自己的專長(zhǎng)：java、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、自然語(yǔ)言理解等等

標(biāo)簽都是用戶自己定義的，有的時(shí)候不會(huì)十分的準(zhǔn)確，這個(gè)時(shí)候需要一些手段來(lái)衡量準(zhǔn)確的程度：PageRank就是一個(gè)很好的手段。比如，我給自己打一個(gè)“考古”的標(biāo)簽，作為我的興趣，通常來(lái)說(shuō)我會(huì)關(guān)注一些考古資訊類的微博、或者一些考古權(quán)威人士。如果，沒(méi)有這些關(guān)注，這個(gè)興趣就值得懷疑了。再比如，我自己打了“復(fù)雜網(wǎng)絡(luò)”的標(biāo)簽，但是我的粉絲中，沒(méi)有人對(duì)這個(gè)感興趣，那么我還能成為這個(gè)領(lǐng)域中的專家么？專家是需要大家認(rèn)可的。所以，主要是從這個(gè)角度講，全量的PageRank需求并不那么強(qiáng)烈。

針對(duì)第二點(diǎn)，我們要充分的理解社交網(wǎng)絡(luò)是變化的，是不斷演變的。很多人都在研究這個(gè)演變的規(guī)律、過(guò)程。我現(xiàn)在興趣，還沒(méi)在這里。但是這個(gè)“變化”對(duì)我們計(jì)算rank有多大的影響呢？其實(shí)一個(gè)網(wǎng)絡(luò)的演變，是分階段。有巨變，有緩慢的變化。巨變的時(shí)候，網(wǎng)絡(luò)結(jié)構(gòu)變化比較多，然而其他的時(shí)候，網(wǎng)絡(luò)的結(jié)構(gòu)都相對(duì)穩(wěn)定。比如，目前的新浪微博，每天還有用戶在注冊(cè)，可能用不了多久就宣告突破5億注冊(cè)用戶。但是，在某些領(lǐng)域，網(wǎng)絡(luò)的結(jié)構(gòu)已經(jīng)相對(duì)比較穩(wěn)固了，該來(lái)的人，差不多都來(lái)了。不該來(lái)的，他以后來(lái)的可能性也不大。所以，這時(shí)，計(jì)算PageRank，得到的排序結(jié)果，還是能夠應(yīng)用一段時(shí)間的。不過(guò)，這個(gè)我建議，還是要定期重新計(jì)算一下，而且要比網(wǎng)頁(yè)的重新計(jì)算更加頻繁。

針對(duì)第三點(diǎn)，我們考慮的主要就是社交圈子的挖掘了。在這里不多說(shuō)。

說(shuō)了很多，繞遠(yuǎn)了。那用什么來(lái)計(jì)算呢？高效的計(jì)算PageRank有不少方法，有單機(jī)的工具包、還有基于MapReduce模型的、基于spark的。我這里向大家介紹一個(gè)工具：Graphchi 非常強(qiáng)大，號(hào)稱比spark還要猛，hadoop類似的，就直接pass。

上面嘮叨了很多在微博中應(yīng)用PageRank的道理。下面我使用graphchi計(jì)算一下3000w人的PageRank，一個(gè)近乎全量的PageRank。

簡(jiǎn)單介紹一下grapchi的使用：

1. 下載graphchi：wget http://graphchi.googlecode.com/files/graphchi_src_v0.1.7b.tar.gz
2. tar zxvf graphchi_src_v0.1.7b.tar.gz
3. cd graphchi_v0.1.7b
4. make example_apps/pagerank
5. bin/example_apps/pagerank file your_graph_file <num_of_iterations>

上面的your_graph_file可是兩種格式：

1. EdgeListFormat：src dist1 value1
2. AdjacencyListFormat：src 4 dist1 dist2 dist3 dist4

一些有用的參數(shù)，命令如下：

bin/myapps/myprogram file GRAPH-FILE  config1 configvalue1 config2 configvalue2 

后面的配置項(xiàng)很方便，可以不用在運(yùn)行時(shí)設(shè)置filetype等，常用的有：

1. file 后面是圖數(shù)據(jù)文件
2. filetype 后面是圖存儲(chǔ)類型 edgelist或者adjacencylist
3. execthreads 計(jì)算的線程數(shù)
4. membudget_mb 加載圖數(shù)據(jù)可使用的內(nèi)存大小

示例如下：

bin/example_apps/pagerank file ../pg/part1_sort.txt 3 filetype edgelist execthreads 8 membudget_mb 4096 

準(zhǔn)備好數(shù)據(jù)和工具，開(kāi)始run————讓我們看看，這隨機(jī)采樣的3000w人中，PageRank的結(jié)果是什么：

這只是部分?jǐn)?shù)據(jù)，我還做了一些精簡(jiǎn)。也能夠看出點(diǎn)效果。比如，我們可以理解為粉絲的質(zhì)量排名。但如果是某個(gè)領(lǐng)域，比如“機(jī)器學(xué)習(xí)”，那我們就可以理解這個(gè)領(lǐng)域有哪些專家，并且誰(shuí)更牛一些。這個(gè)更加有用一些。

【注】graphchi目前支持node id到2^31，再大就無(wú)法計(jì)算。所以我們計(jì)算的時(shí)候，先要做好準(zhǔn)備。

原文鏈接：http://www.cnblogs.com/sing1ee/archive/2012/12/13/2811581.html