用 NetworkX + Gephi + Nebula Graph 分析人物關係（上篇）

權力的遊戲

我們都知道《權利的遊戲》在全世界都很多忠實的粉絲，除去你永遠不知道劇情下一秒誰會掛這種意外“驚喜”，當中複雜交錯的人物關係也是它火爆的原因之一，而本文介紹如何通過 NetworkX 訪問開源的分佈式圖數據庫 Nebula Graph，並藉助可視化工具—— Gephi 來可視化分析《權力的遊戲》中的複雜的人物圖譜關係。

數據集

本文的數據集來源：冰與火之歌第一卷(至第五卷)[1]

人物集 (點集）：書中每個角色建模為一個點，點只有一個屬性：姓名
關係集（邊集）：如果兩個角色在書中發生過直接或間接的交互，則有一條邊；邊只有一個屬性：權重，權重的大小代表交互的強弱。

這樣的點集和邊集構成一個圖網絡，這個網絡存儲在圖數據庫 Nebula Graph [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')

emmm，有點醜…

NetworkX 可視化