Python 分析权力游戏图表
几个月前，数学家 Andrew Beveridge 和 Jie Shan 在 Math Horizon 杂志上发表了 权利的游戏的网络 ，其中，他们分析了小说“冰雨的风暴”，火爆的“冰与火之歌”（权利的游戏电视剧的基础）的第三卷中的角色互动网络。在他们的论文中，他们详细介绍了如何通过使用文本分析和实体抽取，来发现文本中提到的角色，从而构建角色互动网络。然后，他们应用社交网络分析算法到该网络中，以找到该网络中最重要的角色，并且应用社区检测算法来找到角色集群。
分析和可视化是通过使用 Gephi，这一流行的图形分析工具，来完成的。我想，尝试使用 Neo4j 来复制作者的结果，将会很好玩。
导入初始数据到 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
中心性度量
中心性度量 为我们提供了网络中重要性的相对措施。有许多不同的中心性度量，而每种度量不同类型的“重要性”。
度中心性(Degree Centrality)
度中心性仅是一个节点在网络中的连接数。在权利的游戏的图的上下文中，一个角色的度中心性是该角色交互的其他角色数。我们可以像这样使用 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)
一个网络中的一个节点的 中介中心性(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)
接近中心性(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 │
└───────┴─────────────────────┘
使用 python-igraph
我爱关于 Neo4j 的事情之一是，它与其他工具，例如 R 和 Python 数据科学工具配合良好。我们可以继续使用 apoc 来运行 PageRank 和 社区检测 算法，但是，让我们切换到使用 python-igraph 来计算一些分析。Python-igraph 移植自 R 的 igraph 图形分析库。仅需使用 pip install python-igraph ，即可安装它。
从 Neo4j 构建一个 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 中实现的图算法了。
PageRank
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 上找到 。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论