在之前的前幾篇文章中，我們分別介紹了圖遍歷算法，單源最短路算法。這篇文章里將介紹一下佩奇排名（PageRank）算法。
PageRank，網(wǎng)頁排名，又稱為網(wǎng)頁級(jí)別，Google左側(cè)排名，是一種由網(wǎng)頁之間相互的超鏈接計(jì)算的技術(shù)，作為網(wǎng)頁排名的要素之一。Google用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性，在搜索引擎優(yōu)化操作中是經(jīng)常被用來評(píng)估網(wǎng)頁優(yōu)化的成效因素之一。
我們?cè)谏詈蜕a(chǎn)活動(dòng)中，會(huì)經(jīng)常遇到網(wǎng)絡(luò)中節(jié)點(diǎn)排序的任務(wù)。在互聯(lián)網(wǎng)中會(huì)有以億為單位的網(wǎng)頁，那么哪些頁面對(duì)用戶感興趣，怎么投放廣告？論文在引用和被引用的過程中實(shí)現(xiàn)了知識(shí)傳遞，哪些論文在發(fā)展中起著關(guān)鍵性的作用？
我們可以用圖來表示。圖1是有向圖，包含了4個(gè)節(jié)點(diǎn)和4條邊。邊的起點(diǎn)是一個(gè)網(wǎng)頁，人或者論文，終點(diǎn)指向的是起點(diǎn)所引用的網(wǎng)頁，人或者論文。節(jié)點(diǎn)1引用節(jié)點(diǎn)0，代表前者從后者獲取消息，知識(shí)。引用其他節(jié)點(diǎn)就是獲益；反之，被他人引用就是傳播信息。
問題，哪個(gè)節(jié)點(diǎn)傳播力最強(qiáng)更重要?
PageRank認(rèn)為，節(jié)點(diǎn)1向其他節(jié)點(diǎn)傳遞信息，節(jié)點(diǎn)1接受不能搞傳播從節(jié)點(diǎn)0得到的信息。節(jié)點(diǎn)0的影響力，可以用其相連的節(jié)點(diǎn)1的影響力來衡量。類似于“通過一個(gè)人的朋友來分析這個(gè)人”。
以上就是對(duì)于PageRank算法的介紹，感興趣的朋友可以自己動(dòng)手嘗試，在這里我推薦使用Graphscope這個(gè)平臺(tái)。
graphscope是阿里達(dá)摩院智能計(jì)算實(shí)驗(yàn)室研發(fā)并開源的全球首個(gè)一站式超大規(guī)模分布式圖計(jì)算平臺(tái)，支持多種圖算法，可以方便地進(jìn)行圖分析和圖計(jì)算，并且在性能上也達(dá)到極致。
在圖分析測(cè)試 LDBC GraphAnalytics Benchmark 上，GraphScope 與 PowerGraph 以及其他最新系統(tǒng)比較，幾乎在所有算法和數(shù)據(jù)集的組合中居于領(lǐng)先水平。從下圖中我們可以看到，在執(zhí)行PageRank時(shí)，GraphScope用時(shí)1.61秒，遠(yuǎn)小于PowerGraph的26.9秒。
GraphScope 的白皮書、代碼已經(jīng)在 github.com/alibaba/graphscope 開源，可以直接試用。
聯(lián)系客服
