【图算法】

大家好，今天和大家分享一下图算法中的一些基础知识，已经如何使用python中的networkx库实现网络图的基本建模 *** 作。内容较多，可通过右侧目录栏跳转。

---

1. 邻接矩阵 1.1 方法介绍

邻接矩阵是图的等价表示，邻接矩阵的元素代表网络节点连线之间的交互关系。

如图1，对于一个无向无权网络，它的邻接矩阵A是一个对称矩阵。其中对角线元素都为0，；无向表示节点之间的连线不区分方向，即节点之间是双向关系，；无权代表节点之间的边没有权重，此时邻接矩阵A是由0,1元素组成的，如果节点之间存在连边那么元素等于1，否则等于0。

根据邻接矩阵求出网络所包含的连边的数量，邻接矩阵的所有非零元素加起来除以2。 

如图2，有向无权网络，如果存在一条连边从节点 i 指向节点 j，那么  ，有向网络不一定是对称的 。

如图3，无向加权网络，和无向无权网络的区别就是，节点之间的连边有权重。因此邻接矩阵中的非零元素就不一定等于1了。网络的连边数量等于：邻接矩阵中非零元素的数量求和

如图4，自环网络，存在从节点出发到它自身的连边，该邻接矩阵中，对角线元素不一定等于0，如果存在自环那么 

---

1.2 代码实现 （1）无向无权图

创建无向图(空图)： nx.Graph()

添加节点： Graph.add_nodes_from()

添加连边： Graph.add_edges_from()

网络图可视化： nx.draw()

获取网络图的邻接矩阵： nx.adjacency_matrix( Graph ).todense()

通过邻接矩阵获得网络图： nx.from_numpy_matrix( matrix )

#（1）创建图及其邻接矩阵
import networkx as nx

# 创建一个空图，不包含节点和边
G = nx.Graph()  # 无向图
# 添加节点
G.add_nodes_from([1,2,3,4])
# 添加边
G.add_edges_from([(1,2), (1,3), (2,3), (2,4)])

# 可视化
nx.draw(G, node_size=500, with_labels=True)
    
# 获取邻接矩阵, 获取的是连边
As = nx.adjacency_matrix(G)
print(As)

# 将连边转化为二维数组, 即邻接矩阵
A = As.todense()
print(A)
# [[0 1 1 0]
#  [1 0 1 1]
#  [1 1 0 0]
#  [0 1 0 0]]
 

#（2）已知邻接矩阵，创建图
import numpy as np
import networkx as nx

# 创建邻接矩阵
A = np.array([[0,1,1], [1,0,1], [1,1,0]])
# 通过邻接矩阵获得图
G = nx.from_numpy_matrix(A)

# 图可视化
nx.draw(G, node_size=500, with_labels=True)

绘图展示：

---

（2）无向加权图

在节点之间添加有权重的连边： Graph.add_weighted_edges_from()

import networkx as nx
G = nx.Graph()  # 创建无向图
# 添加连边，每条边有权重
G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5), (0, 2, 1.5)])
# 获取图的邻接矩阵，获取的是边
As = nx.adjacency_matrix(G)
# 将边转为二维矩阵
A = As.todense()
# 查看邻接矩阵
print(A)
# [[0.  3.  1.5]
#  [3.  0.  7.5]
#  [1.5 7.5 0. ]]

---

（3）有向无权图

创建有向图(空图)： nx.DiGraph()

import networkx as nx
# 创建有向图
G = nx.DiGraph()
# 添加节点
G.add_nodes_from([1,2,3,4])
# 添加边，无权重
G.add_edges_from([(1,2), (1,3), (2,3), (3,4)])
# 绘制有向图
nx.draw(G, node_size=500, with_labels=True)

---

2. 度、平均度、度分布 2.1 方法介绍

节点的度是指：该节点的邻边数量

平均度是指：所有节点的度的平均值

度分布是指：节点度的分布情况，通常用一个直方图来表示

以下图为例，节点2有三条邻边，那么节点2的度=3。该网络的平均度=（1+3+2+2）/ 4 = 2。该网络的度分布是[0,1,2,1]，节点为0的度出现了0次，度为1的节点出现了1次，出现的概率是1/4=0.25，度为2的节点出现了2次，出现的概率是0.5

---

2.2 代码展示

获取网络的所有节点： Graph.nodes

获取网络的所有节点的度： nx.degree( Graph )

获取网络的度分布： nx.degree_histogram( Graph )

返回值是位于0和最大度之间的度的值的频数列表

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# 创建无向图
G = nx.Graph()
# 添加节点
G.add_nodes_from([1,2,3,4])
# 添加边
G.add_edges_from([(1,2), (2,3), (2,4), (3,4)])

# 获取网络的度, 并转为字典类型
d = dict(nx.degree(G))
# 计算网络的平均度=节点度之和/结点个数
d_avg = sum(d.values()) / len(G.nodes)
# 获取度分布，返回所有位于区间[0, 最大度]的度值的频数列表
d_list = nx.degree_histogram(G)

print('网络的度：', d)     # {1: 1, 2: 3, 3: 2, 4: 2}
print('平均度：', d_avg)   # 2.0
print('度分布：', d_list)  # [0, 1, 2, 1]
    
# 绘制度分布直方图
# 横坐标代表度 [0, 1, 2, 3]
x = list(range(max(d.values())+1))
# 度分布除以节点总数，获得每个度的出现频率
y = np.array(d_list) / len(G.nodes)

# 绘制条形图
plt.bar(x, y, width=0.5)
plt.xlabel('du')
plt.ylabel('du_prob')
plt.grid()
plt.show()

绘制网络图，以及度分布直方图

---

3. 路径和距离 3.1 方法介绍

路径是沿着网络的链接运行的路由，路径的长度表示路径包含的链接数。在网络科学中，更多的关注的是两个节点 i 和 j 之间的最短路径，最短路径长度通常被称为两个节点之间的距离。

如下图，节点1和4之间的一条最短路径是 [1,2,3,4]，最短路径长度是 3

---

3.2 代码展示

找出两个节点之间的一条最短路径： nx.shortest_path(Graph, source=起点, target=终点)

找出两个节点之间的所有最短路径： nx.all_shortest_paths(Graph, source=起点, target=终点)

计算两个节点之间的最短路径长度： nx.shortest_path_length(Graph, source=起点, target=终点)

构建如上图所示的网络

import networkx as nx
# 创建无向图
G = nx.Graph()
# 添加节点
G.add_nodes_from([1,2,3,4,5])
# 添加连边
G.add_edges_from([(1,2), (2,3), (2,5), (3,4), (4,5)])
# 绘制网络图
nx.draw(G, node_size=500, with_labels=True)

# 计算节点1和4之间的一条最短路径
short_path = nx.shortest_path(G, source=1, target=4)
# [1, 2, 3, 4]

# 计算节点1和4之间的所有最短路径
short_path_all = list(nx.all_shortest_paths(G, source=1, target=4))
# [[1, 2, 3, 4], [1, 2, 5, 4]]

# 计算节点1和4之间的最短路径的长度
short_path_length = nx.shortest_path_length(G, source=1, target=4)
# 3

---

4. 网络的连通性 4.1 方法介绍

在无向网络中，如果任意一对接点 i 和节点 j 之间至少存在一条连边，那么网络是连通的。如果不存在连边，那么网络是不连通的。

如下图（a）所示，是由两个孤立集团组成的网络，相互之间没有通路。反映在邻接矩阵上，该矩阵是由两个分块矩阵组成的。而图（b）是连通的网络。

---

4.2 代码展示

判断网络是否连通：nx.is_connected( Graph )

创建如上图a所示的网络

import networkx as nx
# 构建一个网络
Ga = nx.Graph()
# 添加节点和边
Ga.add_nodes_from([1,2,3,4,5,6,7])
Ga.add_edges_from([(1,2), (1,3), (2,3), (4,7), (5,6), (5,7), (6,7)])
# 绘制网络图
nx.draw(Ga, node_size=500, with_labels=True)
# 查看网络是否连通
print( nx.is_connected(Ga) ) # False

---

5. 集聚系数 5.1 方法介绍

集聚系数用于比较群组的聚合紧密程度，以及群组能够达到的聚合紧密程度。

局部集聚系数的公式如下， 代表节点； 代表节点的度，即该节点的邻边数； 代表通过该节点的关系数（可通过计算经过该节点的封闭三角形的数量得到）

一个节点的局部聚类系数体现的是其邻节点也相互连通的可能性。该数值的计算过程要用到三角形计数算法。

聚类系数实际上也是一个相对的评估指标，分母的意思是衡量某个节点和其邻节点如果构成完全图的三角形数量（即图上节点的两两都存在相互连接），分子部分就是该节点实际所在的三角形的计数，二者的比值就是节点的聚类系数（也就是局部聚类系数）

整个网络的集聚程度可以由平均集聚系数所表征，它代表了所有节点的局部集聚系数的平均值：

全局集聚系数的计算公式为：3 * 三角形的个数 / 连通三元组的个数。三角形是指：节点和其邻居节点构成的封闭三角形；连通三元组是指：由该节点出发，和两个相邻节点有连边，这三个点可以不构成封闭三角形。

---

5.2 代码展示

计算某个节点的集聚系数： nx.clustering( Graph, nodes=节点 )

计算网络图的平均集聚系数： nx.average_clustering( Graph )

计算网络图的全局集聚系数： nx.transitivity( Graph )

删除网络的指定连边： Graph.remove_edges_from( 连边 )

# 创建无向图，添加节点和边
G = nx.Graph()
G.add_nodes_from([1,2,3,4,5])
G.add_edges_from([(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)])
# 绘制网络图
nx.draw(G, node_size=500, with_labels=True)

# 计算1节点的集聚系数
print(nx.clustering(G, nodes=1))  # 1.0

# 删除部分连边
G.remove_edges_from([(2,4), (3,4), (3,5)])
# 绘制网络图
nx.draw(G, node_size=500, with_labels=True)

# 计算1节点的集聚系数
print(nx.clustering(G, nodes=1))  # 0.5


#（八）平均集聚系数 和 全局集聚系数
# 创建无向图，添加节点和边
G = nx.Graph()
G.add_nodes_from([1,2,3,4,5,6,7])
G.add_edges_from([(1,2), (2,3), (2,4), (2,5), (4,5), (4,6), (4,7), (5,7)])
# 绘制网络图
nx.draw(G, node_size=500, with_labels=True)

# 平均集聚系数
print(nx.average_clustering(G))  # 0.3095238095238095

# 全局集聚系数
print(nx.transitivity(G))  # 0.375

删除部分节点连边后的网络