原文：Analyzing the Graph of Thrones
几个月前，数学家Andrew Beveridge和Jie Shan在Math Horizon杂志上发表了权利的游戏的网络，其中，他们分析了小说“冰雨的风暴”，火爆的“冰与火之歌”（权利的游戏电视剧的基础）的第三卷中的角色互动网络。在他们的论文中，他们详细介绍了如何通过使用文本分析和实体抽取，来发现文本中提到的角色，从而构建角色互动网络。然后，他们应用社交网络分析算法到该网络中，以找到该网络中最重要的角色，并且应用社区检测算法来找到角色集群。
分析和可视化是通过使用Gephi，这一流行的图形分析工具，来完成的。我想，尝试使用Neo4j来复制作者的结果，将会很好玩。
数据可以在作者的网站上找到，你可以在这里下载。它看起来像这样：
Source,Target,Weight
Aemon,Grenn,5
Aemon,Samwell,31
Aerys,Jaime,18
...
这里，我们拥有整个文本中角色的邻接表和他们的互动次数。我们将使用一个简单的数据模型(:Character {name})-[:INTERACTS {weight}]->(:Character {name})。带有标签的节点Character表示文本中的角色，单个关系类型INTERACTS从该角色连接到另一个文本中交互的角色。我们将把角色名作为node属性name存储，把两个角色之间的交互数作为relationships属性weight存储。
首先，我们必须创建一个约束来断言我们架构的完整性：
CREATE CONSTRAINT ON (c:Character) ASSERT c.name IS UNIQUE;一旦创建了约束（该语句也将构建一个索引，它将提高通过角色名查找的性能），我们可以使用Cypher的LOAD CSV语句来导入数据：
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)
ON CREATE SET r.weight = toInt(row.Weight)我们有一个非常简单的数据模型：
CALL apoc.meta.graph()
权利的游戏图的数据模型。角色节点通过INTERACTS关系连接。 relationship.
我们可以看到整个图形，但这并没有给我们关于最重要人物或他们如何交互的许多信息：
MATCH p=(:Character)-[:INTERACTS]-(:Character)
RETURN p
我们将使用Cypher，这一图形查询语言来探索权利的游戏的图，在此过程中应用来自于网络分析的一些工具。这里探索的许多思路在优秀的网络，人群和市场：思考高度连接的世界中进行了详细的解释。
让我们先从简单的部分入手。在我们的图中，出现了多少个角色？
MATCH (c:Character) RETURN count(c) ╒════════╕
│count(c)│
╞════════╡
│107 │
└────────┘
每个角色交互的其他角色数的概要统计：
MATCH (c:Character)-[:INTERACTS]->()
WITH c, count(*) AS num
RETURN min(num) AS min, max(num) AS max, avg(num) AS avg_characters, stdev(num) AS stdev ╒═══╤═══╤═════════════════╤═════════════════╕
│min│max│avg_characters │stdev │
╞═══╪═══╪═════════════════╪═════════════════╡
│1 │24 │4.957746478873241│6.227672391875085│
└───┴───┴─────────────────┴─────────────────┘
一个网络的直径（或者测地线）被定义为网络中的最长最短路径。
// 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 ╒═══╤════════════════════════════════════════════════════════════╕
│len│path │
╞═══╪════════════════════════════════════════════════════════════╡
│6 │[Illyrio, Belwas, Daenerys, Robert, Tywin, Oberyn, Amory] │
├───┼────────────────────────────────────────────────────────────┤
│6 │[Illyrio, Belwas, Daenerys, Robert, Sansa, Bran, Jojen] │
├───┼────────────────────────────────────────────────────────────┤
│6 │[Illyrio, Belwas, Daenerys, Robert, Stannis, Davos, Shireen]│
├───┼────────────────────────────────────────────────────────────┤
│6 │[Illyrio, Belwas, Daenerys, Robert, Sansa, Bran, Luwin] │
└───┴────────────────────────────────────────────────────────────┘
我们可以看到，在网络中，有许多长度为6的路径。
我们可以使用Cypher中的shortestPath函数来查找图中任意两个角色的最短路径。让我们找找从Catelyn Stark到Kahl Drogo的最短路径：
// 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和Drogo的路径。我们可以使用allShortestPaths Cypher函数来查找：
// 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
如果节点位于网络中的其它两个节点之间的所有最短路径之中，那么该节点被认为是关键的。我们可以找到网络中的所有关键节点：
// 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│
╞═══════╪═══════╪═══════════╡
│Aegon │Thoros │Daenerys │
├───────┼───────┼───────────┤
│Aegon │Thoros │Robert │
├───────┼───────┼───────────┤
│Drogo │Ramsay │Robb │
├───────┼───────┼───────────┤
│Styr │Daario │Daenerys │
├───────┼───────┼───────────┤
│Styr │Daario │Jon │
├───────┼───────┼───────────┤
│Styr │Daario │Robert │
├───────┼───────┼───────────┤
│Qhorin │Podrick│Jon │
├───────┼───────┼───────────┤
│Qhorin │Podrick│Sansa │
├───────┼───────┼───────────┤
│Orell │Theon │Jon │
├───────┼───────┼───────────┤
│Illyrio│Bronn │Belwas │
└───────┴───────┴───────────┘
如果我们翻阅了有趣结果的结果表，那么可以看到，对于Drogo和Ramsay来说，Robb是一个关键节点。这意味着，所有连接Drogo和Ramsay的最短路径都经过Robb。我们可以通过看看连接Drogo和Ramsay的所有最短路径，可视化的验证这点：
MATCH (a:Character {name: "Drogo"}), (b:Character {name: "Ramsay"})
MATCH p=allShortestPaths((a)-[:INTERACTS*]-(b))
RETURN p
中心性度量为我们提供了网络中重要性的相对措施。有许多不同的中心性度量，而每种度量不同类型的“重要性”。
度中心性仅是一个节点在网络中的连接数。在权利的游戏的图的上下文中，一个角色的度中心性是该角色交互的其他角色数。我们可以像这样使用Cypher来计算度中心性：
MATCH (c:Character)
RETURN c.name AS character, size( (c)-[:INTERACTS]-() ) AS degree ORDER BY degree DESC ╒═════════╤══════╕
│character│degree│
╞═════════╪══════╡
│Tyrion │36 │
├─────────┼──────┤
│Jon │26 │
├─────────┼──────┤
│Sansa │26 │
├─────────┼──────┤
│Robb │25 │
├─────────┼──────┤
│Jaime │24 │
├─────────┼──────┤
│Tywin │22 │
├─────────┼──────┤
│Cersei │20 │
├─────────┼──────┤
│Arya │19 │
├─────────┼──────┤
│Joffrey │18 │
├─────────┼──────┤
│Robert │18 │
└─────────┴──────┘
而且我们看到，Tyrion与网络中的角色具有最多的互动。鉴于他的心计，我觉得这是有道理的。
我们存储一对角色之间的交互数，作为INTERACTS关系上的weight属性。对角色的所有INTERACTS关系上的该权重求和，我们可以获得他们的_加权度中心性_，或者他们参与的交互总数。同样，我们可以使用Cypher来为所有的角色计算该度量：
MATCH (c:Character)-[r:INTERACTS]-()
RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC ╒═════════╤══════════════╕
│character│weightedDegree│
╞═════════╪══════════════╡
│Tyrion │551 │
├─────────┼──────────────┤
│Jon │442 │
├─────────┼──────────────┤
│Sansa │383 │
├─────────┼──────────────┤
│Jaime │372 │
├─────────┼──────────────┤
│Bran │344 │
├─────────┼──────────────┤
│Robb │342 │
├─────────┼──────────────┤
│Samwell │282 │
├─────────┼──────────────┤
│Arya │269 │
├─────────┼──────────────┤
│Joffrey │255 │
├─────────┼──────────────┤
│Daenerys │232 │
└─────────┴──────────────┘
一个网络中的一个节点的中介中心性(Betweenness Centrality) 是，网络中所有的节点对之间通过该节点的最短路径数。中介中心性是一项重要的指标，因为它可以用于识别网络中的“信息代理”，或者那些连接不同集群的节点。
红色的节点具有较高的中介中心性，并且是集群的连接点。图片来源
要计算中介中心性，我们将使用新的用于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 ╒════════╤══════════════════╕
│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)是到网络中所有其他角色的平均距离的倒数。具有高接近中心性的节点通常在图中的集群之间被高度连接，但在集群外部不一定是高度连接的。
具有高接近中心性的节点连接了网络中许多其他节点。图片提供
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 │
└───────┴─────────────────────┘
我爱关于Neo4j的事情之一是，它与其他工具，例如R和Python数据科学工具配合良好。我们可以继续使用apoc来运行PageRank和社区检测算法，但是，让我们切换到使用python-igraph来计算一些分析。Python-igraph移植自R的igraph图形分析库。仅需使用pip install python-igraph，即可安装它。
要在我们的权利游戏的数据图上使用igraph，所需要做的第一件事是从Neo4j中取出数据，然后在Python中构建一个igraph实例。我们可以使用py2neo，用于Neo4j的Python驱动之一，来做到这点。我们可以将一个Py2neo查询的结果对象直接传到igraph的TupleList构造函数，以创建一个igraph实例：
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中实现的图算法了。
igraph中，我们要使用的第一个算法是PageRank。PageRank是一种最初由Google用来对网页重要性进行排序的算法，它是一种特征向量中心性(eigenvector centrality)算法。
PageRank: 每个节点的大小正比于网络中指向它的其他节点的数目和大小。图片来源wikipedia CC-BY
这里，我们将在我们的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]})
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得分的节点：
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│
└────────┴────────────────────┘
社区检测算法用以查找图中的集群。我们将使用igraph中实现的walktrap方法，来找到那些在社区之中频繁交互，但在社区之外不存在太多互动的角色的社区。
我们将运行walktrap社区检测算法，然后将新发现的社区数写回到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 n
MATCH (c:Character) WHERE c.name = n.name
SET 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 members
RETURN cluster, members ORDER BY cluster ASC ╒═══════╤═══════════════════════════════════════════════════════════════════════════╕
│cluster│members │
╞═══════╪═══════════════════════════════════════════════════════════════════════════╡
│0 │[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, S│
│ │amwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│1 │[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon A│
│ │rryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, │
│ │Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Eli│
│ │a, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chata│
│ │ya, Doran] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│2 │[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│3 │[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Je│
│ │yne, Roslin, Ramsay] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│4 │[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│5 │[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barris│
│ │tan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│6 │[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor] │
├───────┼───────────────────────────────────────────────────────────────────────────┤
│7 │[Lancel] │
└───────┴───────────────────────────────────────────────────────────────────────────┘
权利的游戏之图。节点大小正比于中介中心性，颜色表示节点集群，由walktrap方法测定，而边缘厚度正比于两个角色之间的互动数。
现在，我们已经计算出了该图的这些分析项，让我们创建一个可视化，使我们能够让这些数据有意义。
Neo4j浏览器对于可视化Cypher查询的结果是棒棒哒，但如果我们想要在另一个应用中嵌入我们的图形可视化，我们可能需要使用许多用于图形可视化的伟大的Javascript库中的一个。Vis.js就是这样的一个库，它允许我们构建互动式图形可视化。要进行从Neo4j抽取数据，并使用vis.js构建图形可视化的过程，我一直使用neovis.js，它将vis.js和Neo4j官方Javascript驱动组合在一起。Neovis.js提供了一个简单的API，允许配置可视化。例如，下面的Javascript是生成上面的可视化所需的:
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();请注意，我们已经指定：
- 在可视化中，我们想要包含带标签
Character的节点，使用合适的name作为其标题 - 节点大小应该正比于它们的
betweenness属性 - 在可视化中，我们想要包含
INTERACTS关系 - 关系的厚度应该正比于
weight属性值 - 节点应该根据
community属性值来着色，该属性标识网络中的集群 - 从
localhost上的一个Neo4j服务器中抽取数据 - 在一个id为
viz的DOM元素中展示可视化
Neovis.js需要从Neo4j拉取数据，并且基于我们的最低配置创建可视化。
- A. Beveridge and J. Shan, “Network of Thrones” Math Horizons Magazine , Vol. 23, No. 4 (2016), pp. 18-22.
- J. Kleinberg and D. Easley, Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press (2010)
所有代码可以在Github上找到。