原文鏈接:https://medium.com/neo4j/finding-the-best-tennis-players-of-all-time-using-weighted-pagerank-6950ed5fc98e
最新版本的Neo4j圖形算法庫(kù)對(duì)PageRank算法增加了權(quán)重變量的支持。
我的同事Ryan(https://twitter.com/ryguyrg/)最近發(fā)表的一篇論文《誰(shuí)是有史以來(lái)最好的網(wǎng)球運(yùn)動(dòng)員芒炼？基于職業(yè)網(wǎng)球歷史的復(fù)雜網(wǎng)絡(luò)分析》(https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0017249)瘫怜，在這篇論文中，他使用了一種PageRank的變種算法本刽，于是我就在想鲸湃，我也是一名網(wǎng)球愛(ài)好者，我是不是也可以基本這種算法去做點(diǎn)什么呢子寓？
我原計(jì)劃要做一些數(shù)據(jù)的抓取暗挑，但是Kevin Lin已經(jīng)做了一些比較困難的工作，他將到2017年底的所有比賽結(jié)果都以csv文件的形式放到了Github《atp-world-tour-tennis-data》(https://github.com/serve-and-volley/atp-world-tour-tennis-data)上.
感謝Kevin的付出斜友。
數(shù)據(jù)導(dǎo)入
在導(dǎo)入數(shù)據(jù)之前炸裆，我們先創(chuàng)建一些約束，以避免導(dǎo)入一些重復(fù)的數(shù)據(jù)：
CREATE constraint on (p:Player)ASSERT p.id is unique;CREATE constraint on (m:Match)ASSERT m.id is unique;
接下來(lái)我們將把數(shù)據(jù)導(dǎo)入到Neo4j中鲜屏。先把Kevin創(chuàng)建的CSV文件拷貝到Neo4j的import目錄下烹看。
完成之后我們就可以使用Cypher的LOAD CSV命令將數(shù)據(jù)導(dǎo)入到Neo4j里了国拇。
LOAD CSV FROM "file:///match_scores_1968-1990_UNINDEXED.csv" AS rowMERGE (winner:Player {id: row[8]})ON CREATE SET winner.name = row[7]MERGE (loser:Player {id: row[11]})ON CREATE SET loser.name = row[10]MERGE (m:Match {id: row[22]})SET m.score = row[15], m.year = toInteger(split(row[0], "-")[0])MERGE (m)-[w:WINNER]->(winner) SET w.seed = toInteger(row[13])MERGE (m)-[l:LOSER]->(loser) SET l.seed = toInteger(row[14]);LOAD CSV FROM "file:///match_scores_1991-2016_UNINDEXED.csv" AS rowMERGE (winner:Player {id: row[8]})ON CREATE SET winner.name = row[7]MERGE (loser:Player {id: row[11]})ON CREATE SET loser.name = row[10]MERGE (m:Match {id: row[22]})SET m.score = row[15], m.year = toInteger(split(row[0], "-")[0])MERGE (m)-[w:WINNER]->(winner) SET w.seed = toInteger(row[13])MERGE (m)-[l:LOSER]->(loser) SET l.seed = toInteger(row[14]);LOAD CSV FROM "file:///match_scores_2017_UNINDEXED.csv" AS rowMERGE (winner:Player {id: row[8]})ON CREATE SET winner.name = row[7]MERGE (loser:Player {id: row[11]})ON CREATE SET loser.name = row[10]MERGE (m:Match {id: row[22]})SET m.score = row[15], m.year = toInteger(split(row[0], "-")[0])MERGE (m)-[w:WINNER]->(winner) SET w.seed = toInteger(row[13])MERGE (m)-[l:LOSER]->(loser) SET l.seed = toInteger(row[14]);
這個(gè)模型非常簡(jiǎn)單，可以運(yùn)行下面的請(qǐng)求看到可視化的描述：
CALL?db.schema()可以看到：
看起來(lái)不錯(cuò)惯殊。在繼續(xù)寫(xiě)之前酱吝，我們先寫(xiě)個(gè)簡(jiǎn)單查詢(xún)來(lái)看一下數(shù)據(jù)情況：
MATCH p=()<-[:LOSER]-()-[r:WINNER]->()RETURN pLIMIT 25
獲勝最多的選手
現(xiàn)在，我們想看一下獲勝最多選手土思，這個(gè)語(yǔ)句要怎么寫(xiě)呢务热？
MATCH (p:Player)WITH p,size((p)<-[:WINNER]-()) AS wins,size((p)<-[:LOSER]-()) as defeatsRETURN p.name, wins, defeats,CASE WHEN wins+defeats = 0 THEN 0ELSE (wins * 100.0) / (wins + defeats) ENDAS percentageWinsORDER BY wins DESCLIMIT 10
運(yùn)行上面的語(yǔ)句，將看到下面的輸出：
如果你也是一名網(wǎng)球迷己儒，你可能認(rèn)識(shí)這份名單中的大部分名字崎岂。他們中的大部分都被認(rèn)為是有史以來(lái)最優(yōu)秀的球員，但是僅僅計(jì)算贏球的場(chǎng)數(shù)好像并不太嚴(yán)謹(jǐn)闪湾。
此時(shí)该镣，似乎我們可以試試更高級(jí)的方法---PageRank算法.....
建立一個(gè)可信的投影圖
通過(guò)一個(gè)結(jié)點(diǎn)的入口關(guān)系來(lái)決定這個(gè)結(jié)點(diǎn)的可信度，這就是PageRank算法的工作原理响谓。例如损合，在網(wǎng)絡(luò)的世界里，一個(gè)網(wǎng)頁(yè)通過(guò)鏈接到另一個(gè)網(wǎng)頁(yè)娘纷，而給他帶來(lái)可信度嫁审。這個(gè)可信度可以通過(guò)這個(gè)關(guān)系的權(quán)重屬性來(lái)決定。
在我們的網(wǎng)球世界里赖晶，運(yùn)動(dòng)員的可信度則由他們彼此之間比較的勝負(fù)數(shù)來(lái)決定律适。例如，下面的查詢(xún)顯示了費(fèi)德勒和納達(dá)爾相互贏了多少次遏插。
MATCH (p1:Player {name: "Roger Federer"}),(p2:Player {name: "Rafael Nadal"})RETURN p1.name, p2.name,size((p1)<-[:WINNER]-()-[:LOSER]->(p2)) AS p1Wins,size((p1)<-[:LOSER]-()-[:WINNER]->(p2)) AS p2Wins
運(yùn)行輸出結(jié)果如下：
我們的投影圖應(yīng)該在費(fèi)德勒和納達(dá)爾之間建立直接關(guān)系捂贿，用權(quán)重表示他們互相之間比賽贏的次數(shù)。從費(fèi)德勒到納達(dá)爾的關(guān)系上權(quán)重是23胳嘲，表示費(fèi)德勒贏了納達(dá)爾23次厂僧。而納達(dá)爾到費(fèi)德勒的有關(guān)系上權(quán)重就是15.
我們寫(xiě)下面的查詢(xún)語(yǔ)句將投影出這個(gè)圖:
MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2)WHERE p1.name IN ["Roger Federer", "Rafael Nadal"]AND p2.name IN ["Roger Federer", "Rafael Nadal"]RETURN p2.name AS source, p1.name AS target, count(*) as weightLIMIT 10
這個(gè)查詢(xún)的輸出結(jié)果如下所示：
接下來(lái)我們要做的是刪除WHERE條件，使這個(gè)查詢(xún)可以在全圖中進(jìn)行了牛。
使用加權(quán)PageRank來(lái)發(fā)現(xiàn)最好的網(wǎng)球運(yùn)動(dòng)員
現(xiàn)在我們通過(guò)PageRank算法的weightProperty參數(shù)來(lái)調(diào)用加權(quán)PageRank算法颜屠。默認(rèn)情況下，PageRank算法是非加權(quán)模式鹰祸。
下面的語(yǔ)句即是在全圖上運(yùn)行加權(quán)PageRank算法：
CALL algo.pageRank.stream("MATCH (p:Player) RETURN id(p) AS id","MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2)RETURN id(p2) AS source, id(p1) AS target, count(*) as weight",{graph:"cypher", weightProperty: "weight"})YIELD nodeId, scoreRETURN algo.getNodeById(nodeId).name AS player, scoreORDER BY score DESCLIMIT 10
其運(yùn)行結(jié)果如下：
我們看到甫窟，我們排名的頭部與Filippo Radicchi論文的排名是不一樣的，主要區(qū)別是費(fèi)德勒蛙婴，納達(dá)爾和德約科維奇進(jìn)入了前五粗井。這是因?yàn)镽adicchi的分析僅到2010年，而這三名球員在此后的8年時(shí)間里一直非常優(yōu)秀，所以浇衬，這也就是我們排名不太一樣的原因呆瞻。
我們可以模板僅包括2010年之前的比賽，則如下查詢(xún)語(yǔ)句:
CALL algo.pageRank.stream("MATCH (p:Player) RETURN id(p) AS id","MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2)WHERE match.year <= $yearRETURN id(p2) AS source, id(p1) AS target, count(*) as weight",{graph:"cypher", weightProperty: "weight", params: {year: 2010}})YIELD nodeId, scoreRETURN algo.getNodeById(nodeId).name AS player, scoreORDER BY score DESCLIMIT 10
運(yùn)行效果如下：
注意径玖，在這個(gè)查詢(xún)中，我們將年份值通過(guò)params鍵作為參數(shù)傳遞到Cypher投影查詢(xún)中颤介。
我們排行榜的前兩名現(xiàn)在與Radicche的一樣了梳星，但是費(fèi)德勒目前在第三位并不是Radicche的榜單中是第七位，同時(shí)納達(dá)爾和德約科維奇在我們榜單中已經(jīng)排到前十之外了滚朵。
我們還可能查詢(xún)某一個(gè)比賽的PageRank排名冤灾，下面的查詢(xún)是2017年的PageRank排名
CALL algo.pageRank.stream("MATCH (p:Player) RETURN id(p) AS id","MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2)WHERE match.year = $yearRETURN id(p2) AS source, id(p1) AS target, count(*) as weight",{graph:"cypher", weightProperty: "weight", params: {year: 2017}})YIELD nodeId, scoreRETURN algo.getNodeById(nodeId).name AS player, scoreORDER BY score DESCLIMIT 10
運(yùn)行效果如下：
下圖是2017年ATP世界巡回賽的年終排名
這個(gè)排名與我們的排名完全不同！這是什么原因呢辕近？這是因?yàn)楣俜脚琶麨槊繄?chǎng)比賽都給予了不同的權(quán)重韵吨，而我們的PageRank排名在每場(chǎng)比賽上給予的是相同權(quán)重。
好移宅，關(guān)于使用加權(quán)PageRank找史上最優(yōu)化網(wǎng)球選手的問(wèn)題就介紹到這归粉，我期待著看到更多人使用加權(quán)PageRank去解決其他問(wèn)題。如是你也用了漏峰，請(qǐng)告訴我devrel@neo4j.com
Enjoy!
譯者言：作者僅從應(yīng)用角度介紹了如果實(shí)現(xiàn)這個(gè)事糠悼，完成沒(méi)有介紹algo.pageRank.stream這個(gè)方法各個(gè)參數(shù)的功能，以后有空找到相關(guān)文章再給大家介紹浅乔。
