使用加權PageRank發現最好的網球運動員

原文鏈接:https://medium.com/neo4j/finding-the-best-tennis-players-of-all-time-using-weighted-pagerank-6950ed5fc98e

最新版本的Neo4j圖形算法庫對PageRank算法增加了權重變量的支持。

我的同事Ryan(https://twitter.com/ryguyrg/)最近發表的一篇論文《誰是有史以來最好的網球運動員？基於職業網球歷史的複雜網絡分析》(https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0017249)，在這篇論文中，他使用了一種PageRank的變種算法，於是我就在想，我也是一名網球愛好者，我是不是也可以基本這種算法去做點什麼呢？

我原計劃要做一些數據的抓取，但是Kevin Lin已經做了一些比較困難的工作，他將到2017年底的所有比賽結果都以csv文件的形式放到了Github《atp-world-tour-tennis-data》(https://github.com/serve-and-volley/atp-world-tour-tennis-data)上.

感謝Kevin的付出。

數據導入

在導入數據之前，我們先創建一些約束，以避免導入一些重複的數據：

CREATE constraint on (p:Player)
ASSERT p.id is unique;
CREATE constraint on (m:Match)
ASSERT m.id is unique;

接下來我們將把數據導入到Neo4j中。先把Kevin創建的CSV文件拷貝到Neo4j的import目錄下。

完成之後我們就可以使用Cypher的LOAD CSV命令將數據導入到Neo4j里了。

LOAD CSV FROM "file:///match_scores_1968-1990_UNINDEXED.csv" AS row
MERGE (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 row
MERGE (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 row
MERGE (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]);

這個模型非常簡單，可以運行下面的請求看到可視化的描述：

CALL db.schema()

可以看到：

看起來不錯。在繼續寫之前，我們先寫個簡單查詢來看一下數據情況：

MATCH p=()<-[:LOSER]-()-[r:WINNER]->() 
RETURN p 
LIMIT 25

獲勝最多的選手

現在，我們想看一下獲勝最多選手，這個語句要怎麼寫呢？

MATCH (p:Player)
WITH p, 
 size((p)<-[:WINNER]-()) AS wins, 
 size((p)<-[:LOSER]-()) as defeats
RETURN p.name, wins, defeats, 
 CASE WHEN wins+defeats = 0 THEN 0 
 ELSE (wins * 100.0) / (wins + defeats) END
 AS percentageWins
ORDER BY wins DESC
LIMIT 10

運行上面的語句，將看到下面的輸出：

如果你也是一名網球迷，你可能認識這份名單中的大部分名字。他們中的大部分都被認為是有史以來最優秀的球員，但是僅僅計算贏球的場數好像並不太嚴謹。

此時，似乎我們可以試試更高級的方法---PageRank算法.....

建立一個可信的投影圖

通過一個結點的入口關係來決定這個結點的可信度，這就是PageRank算法的工作原理。例如，在網絡的世界裏，一個網頁通過鏈接到另一個網頁，而給他帶來可信度。這個可信度可以通過這個關係的權重屬性來決定。

在我們的網球世界裏，運動員的可信度則由他們彼此之間比較的勝負數來決定。例如，下面的查詢顯示了費德勒和納達爾相互贏了多少次。

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

運行輸出結果如下：

我們的投影圖應該在費德勒和納達爾之間建立直接關係，用權重表示他們互相之間比賽贏的次數。從費德勒到納達爾的關係上權重是23，表示費德勒贏了納達爾23次。而納達爾到費德勒的有關係上權重就是15.

我們寫下面的查詢語句將投影出這個圖:

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 weight
LIMIT 10

這個查詢的輸出結果如下所示：

接下來我們要做的是刪除WHERE條件，使這個查詢可以在全圖中進行。

使用加權PageRank來發現最好的網球運動員

現在我們通過PageRank算法的weightProperty參數來調用加權PageRank算法。默認情況下，PageRank算法是非加權模式。

下面的語句即是在全圖上運行加權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, score
RETURN algo.getNodeById(nodeId).name AS player, score
ORDER BY score DESC
LIMIT 10

其運行結果如下：

我們看到，我們排名的頭部與Filippo Radicchi論文的排名是不一樣的，主要區別是費德勒，納達爾和德約科維奇進入了前五。這是因為Radicchi的分析僅到2010年，而這三名球員在此後的8年時間裏一直非常優秀，所以，這也就是我們排名不太一樣的原因。

我們可以模板僅包括2010年之前的比賽，則如下查詢語句:

CALL algo.pageRank.stream(
 "MATCH (p:Player) RETURN id(p) AS id",
 "MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2) 
 WHERE match.year <= $year
 RETURN id(p2) AS source, id(p1) AS target, count(*) as weight
 ",
 {graph:"cypher", weightProperty: "weight", params: {year: 2010}})
YIELD nodeId, score
RETURN algo.getNodeById(nodeId).name AS player, score
ORDER BY score DESC
LIMIT 10

運行效果如下：

注意，在這個查詢中，我們將年份值通過params鍵作為參數傳遞到Cypher投影查詢中。

我們排行榜的前兩名現在與Radicche的一樣了，但是費德勒目前在第三位並不是Radicche的榜單中是第七位，同時納達爾和德約科維奇在我們榜單中已經排到前十之外了。

我們還可能查詢某一個比賽的PageRank排名，下面的查詢是2017年的PageRank排名

CALL algo.pageRank.stream(
 "MATCH (p:Player) RETURN id(p) AS id",
 "MATCH (p1)<-[:WINNER]-(match)-[:LOSER]->(p2)
 WHERE match.year = $year 
 RETURN id(p2) AS source, id(p1) AS target, count(*) as weight
 ",
 {graph:"cypher", weightProperty: "weight", params: {year: 2017}})
YIELD nodeId, score
RETURN algo.getNodeById(nodeId).name AS player, score
ORDER BY score DESC
LIMIT 10

運行效果如下：

下圖是2017年ATP世界巡迴賽的年終排名

這個排名與我們的排名完全不同！這是什麼原因呢？這是因為官方排名為每場比賽都給予了不同的權重，而我們的PageRank排名在每場比賽上給予的是相同權重。

好，關於使用加權PageRank找史上最優化網球選手的問題就介紹到這，我期待着看到更多人使用加權PageRank去解決其他問題。如是你也用了，請告訴我[email protected]

Enjoy!

譯者言：作者僅從應用角度介紹了如果實現這個事，完成沒有介紹algo.pageRank.stream這個方法各個參數的功能，以後有空找到相關文章再給大家介紹。