基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇

摘自:http://www.toutiao.com/a6305624170701783298/
其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。

导入原始数据到Neo4j
原始数据可从网络上下载，格式如下：
Source,Target,Weight
Aemon,Grenn,5
Aemon,Samwell,31
Aerys,Jaime,18 ...

上面是人物关系的之邻接表以及关系权重。作者使用简单的数据模型：
(:Character {name})-[:INTERACTS]->(:Character {name})

带有标签Character的节点代表小说中的角色，用单向关系类型INTERACTS代表小说中的角色有过接触。节点属性会存储角色的名字name，两角色间接触的次数作为关系的属性：权重（weight）。
首先创建节点c，并做唯一限制性约束，c.name唯一，保证schema的完整性：
CREATE CONSTRAINT ON (c:Character) ASSERT c.name IS UNIQUE;

一旦约束创建即相应的创建索引，这将有助于通过角色的名字查询的性能。作者使用Neo4j的Cypher（Cypher是一种声明式图查询语言，能表达高效查询和更新图数据库）LOAD CSV语句导入数据：
LOAD CSV WITH HEADERS FROM "https://www.macalester.edu/~abeverid/data/stormofswords.csv" AS rowMERGE (src:Character {name: row.Source})MERGE (tgt:Character {name: row.Target})MERGE (src)-[r:INTERACTS]->(tgt)SET r.weight = toInt(row.Weight)

这样得到一个简单的数据模型：
CALL apoc.meta.graph

基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇

图1 ：《权力的游戏》模型的图。Character角色节点由INTERACTS关系联结
我们能可视化整个图形，但是这并不能给我们很多信息，比如哪些是最重要的人物，以及他们相互接触的信息：
MATCH p=(:Character)-[:INTERACTS]-(:Character) RETURN p

基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇

图2

人物网络分析
作者使用Neo4j的图查询语言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

图（网络）的直径
网络的直径或者测底线或者最长最短路径：
// 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

我们能看到网络中有许多长度为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

基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇
图3

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

基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇
图4

关键节点
在网络中，如果一个节点位于其它两个节点所有的最短路径上，即称为关键节点。下面我们找出网络中所有的关键节点：
// 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
从结果表格中我们可以看出有趣的结果：罗柏·史塔克（Robb）是卓戈·卡奥（Drogo）和拉姆塞·波顿（Ramsay）的关键节点。这意味着，所有联结卓戈·卡奥（Drogo）和拉姆塞·波顿（Ramsay）的最短路径都要经过罗柏·史塔克（Robb）。我们可以通过可视化卓戈·卡奥（Drogo）和拉姆塞·波顿（Ramsay）之间的所有最短路径来验证：
MATCH (a:Character {name: "Drogo"}), (b:Character {name: "Ramsay"}) MATCH p=allShortestPaths((a)-[:INTERACTS*]-(b)) RETURN p

基于社区发现算法和图分析Neo4j解读《权力的游戏》上篇

图5