圖算法你好： 以 Neo4j 進行《冰與火之歌：權力遊戲》實作

熟悉 Neo4j 的 Cypher 語法

「工欲善其事，必先利其器」，延續上集 Neo4j 的環境與工具安裝，透過 The Game of Thrones 這個有趣的數據集實作與練習，可以更好地理解圖算法中心度本質以及熟悉 Cypher 語法的使用。圖算法的環境安裝與配置可以參考上篇：圖算法你好：以 Neo4j 為主的開發環境與《冰與火之歌：權力遊戲》實作 (上)。

Neo4j 實作：The Game of Thrones

《冰與火之歌：權力遊戲》目前來到 Season8 ，關於角色之間的關係錯綜複雜。Andrew Beveridge 教授在 2016 年針對 Season3 第三篇的小說內容：A Storm of Swords 進行角色的關係網絡分析，並將成果（包含：數據、提取方法、網絡圖分析結果）放到 Network of Thrones 網站。

現在上面已有 Season1~Season7 角色的關係數據，透過小說的文字提取與實體識別，將角色間的互動整理成實體與邊的權重（e.g. Cersei 接觸 Tyrion 的次數為 46 次），接著透過不同定義的中心度衡量角色重要性與社區發現算法將角色作聚類。

S3E10

數據來源

以下使用 Season3: A Storm of swords 為例子，數據可以透過連結直接讀取，或是將下載的 .txt 文件，放到 neo4j/import 底下。由於是練習用，參考了 Analyzing the Graph of Thrones 的方法練習 Cypher 語法。

創建人物角色圖

# Node 表示
(src)       
(tgt)
# Edge 
-[:INTERACTS]->            // 邊的關係定義為 INTERACTS
(src)-[r:INTERACTS]->(tgt) // src的角色指向tgt的角色，其中邊的關係定義為 INTERACTS
# Property
r.weight                   //代表 INTERACTS 這個關係的屬性，這裡定義為權重

透過以下程式碼，複製到 Neo4j 瀏覽器端的程式碼輸入區塊，就可以根據來源網址一行一行讀取，將新增 source 與 target 的節點至 Character 這個集合當中，並且將角色交互次數變成邊的權重，產生的圖是動態的，可以拖拉。

Season3 角色人物關係圖：包含 107 個節點 ( Node ) 、352 條邊 ( Edge)、 459 個屬性 (Property)

篩選特定角色

四種中心度算法介紹：衡量角色重要性

以下調用的圖算法皆更新為從 algo 而來，舊版的是 apoc.algo ，兩者寫法有些微不同。

1. Degree Centrality （點度中心性）：在網絡當中，該節點和其他節點直接連接的數量 (in-degree, out-degree 數)，認為連接的數量越多代表越重要。在第三季當中，Tyrion 在 degree 數以及 out-degree 數都是第一名。

degree數/ in-degree數/ out-degree數 各取前五名

2. Betweeness Centrality（中介中心性）：成為任兩節點之間的最短路徑次數，可以鑑別「信息中間人」或是網絡聚類後的聯結點。可以根據 algo.betweeness 算出 Tyrion 仍位居第一。

betweeness 中心度的示意圖

betweenness 中心度

接著我們可以更進一步針對兩兩特定角色的最短路徑：

Tyrion 與 Grenn 的最短路徑

Tyrion 與 Grenn 的所有最短路徑

3. Closeness Centrality（緊密度中心性）：在網絡中和所有其他角色的平均距離的倒數 ( 1/d )，若一個節點跟所有其他節點的距離越近 (d越小、值越大)，代表在聚類社區之間能被其他節點高度聯結。

closeness 中心度的示意圖

closeness 中心度

4. EigenVector Centrality（特徵向量中心性）：與你連接的人越重要，你也越重要，是網頁排名 PageRank的經典算法。以網頁為例，透過加總所有連結到該網站的 PageRank 值，除以本身的 Out-degree數。可以看到，在前面三個中心度名列前茅的 Tyrion 在 Pagerank 的算法下居然排到第16 名。

pagerank

小結

Andrew Beveridge 教授對小說內容進行角色的關係網絡分析研究十分有趣（Networks of Thrones：A Storm of Swords），顯然以下結果跟我們在用 Neo4j 中心度算法算出的排序結果有些微不同（PageRank & Betweeness 的部分），原因有可能是 Neo4j 封裝的圖算法跟 Andrew 教授他們使用的工具所封裝圖算法寫法不同的關係。

Andrew 教授整理各種 Centrality 方法的角色重要性排序

若想試試看其他季的數據集與角色關係探勘，也可以到 Network of Thrones 網站下載原始數據集和各季的完整分析（比如：第三季的完整分析）。

參考來源

1. Network of Thrones | A Song of Math and Westeros
2. Analyzing the Graph of Thrones · William Lyon
3. Cypher Style Guide — Neo4j Graph Database Platform
4. graphgist — Neo4j Graph Database Platform
5. 基于社区发现算法和图分析Neo4j解读《权力的游戏》 | 神机喵算

如果這篇文章有幫助到你，可以幫我在下方綠色的拍手圖示按5下，只要登入Google或FB，不需任何花費就能【免費支持】youmgmi 繼續創作。