本案例使用 igraph 对空手道网络进行中心度分析及社区发现。

本案例主要包括以下内容：

1. Python图分析工具包介绍
2. 构建空手道俱乐部图Graph
    2.1 读取gml文件
    2.2 绘制空手道俱乐部图并渲染
3. 中心度分析
    3.1 计算中心度数值
    3.2 制作`color_num`个渐变配色方案
    3.3 中心度分析
4. 社区发现
    4.1 基于层次聚类和模块度的社区发现
    4.2 层次聚类树状图 Dendrogram

空手道俱乐部网络是一个经典的社交网络。20世纪70年代初期，美国社会学家Zachary用了两年的时间来观察美国一所大学中空手道俱乐部34名成员间的社会关系。

基于俱乐部成员们在内部及外部的交往情况，他构造了成员之间的关系网。 该网络包含34个节点，其中每个节点代表一个成员，若两个成员之间至少是交往频繁的朋友关系，则对应的节点之间有一条边。 由于俱乐部教练(节点1)与主管(节点34)之间发生争执而分裂成以各自为核心的两个小俱乐部，小俱乐部成员分别用黄色节点和绿色节点表示。该网络包含两个真实的社区，很多研究者使用该网络来检验社区发现算法的效果。

空手道俱乐部网络数据集可以通过该链接下载，但是大部分的python图分析工具包其本身就包含了该数据集或者可以调用包中方法从远程链接中直接下载。

本案例首先对当前比较流行的python图分析工具包进行介绍，然后选择了igraph工具包对空手道俱乐部网络进行分析，分析过程包括构建图、节点中心度分析以及社区发现三个部分。其余网络分析软件和工具包比较可以参考文章。

0 包版本信息

通过在notebook中执行shell命令查看包的版本。

In [1]:
!pip freeze | grep python-igraph

python-igraph==0.7.1.post6

1 Python图分析工具包介绍

比较流行的python的图分析工具包有igraph、NetworkX和graph-tool。NetworkX是一个纯粹的python实现，而igraph是用C中实现的，在Python和R都可以调用，所以从时间消耗上看igraph优于NetworkX。

下图是三个库在同一图上(共有39796个节点，301498条边)实现的几个代表性算法的性能比较：

python-igraph包的安装参考python-igraph官网。一定要注意的是不能直接使用pip install igraph，这个方法下载到的包并不是我们使用到的图分析著名工具包iGraph。

由于该包需要依赖C语言的一些图形渲染工具，故安装过程可能出现一些依赖问题，读者需要耐心的一步一步解决，可能性很多，不再一一赘述。下面简单的说一下MacOS系统安装的流程(在Anaconda环境中执行igraph，如果是系统自带python环境使用brew install)：

conda install cairo
pip install python-igraph
pip install cairocffi

作者也是踩过很多坑，然后才总结出来以上的安装步骤的，如果使用以上的代码还不work，那就需要读者自行寻找答案了。祝你好运！

2 构建空手道俱乐部图Graph

In [21]:
from igraph import *
import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np
import pandas as pd
%matplotlib inline

igraph提供了Nexus可以远程获取常用的网络进行分析，如Nexus.get("karate")可以直接获得空手道俱乐部的图，但是由于远程域名http://nexus.igraph.org/现在无法正常解析，所以我们选择直接到UCL网络数据集下载空手道俱乐部的网络文件。

2.1 读取gml文件

igraph可以读取多种格式的网络数据文件，如net、gml、graphml和pajek等。这里，我们调用Read_GML读取网络数据，并存为一个Graph对象，之后的所有分析都需要调用该对象。

In [22]:
karate = Graph.Read_GML('karate.gml')

2.2 绘制空手道俱乐部图并渲染

我们可以使用summary()和plot()函数分别观察空手道俱乐部网络的基本信息以及画出其网络图。

In [31]:
print summary(karate)

# 使用字典 visual_style 对图形的一些布局进行设置
layout = karate.layout('kk') # 使用常见的Kamada-Kawai布局
visual_style = {}
visual_style["edge_color"] = "gray" # 设置边的颜色
visual_style["vertex_size"] = 20 # 节点大小设置
visual_style["vertex_color"] = 'rgb(218.89, 232.93, 245.96)'# 节点颜色设置
visual_style["layout"] = layout # 设置布局模板
visual_style["bbox"] = (300, 300) # 设置大小
visual_style["margin"] = 20 # 设置图形离边缘的距离
visual_style["edge_curved"] = False # 指定边为弯曲或者直边
plot(karate, **visual_style)

IGRAPH U--- 34 78 -- 
+ attr: id (v)
None
Out[31]:

该网络包含34个节点，78条边，并且数据文件中包含了id属性，代表了每一个节点的id信息。并且是一个无向网络图。接下来我们使用节点中的id信息将其标记在图中的节点上，我们通过karate.vs增加新的属性label用于对节点进行标记，这个新的属性与id实际上是一样的。plot()函数在画图时会自动根据label标记节点。

In [32]:
# 将id转换了int类型
karate.vs['label'] = [int(item) for item in karate.vs['id']] 
plot(karate, **visual_style)
Out[32]:

3 中心度分析

使用igraph我们需要记住，对节点进行操作需要结合karate.vs()函数，其中的"vs"是“vertexs”的简写，中文意思是顶点的意思，与我们常常说的节点(node)是同一个意思。对于边的操作需要结合karate.es()函数，其中"es"是“edges”的简写，即是边的意思，比较好理解。

接下来我们将计算每个节点的各个中心度值，使用由浅至深的颜色标记各个节点，并且颜色越深表示中心度值越大。

3.1 计算中心度数值

首先计算度中心度、介数中心度、紧密中心度和特征向量中心度的数值。

In [33]:
degree_cent = karate.degree() # 度中心度
between_cent = karate.betweenness() # 介数中心度
closeness_cent = karate.closeness() #紧密中心度
eigen_cent = karate.eigenvector_centrality() # 特征向量中心度

为了使得颜色的深浅能够刻画出各节点之间中心度的相对大小关系，我们采用以下思路进行绘制：

  • 制作color_num个不同的颜色方案colors，并且为同一颜色由浅至深
  • 利用等距离散化将中心度值划分为color_num个区间bins
  • 将每个节点的中心度与所属的区间对应起来，对每个节点进行从属标记vs_belongs
  • 区间bins与colors一一对应，根据节点所属区间取出对应的颜色进行绘制

3.2 制作color_num个渐变配色方案

首先，我们的配色方案是10个由浅到深的蓝色。

In [34]:
vsnumber = karate.vcount() # 网络节点数
color_num = 20
sns.palplot(sns.color_palette("Blues",color_num))
colors = [x for x in sns.color_palette("Blues",color_num)]

接下来定义根据中心度的值绘制不同节点颜色的函数(为了重复画四种中心度条件下的网络图)，这一段比较难理解，请耐心：

In [35]:
def colors_by_centrality(centrality):
    """
    输入：centrality，中心度值的列表
    输出：karate.vs["colors"],每个节点对应的颜色值列表
    """
    centrality_df = pd.DataFrame(centrality, index=range(1,vsnumber+1), columns=['centrality'])
    bound_low = min(centrality_df['centrality'])
    bound_high = max(centrality_df['centrality'])

    # 获得color_num个区间
    bins = list(np.linspace(bound_low, bound_high, color_num+1))
    bins[-1] = bound_high+0.001 # 保证最大值在最后一个区间内
    bins[0] = bound_low-0.001 # 保证0在第一个区间内

    # 每个节点对应的区间用(0,...,9)标记
    vs_belongs = pd.cut(centrality_df['centrality'],bins, labels= range(0,color_num))

    # 设置每个节点的颜色属性colors
    for vertex in karate.vs():
        vs_belong = vs_belongs.iloc[vertex.index]
        rgb_code = tuple(map(lambda x:x*255, colors[vs_belong])) #将颜色百分比转换为0-255的RGB值
        vertex["colors"] = 'rgb'+str(rgb_code)
    return karate.vs["colors"]

3.3 中心度分析

In [36]:
# 度中心度
visual_style["vertex_color"] = colors_by_centrality(degree_cent)
plot(karate,**visual_style)
Out[36]:
In [37]:
# 介数中心度
visual_style["vertex_color"] = colors_by_centrality(between_cent)
plot(karate,**visual_style)
Out[37]:
In [38]:
# 紧密中心度
visual_style["vertex_color"] = colors_by_centrality(closeness_cent)
plot(karate,**visual_style)
Out[38]:
In [39]:
# 特征向量中心度
visual_style["vertex_color"] = colors_by_centrality(eigen_cent)
plot(karate,**visual_style)
Out[39]:

对于四种中心度度量方式，节点1和节点34的中心度值都比其他节点大，回忆案例最开始讲解的网络由来，发现这与实际情况一致。

4 社区发现

最后，我们使用不同的社区发现算法进行社区发现。igraph提供了许多种社区发现算法，我们这里使用基于边介数的GN算法community_edge_betweenness()和基于贪婪模式的模块度优化的Newman快速算法community_fastgreedy()。Newman快速算法无法指定最终切分为多少个社区，而GN算法可以设置clusters参数指定。

4.1 基于层次聚类和模块度的社区发现

In [46]:
# 运行社区发现算法
gn = karate.community_edge_betweenness(clusters=2)
nf = karate.community_fastgreedy()
karate.com
membership_gn = gn.as_clustering().membership
membership_nf = nf.as_clustering().membership

这样我们就可以给每个节点打上从属社区的标签。

还是先使用seaborn指定三个漂亮的渲染颜色，这里从seaborn的xkcd颜色方案中选择了三个漂亮的颜色，如果经常用seaborn画图，建议收藏此网站，使用频率会很高。

In [47]:
colors_cd = ["powder blue",'eggshell','light sage'] # cd表示community_dectection
sns.palplot(sns.xkcd_palette(colors_cd),size=2)
colors_cd = [x for x in sns.xkcd_palette(colors_cd)] # 转成一个rgb百分值列表

GN算法社区发现结果

In [48]:
for vertex in karate.vs():
    color_belong = membership_gn[vertex.index]
    rgb_code = tuple(map(lambda x:x*255, colors_cd[color_belong])) #将颜色百分比转换为0-255的RGB值
    vertex["colors"] = 'rgb'+str(rgb_code)

visual_style["vertex_color"] = karate.vs["colors"]
plot(karate,**visual_style)
Out[48]:

与真实网络比较，我们发现节点3划分错误，它应属于节点1所在社区。

Newman快速算法社区发现结果

In [45]:
for vertex in karate.vs():
    color_belong = membership_nf[vertex.index]
    rgb_code = tuple(map(lambda x:x*255, colors_cd[color_belong])) #将颜色百分比转换为0-255的RGB值
    vertex["colors"] = 'rgb'+str(rgb_code)

visual_style["vertex_color"] = karate.vs["colors"]
plot(karate,**visual_style)
Out[45]:

Newman快速算法分出了三个社区。

4.2 层次聚类树状图 Dendrogram

我们可以直接使用karate.community_edge_betweenness(clusters=2)的结果，画出层次聚类树状图，如下所示。

In [129]:
plot(karate.community_edge_betweenness(clusters=2), bbox=[0,0,450,420])
Out[129]: