導讀：幾個月前，數學家 Andrew Beveridge和Jie Shan在數學雜誌上發表《權力的網絡》，主要分析暢銷小說《冰與火之歌》第三部《冰雨的風暴》中人物關係，其已經拍成電視劇《權力的遊戲》系列。他們在論文中介紹了如何通過文本分析和實體提取構建人物關係的網絡。緊接著，使用社交網絡分析算法對人物關係網絡分析找出最重要的角色；應用社區發現算法來找到人物聚類。
其中的分析和可視化是用Gephi做的，Gephi是非常流行的圖分析工具。但作者覺得使用Neo4j來實現更有趣。
本文為「下篇」，「上篇」見《基於社區發現算法和圖分析Neo4j解讀《權力的遊戲》上篇》。
節點中心度節點中心度給出網絡中節點的重要性的相對度量。有許多不同的方式來度量中心度，每種方式都代表不同類型的「重要性」。
度中心性(Degree Centrality)度中心性是最簡單度量，即為某個節點在網絡中的聯結數。在《權力的遊戲》的圖中，某個角色的度中心性是指該角色接觸的其他角色數。作者使用Cypher計算度中心性：
MATCH (c:Character)-[:INTERACTS]-()RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC
characterdegreeTyrion36Jon26Sansa26Robb25Jaime24Tywin22Cersei20Arya19Joffrey18Robert18從上面可以發現，在《權力的遊戲》網絡中提利昂·蘭尼斯特（Tyrion）和最多的角色有接觸。鑑於他的心計，我們覺得這是有道理的。
加權度中心性（Weighted Degree Centrality）作者存儲一對角色接觸的次數作為INTERACTS關係的weight屬性。對該角色的INTERACTS關係的所有weight相加得到加權度中心性。作者使用Cypher計算所有角色的這個度量：
MATCH (c:Character)-[r:INTERACTS]-()RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC
characterweightedDegreeTyrion551Jon442Sansa383Jaime372Bran344Robb342Samwell282Arya269Joffrey255Daenerys232介數中心性（Betweenness Centrality）介數中心性：在網絡中，一個節點的介數中心性是指其它兩個節點的所有最短路徑都經過這個節點，則這些所有最短路徑數即為此節點的介數中心性。介數中心性是一種重要的度量，因為它可以鑑別出網絡中的「信息中間人」或者網絡聚類後的聯結點。
圖6中紅色節點是具有高的介數中心性，網絡聚類的聯結點。
為了計算介數中心性，作者使用Neo4j 3.x或者apoc庫。安裝apoc後能用Cypher調用其170+的程序：
MATCH (c:Character)WITH collect(c) AS characters
CALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, score
SET node.betweenness = score
RETURN node.name AS name, score ORDER BY score DESC
緊度中心性是指到網絡中所有其他角色的平均距離的倒數。在圖中，具有高緊度中心性的節點在聚類社區之間被高度聯結，但在社區之外不一定是高度聯結的。
圖7 ：網絡中具有高緊度中心性的節點被其它節點高度聯結
MATCH (c:Character)WITH collect(c) AS characters
CALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, score
RETURN node.name AS name, score ORDER BY score DESC
Neo4j與其它工具（比如，R和Python數據科學工具）完美結合。我們繼續使用apoc運行 PageRank和社區發現（community detection）算法。這裡接著使用python-igraph計算分析。Python-igraph移植自R的igraph圖形分析庫。 使用pip install python-igraph安裝它。
從Neo4j構建一個igraph實例為了在《權力的遊戲》的數據的圖分析中使用igraph，首先需要從Neo4j拉取數據，用Python建立igraph實例。作者使用 Neo4j 的Python驅動庫py2neo。我們能直接傳入Py2neo查詢結果對象到igraph的TupleList構造器，創建igraph實例：
from py2neo import Graphfrom igraph import Graph as IGraphgraph = Graph()query = '''MATCH (c1:Character)-[r:INTERACTS]->(c2:Character)RETURN c1.name, c2.name, r.weight AS weight'''ig = IGraph.TupleList(graph.run(query), weights=True)
現在有了igraph對象，可以運行igraph實現的各種圖算法來。
PageRank作者使用igraph運行的第一個算法是PageRank。PageRank算法源自Google的網頁排名。它是一種特徵向量中心性(eigenvector centrality)算法。
在igraph實例中運行PageRank算法，然後把結果寫回Neo4j，在角色節點創建一個pagerank屬性存儲igraph計算的值：
pg = ig.pagerank()pgvs = []for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]})pgvswrite_clusters_query = '''UNWIND {nodes} AS nMATCH (c:Character) WHERE c.name = n.nameSET c.pagerank = n.pg'''graph.run(write_clusters_query, nodes=pgvs)
現在可以在Neo4j的圖中查詢最高PageRank值的節點：
MATCH (n:Character)RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10
namepagerankTyrion0.042884981999963316Jon0.03582869669163558Robb0.03017114665594764Sansa0.030009716660108578Daenerys0.02881425425830273Jaime0.028727587587471206Tywin0.02570016262642541Robert0.022292016521362864Cersei0.022287327589773507Arya0.022050209663844467社區發現（Community detection）圖8
社區發現算法用來找出圖中的社區聚類。作者使用igraph實現的隨機遊走算法（ walktrap）來找到在社區中頻繁有接觸的角色社區，在社區之外角色不怎麼接觸。
在igraph中運行隨機遊走的社區發現算法，然後把社區發現的結果導入Neo4j，其中每個角色所屬的社區用一個整數來表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering()nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx]write_clusters_query = '''UNWIND {nodes} AS nMATCH (c:Character) WHERE c.name = n.nameSET c.community = toInt(n.community)'''graph.run(write_clusters_query, nodes=nodes)
我們能在Neo4j中查詢有多少個社區以及每個社區的成員數：
MATCH (c:Character)WITH c.community AS cluster, collect(c.name) AS membersRETURN cluster, members ORDER BY cluster ASC
clustermembers0[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]1[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]2[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]3[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]4[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]5[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]6[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]7[Lancel]角色「大合影」《權力的遊戲》的權力圖。節點的大小正比於介數中心性，顏色表示社區（由隨機遊走算法獲得），邊的厚度正比於兩節點接觸的次數。
現在已經計算好這些圖的分析數據，讓我們對其進行可視化，讓數據看起來更有意義。
Neo4j自帶瀏覽器可以對Cypher查詢的結果進行很好的可視化，但如果我們想把可視化好的圖嵌入到其它應用中，可以使用Javascript可視化庫Vis.js。從Neo4j拉取數據，用Vis.js的neovis.js構建可視化圖。Neovis.js提供簡單的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": null }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" }};var viz = new NeoVis(config);viz.render();
其中：
俠天，專注於大數據、機器學習和數學相關的內容，並有個人公眾號：bigdata_ny分享相關技術文章。
若發現以上文章有任何不妥，請聯繫我。