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

熟悉 Neo4j 的 Cypher 語法

6 min readAug 2, 2019

--

「工欲善其事，必先利其器」，延續上集 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 次），接著透過不同定義的中心度衡量角色重要性與社區發現算法將角色作聚類。

數據來源

以下使用 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 ，兩者寫法有些微不同。

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

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

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

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

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

小結

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