导读 ：几个月前，数学家 Andrew Beveridge和Jie Shan在数学杂志上发表 《权力的网络》 ，主要分析畅销小说《冰与火之歌》第三部《冰雨的风暴》中人物关系，其已经拍成电视剧《权力的游戏》系列。他们在论文中介绍了如何通过文本分析和实体提取构建人物关系的网络。紧接着，使用社交网络分析算法对人物关系网络分析找出最重要的角色；应用社区发现算法来找到人物聚类。

其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。

导入原始数据到Neo4j

原始数据可从 网络上下载 ，格式如下：

Source,Target,Weight
Aemon,Grenn,5
Aemon,Samwell,31
Aerys,Jaime,18

上面是人物关系的之邻接表以及关系权重。作者使用简单的数据模型：

1

(:Character {name})-[:INTERACTS]->(:Character {name})

带有标签 Character 的节点代表小说中的角色，用单向关系类型 INTERACTS 代表小说中的角色有过接触。节点属性会存储角色的名字 name ，两角色间接触的次数作为关系的属性：权重（ weight ）。

首先创建节点c，并做唯一限制性约束， c.name 唯一，保证schema的完整性：

1

CREATE CONSTRAINT ON (c:Character) ASSERT c.name IS UNIQUE;

一旦约束创建即相应的创建索引，这将有助于通过角色的名字查询的性能。作者使用Neo4j的Cypher（Cypher是一种声明式图查询语言，能表达高效查询和更新图数据库） LOAD CSV 语句导入数据：

1
2
3
4
5

LOAD CSV WITH HEADERS FROM "https://www.macalester.edu/~abeverid/data/stormofswords.csv" AS row
MERGE (src:Character {name: row.Source})
MERGE (tgt:Character {name: row.Target})
MERGE (src)-[r:INTERACTS]->(tgt)
SET r.weight = toInt(row.Weight)

这样得到一个简单的数据模型：

1

CALL apoc.meta.graph()

图1 ：《权力的游戏》模型的图。Character角色节点由INTERACTS关系联结

我们能可视化整个图形，但是这并不能给我们很多信息，比如哪些是最重要的人物，以及他们相互接触的信息：

1
2

MATCH p=(:Character)-[:INTERACTS]-(:Character)
RETURN p

人物网络分析

作者使用Neo4j的图查询语言Cypher来做《权力的游戏》图分析，应用到了网络分析的一些工具，具体见 《网络，人群和市场：关于高度连接的世界》 。

人物数量

万事以简单开始。先看看上图上由有多少人物：

1

MATCH (c:Character) RETURN count(c)

图（网络）的直径

网络的直径或者测底线或者最长最短路径：

1
2
3
4
5
6

// Find maximum diameter of network
// maximum shortest path between two nodes
MATCH (a:Character), (b:Character) WHERE id(a) > id(b)
MATCH p=shortestPath((a)-[:INTERACTS*]-(b))
RETURN length(p) AS len, extract(x IN nodes(p) | x.name) AS path
ORDER BY len DESC LIMIT 4

最短路径

作者使用Cypher 的shortestPath函数找到图中任意两个角色之间的最短路径。让我们找出凯特琳·史塔克（Catelyn Stark ）和卓戈·卡奥（Kahl Drogo）之间的最短路径：

1
2
3
4

// Shortest path from Catelyn Stark to Khal Drogo
MATCH (catelyn:Character {name: "Catelyn"}), (drogo:Character {name: "Drogo"})
MATCH p=shortestPath((catelyn)-[INTERACTS*]-(drogo))
RETURN p

所有最短路径

联结凯特琳·史塔克（Catelyn Stark ）和卓戈·卡奥（Kahl Drogo）之间的最短路径可能还有其它路径，我们可以使用Cypher的 allShortestPaths 函数来查找：

1
2
3
4

// All shortest paths from Catelyn Stark to Khal Drogo
MATCH (catelyn:Character {name: "Catelyn"}), (drogo:Character {name: "Drogo"})
MATCH p=allShortestPaths((catelyn)-[INTERACTS*]-(drogo))
RETURN p

关键节点

在网络中，如果一个节点位于其它两个节点所有的最短路径上，即称为关键节点。下面我们找出网络中所有的关键节点：

1
2
3
4
5

// Find all pivotal nodes in network
MATCH (a:Character), (b:Character)
MATCH p=allShortestPaths((a)-[:INTERACTS*]-(b)) WITH collect(p) AS paths, a, b
MATCH (c:Character) WHERE all(x IN paths WHERE c IN nodes(x)) AND NOT c IN [a,b]
RETURN a.name, b.name, c.name AS PivotalNode SKIP 490 LIMIT 10

|a.name |b.name |PivotalNode|

1
2
3

MATCH (a:Character {name: "Drogo"}), (b:Character {name: "Ramsay"})
MATCH p=allShortestPaths((a)-[:INTERACTS*]-(b))
RETURN p

节点中心度

节点中心度 给出网络中节点的重要性的相对度量。有许多不同的方式来度量中心度，每种方式都代表不同类型的“重要性”。

度中心性(Degree Centrality)

度中心性是最简单度量，即为某个节点在网络中的联结数。在《权力的游戏》的图中，某个角色的度中心性是指该角色接触的其他角色数。作者使用Cypher计算度中心性：

1
2

MATCH (c:Character)-[:INTERACTS]-()
RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

|character|degree|

加权度中心性（Weighted Degree Centrality）

作者存储一对角色接触的次数作为 INTERACTS 关系的 weight 属性。对该角色的 INTERACTS 关系的所有 weight 相加得到加权度中心性。作者使用Cypher计算所有角色的这个度量：

1
2

MATCH (c:Character)-[r:INTERACTS]-()
RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

|character|weightedDegree|

介数中心性（Betweenness Centrality）

介数中心性 ：在网络中，一个节点的介数中心性是指其它两个节点的所有最短路径都经过这个节点，则这些所有最短路径数即为此节点的介数中心性。介数中心性是一种重要的度量，因为它可以鉴别出网络中的“信息中间人”或者网络聚类后的联结点。

图6中红色节点是具有高的介数中心性，网络聚类的联结点。

为了计算介数中心性，作者使用 Neo4j 3.x或者apoc库 。安装apoc后能用Cypher调用其170+的程序：

1
2
3
4
5

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

|name    |score             |

—|—|
|Jon |1279.7533534055322|
|Robert |1165.6025171231624|
|Tyrion |1101.3849724234349|
|Daenerys|874.8372110508583 |
|Robb |706.5572832464792 |
|Sansa |705.1985623519137 |
|Stannis |571.5247305125714 |
|Jaime |556.1852522889822 |
|Arya |443.01358430043337|
|Tywin |364.7212195528086 |

紧度中心性（Closeness centrality）

紧度中心性 是指到网络中所有其他角色的平均距离的倒数。在图中，具有高紧度中心性的节点在聚类社区之间被高度联结，但在社区之外不一定是高度联结的。

图7 ：网络中具有高紧度中心性的节点被其它节点高度联结

1
2
3
4

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

|name   |score                |

—|—|
|Tyrion |0.004830917874396135 |
|Sansa |0.004807692307692308 |
|Robert |0.0047169811320754715|
|Robb |0.004608294930875576 |
|Arya |0.0045871559633027525|
|Jaime |0.004524886877828055 |
|Stannis|0.004524886877828055 |
|Jon |0.004524886877828055 |
|Tywin |0.004424778761061947 |
|Eddard |0.004347826086956522 |

使用python-igraph

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实例：

1
2
3
4
5
6
7
8
9
10

from py2neo import Graph
from igraph import Graph as IGraph
graph = 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计算的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

pg = ig.pagerank()
pgvs = []
for p in zip(ig.vs, pg):
    print(p)
    pgvs.append({"name": p[0]["name"], "pg": p[1]})
pgvs
write_clusters_query = '''
UNWIND {nodes} AS n
MATCH (c:Character) WHERE c.name = n.name
SET c.pagerank = n.pg
'''
graph.run(write_clusters_query, nodes=pgvs)

现在可以在Neo4j的图中查询最高PageRank值的节点：

1
2

MATCH (n:Character)
RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

|name    |pagerank            |

—|—|
|Tyrion |0.042884981999963316|
|Jon |0.03582869669163558 |
|Robb |0.03017114665594764 |
|Sansa |0.030009716660108578|
|Daenerys|0.02881425425830273 |
|Jaime |0.028727587587471206|
|Tywin |0.02570016262642541 |
|Robert |0.022292016521362864|
|Cersei |0.022287327589773507|
|Arya |0.022050209663844467|

社区发现（Community detection）

社区发现算法用来找出图中的社区聚类。作者使用igraph实现的 随机游走算法 （ walktrap）来找到在社区中频繁有接触的角色社区，在社区之外角色不怎么接触。

在igraph中运行随机游走的社区发现算法，然后把社区发现的结果导入Neo4j，其中每个角色所属的社区用一个整数来表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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 n
MATCH (c:Character) WHERE c.name = n.name
SET c.community = toInt(n.community)
'''
graph.run(write_clusters_query, nodes=nodes)

我们能在Neo4j中查询有多少个社区以及每个社区的成员数：

1
2
3

MATCH (c:Character)
WITH c.community AS cluster, collect(c.name) AS  members
RETURN cluster, members ORDER BY cluster ASC

角色“大合影”

《权力的游戏》的权力图。节点的大小正比于介数中心性，颜色表示社区（由随机游走算法获得），边的厚度正比于两节点接触的次数。
现在已经计算好这些图的分析数据，让我们对其进行可视化，让数据看起来更有意义。

Neo4j自带浏览器可以对Cypher查询的结果进行很好的可视化，但如果我们想把可视化好的图嵌入到其它应用中，可以使用Javascript可视化库 Vis.js 。从Neo4j拉取数据，用Vis.js的 neovis.js 构建可视化图。Neovis.js提供简单的API配置，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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分享相关技术文章。
英文原文： Analyzing the Graph of Thrones