用 NetworkX + Gephi + NebulaGraph 分析 <权力的游戏>人物关系（上篇）

权力的游戏

我们都知道《权利的游戏》在全世界都很多忠实的粉丝，除去你永远不知道剧情下一秒谁会挂这种意外“惊喜”，当中复杂交错的人物关系也是它火爆的原因之一，而本文介绍如何通过 NetworkX 访问开源的分布式图数据库 NebulaGraph，并借助可视化工具—— Gephi 来可视化分析《权力的游戏》中的复杂的人物图谱关系。

数据集

本文的数据集来源：冰与火之歌第一卷(至第五卷)[1]

人物集 (点集）：书中每个角色建模为一个点，点只有一个属性：姓名
关系集（边集）：如果两个角色在书中发生过直接或间接的交互，则有一条边；边只有一个属性：权重，权重的大小代表交互的强弱。

这样的点集和边集构成一个图网络，这个网络存储在图数据库 NebulaGraph [2]中。

社区划分——Girvan-Newman 算法

我们使用 NetworkX [3] 内置的社区发现算法 Girvan-Newman 来为我们的图网络划分社区。

以下为「社区发现算法 Girvan-Newman」解释：

网络图中，连接较为紧密的部分可以被看成一个社区。每个社区内部节点之间有较为紧密的连接，而在两个社区间连接则较为稀疏。社区发现就是找到给定网络图所包含的一个个社区的过程。

Girvan-Newman 算法即是一种基于介数的社区发现算法，其基本思想是根据边介数中心性（edge betweenness）从大到小的顺序不断地将边从网络中移除直到整个网络分解为各个社区。因此，Girvan-Newman 算法实际上是一种分裂方法。

Girvan-Newman 算法的基本流程如下：（1）计算网络中所有边的边介数；（2）找到边介数最高的边并将它从网络中移除；（3）重复步骤 2，直到每个节点成为一个独立的社区为止，即网络中没有边存在。

概念解释完毕，下面来实操下。

使用 Girvan-Newman 算法划分社区。NetworkX 示例代码如下

comp = networkx.algorithms.community.girvan_newman(G)
k = 7
limited = itertools.takewhile(lambda c: len(c) <= k, comp)
communities = list(limited)[-1]

为图中每个点添加一个 community 属性，该属性值记录该点所在的社区编号

community_dict = {}
community_num = 0
for community in communities:
    for character in community:
        community_dict[character] = community_num
        community_num += 1
        nx.set_node_attributes(G, community_dict, 'community')

节点样式——Betweenness Centrality 算法

下面我们来调整下节点大小及节点上标注的角色姓名大小，我们使用 NetworkX 的 Betweenness Centrality 算法来决定节点大小及节点上标注的角色姓名的大小。

图中各个节点的重要性可以通过节点的中心性（Centrality）来衡量。在不同的网络中往往采用了不同的中心性定义来描述网络中节点的重要性。Betweenness Centrality 根据有多少最短路径经过该节点，来判断一个节点的重要性。

计算每个节点的介数中心性的值

betweenness_dict = nx.betweenness_centrality(G) # Run betweenness centrality

为图中每个点再添加一个 betweenness 属性

nx.set_node_attributes(G, betweenness_dict, 'betweenness')

边的粗细

边的粗细直接由边的权重属性来决定。

通过上面的处理，现在，我们的节点拥有 name、community、betweenness 三个属性，边只有一个权重 weight 属性。

下面显示一下：

import matplotlib.pyplot as plt
color = 0
color_map = ['red', 'blue', 'yellow', 'purple', 'black', 'green', 'pink']
for community in communities:
    nx.draw(G, pos = nx.spring_layout(G, iterations=200), nodelist = community, node_size = 100, node_color = color_map[color])
    color += 1
plt.savefig('./game.png')