NetworkX系列教程(9)-线性代数相关

发表于 更新于 分类于 ， 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

学过线性代数的都了解矩阵,在矩阵上的文章可做的很多,什么特征矩阵,单位矩阵等.grpah存储可以使用矩阵,比如graph的邻接矩阵,权重矩阵等,这节主要是在等到graph后,如何快速得到这些信息.详细官方文档在这里

注意: 如果代码出现找不库,请返回第一个教程,把库文件导入.

线性代数相关

图矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#定义图的节点和边
nodes=['0','1','2','3','4','5','a','b','c']
edges=[('0','0',1),('0','1',1),('0','5',1),('0','5',2),('1','2',3),('1','4',5),('2','1',7),('2','4',6),('a','b',0.5),('b','c',0.5),('c','a',0.5)]

plt.subplots(1,2,figsize=(10,3))

#定义一个无向图和有向图
G1 = nx.Graph()
G1.add_nodes_from(nodes)
G1.add_weighted_edges_from(edges)

G2 = nx.DiGraph()
G2.add_nodes_from(nodes)
G2.add_weighted_edges_from(edges)

pos1=nx.circular_layout(G1)
pos2=nx.circular_layout(G2)

#画出无向图和有向图
plt.subplot(121)
nx.draw(G1,pos1, with_labels=True, font_weight='bold')
plt.title('无向图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

plt.subplot(122)
nx.draw(G2,pos2, with_labels=True, font_weight='bold')
plt.title('有向图',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])

plt.show()

#控制numpy输出小数位数
import numpy as np
np.set_printoptions(precision=3) 

#邻接矩阵
A = nx.adjacency_matrix(G1)
print('邻接矩阵:\n',A.todense())

#关联矩阵
I = nx.incidence_matrix(G1)
print('\n关联矩阵:\n',I.todense())

#拉普拉斯矩阵
L=nx.laplacian_matrix(G1)
print('\n拉普拉斯矩阵:\n',L.todense())

#标准化的拉普拉斯矩阵
NL=nx.normalized_laplacian_matrix(G1)
print('\n标准化的拉普拉斯矩阵:\n',NL.todense())

#有向图拉普拉斯矩阵
DL=nx.directed_laplacian_matrix(G2)
print('\n有向拉普拉斯矩阵:\n',DL)

#拉普拉斯算子的特征值
LS=nx.laplacian_spectrum(G1)
print('\n拉普拉斯算子的特征值:\n',LS)

#邻接矩阵的特征值
AS=nx.adjacency_spectrum(G1)
print('\n邻接矩阵的特征值:\n',AS)

#无向图的代数连通性
AC=nx.algebraic_connectivity(G1)
print('\n无向图的代数连通性:\n',AC)

#图的光谱排序
SO=nx.spectral_ordering(G1)
print('\n图的光谱排序:\n',SO)

#两个矩阵的解释看:https://blog.csdn.net/Hanging_Gardens/article/details/55670356

图矩阵示例

输出:

邻接矩阵:
 [[0.  0.  0.  0.  5.  0.  0.  0.  6. ]
 [0.  0.  0.  2.  0.  0.  0.  0.  0. ]
 [0.  0.  0.  0.  0.  0.5 0.5 0.  0. ]
 [0.  2.  0.  1.  1.  0.  0.  0.  0. ]
 [5.  0.  0.  1.  0.  0.  0.  0.  7. ]
 [0.  0.  0.5 0.  0.  0.  0.5 0.  0. ]
 [0.  0.  0.5 0.  0.  0.5 0.  0.  0. ]
 [0.  0.  0.  0.  0.  0.  0.  0.  0. ]
 [6.  0.  0.  0.  7.  0.  0.  0.  0. ]]

关联矩阵:
 [[1. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 1. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 1. 0. 0. 0.]
 [0. 1. 0. 0. 0. 1. 0. 1. 0.]
 [0. 0. 0. 1. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 1. 0. 0. 0. 1.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [1. 0. 0. 0. 0. 0. 0. 1. 0.]]

拉普拉斯矩阵:
 [[11.   0.   0.   0.  -5.   0.   0.   0.  -6. ]
 [ 0.   2.   0.  -2.   0.   0.   0.   0.   0. ]
 [ 0.   0.   1.   0.   0.  -0.5 -0.5  0.   0. ]
 [ 0.  -2.   0.   3.  -1.   0.   0.   0.   0. ]
 [-5.   0.   0.  -1.  13.   0.   0.   0.  -7. ]
 [ 0.   0.  -0.5  0.   0.   1.  -0.5  0.   0. ]
 [ 0.   0.  -0.5  0.   0.  -0.5  1.   0.   0. ]
 [ 0.   0.   0.   0.   0.   0.   0.   0.   0. ]
 [-6.   0.   0.   0.  -7.   0.   0.   0.  13. ]]

标准化的拉普拉斯矩阵:
 [[ 1.     0.     0.     0.    -0.418  0.     0.     0.    -0.502]
 [ 0.     1.     0.    -0.707  0.     0.     0.     0.     0.   ]
 [ 0.     0.     1.     0.     0.    -0.5   -0.5    0.     0.   ]
 [ 0.    -0.707  0.     0.75  -0.139  0.     0.     0.     0.   ]
 [-0.418  0.     0.    -0.139  1.     0.     0.     0.    -0.538]
 [ 0.     0.    -0.5    0.     0.     1.    -0.5    0.     0.   ]
 [ 0.     0.    -0.5    0.     0.    -0.5    1.     0.     0.   ]
 [ 0.     0.     0.     0.     0.     0.     0.     0.     0.   ]
 [-0.502  0.     0.     0.    -0.538  0.     0.     0.     1.   ]]

有向拉普拉斯矩阵:
 [[ 0.889 -0.117 -0.029 -0.087 -0.319 -0.029 -0.029 -0.129 -0.242]
 [-0.117  0.889 -0.026 -0.278 -0.051 -0.026 -0.026 -0.114 -0.056]
 [-0.029 -0.026  0.994 -0.012 -0.009 -0.481 -0.481 -0.025 -0.01 ]
 [-0.087 -0.278 -0.012  0.757 -0.097 -0.012 -0.012 -0.052 -0.006]
 [-0.319 -0.051 -0.009 -0.097  0.994 -0.009 -0.009 -0.041 -0.434]
 [-0.029 -0.026 -0.481 -0.012 -0.009  0.994 -0.481 -0.025 -0.01 ]
 [-0.029 -0.026 -0.481 -0.012 -0.009 -0.481  0.994 -0.025 -0.01 ]
 [-0.129 -0.114 -0.025 -0.052 -0.041 -0.025 -0.025  0.889 -0.045]
 [-0.242 -0.056 -0.01  -0.006 -0.434 -0.01  -0.01  -0.045  0.994]]

拉普拉斯算子的特征值:
 [-1.436e-15  0.000e+00  4.610e-16  7.000e-01  1.500e+00  1.500e+00
  4.576e+00  1.660e+01  2.013e+01]

邻接矩阵的特征值:
 [12.068+0.000e+00j  2.588+0.000e+00j -7.219+0.000e+00j -4.925+0.000e+00j
 -1.513+0.000e+00j  1.   +0.000e+00j -0.5  +2.393e-17j -0.5  -2.393e-17j
  0.   +0.000e+00j]

无向图的代数连通性:
 0.0

图的光谱排序:
 ['4', '2', '1', '0', '5', 'b', 'c', 'a', '3']

后面还有两个小节,由于对图论算法不是很明白,所以先讲明白算法原理,再使用networkX实现,如无须读算法,可以跳过算法原理部分.