一. 图是什么?
首先我们导入需要的包
import numpy as np import random import networkx as nx from IPython.display import Image import matplotlib.pyplot as plt
图的定义
图表示物件与物件之间的关系的数学对象,是图论的基本研究对象。
举个例子,一个简单的图可能是这样:
image
节点(node)用红色标出,通过黑色的边(edge)连接。
图可用于表示:
- 社交网络
- 网页
- 生物网络
- …
我们可以在图上执行怎样的分析?
- 研究拓扑结构和连接性
- 群体检测
- 识别中心节点
- 预测缺失的节点
- 预测缺失的边
- …
我们首先在我们的笔记本中导入第一个预构建的图:
# Load the graph # Zachary的空手道俱乐部网络 G_karate = nx.karate_club_graph() # Find key-values for the graph pos = nx.spring_layout(G_karate) # print(pos) # Plot the graph nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)
空手道俱乐部图
这个「空手道」图表示什么?Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员,成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间,管理员 JohnA 与教练 Mr.Hi(化名)之间出现了冲突,导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部,另一半则找了一个新教练或放弃了空手道。基于收集到的数据,除了其中一个成员,Zachary 正确分配了所有成员在分裂之后所进入的分组。
图的基本表示方法
- 图 G=(V, E) 由下列要素构成:
- 一组节点(也称为 verticle)V=1,…,n
- 一组边 E⊆V×V
- 边 (i,j) ∈ E 连接了节点 i 和 j
- i 和 j 被称为相邻节点(neighbor)
- 节点的度(degree)是指相邻节点的数量
image
节点、边和度的示意图
- 如果一个图的所有节点都有 n-1 个相邻节点,则该图是完备的(complete)。也就是说所有节点都具备所有可能的连接方式。
- 从 i 到 j 的路径(path)是指从 i 到达 j 的边的序列。该路径的长度(length)等于所经过的边的数量。
- 图的直径(diameter)是指连接任意两个节点的所有最短路径中最长路径的长度。
举个例子,在这个案例中,我们可以计算出一些连接任意两个节点的最短路径。该图的直径为 3,因为没有任意两个节点之间的最短路径的长度超过 3。
image
一个直径为 3 的图
- 测地路径(geodesic path)是指两个节点之间的最短路径。
- 如果所有节点都可通过某个路径连接到彼此,则它们构成一个连通分支(connected component)。如果一个图仅有一个连通分支,则该图是连通的(connected)
举个例子,下面是一个有两个不同连通分支的图:
image
一个有两个连通分支的图
- 如果一个图的边是有顺序的配对,则该图是有向的(directed)。i 的入度(in-degree)是指向 i 的边的数量,出度(out-degree)是远离 i 的边的数量
image
有向图
- 如果可以回到一个给定节点,则该图是有环的(cyclic)。相对地,如果至少有一个节点无法回到,则该图就是无环的(acyclic)。
- 图可以被加权(weighted),即在节点或关系上施加权重。
- 如果一个图的边数量相比于节点数量较小,则该图是稀疏的(sparse)。相对地,如果节点之间的边非常多,则该图是密集的(dense)
Neo4J 的关于图算法的书给出了清晰明了的总结:
image
总结(来自 Neo4J Graph Book)
回到我们的空手道俱乐部图
# .degree() 属性会返回该图的每个节点的度(相邻节点的数量)的列表: n=34 print(G_karate.degree()) degree_sequence = list(G_karate.degree())
[(0, 16), (1, 9), (2, 10), (3, 6), (4, 3), (5, 4), (6, 4), (7, 4), (8, 5), (9, 2), (10, 3), (11, 1), (12, 2), (13, 5), (14, 2), (15, 2), (16, 2), (17, 2), (18, 2), (19, 3), (20, 2), (21, 2), (22, 2), (23, 5), (24, 3), (25, 3), (26, 2), (27, 4), (28, 3), (29, 4), (30, 4), (31, 6), (32, 12), (33, 17)]
# 计算边的数量,但也计算度序列的度量: nb_nodes = n # nb_arr = len(G_karate.edges()) #边的数量 avg_degree = np.mean(np.array(degree_sequence)[:,1]) # med_degree = np.median(np.array(degree_sequence)[:,1]) max_degree = max(np.array(degree_sequence)[:,1]) min_degree = np.min(np.array(degree_sequence)[:,1]) # 最后,打印所有信息: print("Number of nodes : " + str(nb_nodes)) print("Number of edges : " + str(nb_arr)) print("Maximum degree : " + str(max_degree)) print("Minimum degree : " + str(min_degree)) print("Average degree : " + str(avg_degree)) print("Median degree : " + str(med_degree))
Number of nodes : 34 Number of edges : 78 Maximum degree : 17 Minimum degree : 1 Average degree : 4.588235294117647 Median degree : 3.0
# 平均而言,该图中的每个人都连接了 4.6 个人。 # 我们可以绘出这些度的直方图: degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float') plt.figure(figsize=(12, 8)) plt.stem(degree_freq) plt.ylabel("Frequence") plt.xlabel("Degre") plt.show()
我们后面会看到,度的直方图相当重要,可用于确定我们看到的图的种类。
二. 如何存储图?
存储图的方式有三种,取决于你想用它做什么:
- 存储为边列表:
1 2
1 3
1 4
2 3
3 4
...
我们存储有边连接的每一对节点的 ID,例如:
G_karate.edges()
EdgeView([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13), (0, 17), (0, 19), (0, 21), (0, 31), (1, 2), (1, 3), (1, 7), (1, 13), (1, 17), (1, 19), (1, 21), (1, 30), (2, 3), (2, 7), (2, 8), (2, 9), (2, 13), (2, 27), (2, 28), (2, 32), (3, 7), (3, 12), (3, 13), (4, 6), (4, 10), (5, 6), (5, 10), (5, 16), (6, 16), (8, 30), (8, 32), (8, 33), (9, 33), (13, 33), (14, 32), (14, 33), (15, 32), (15, 33), (18, 32), (18, 33), (19, 33), (20, 32), (20, 33), (22, 32), (22, 33), (23, 25), (23, 27), (23, 29), (23, 32), (23, 33), (24, 25), (24, 27), (24, 31), (25, 31), (26, 29), (26, 33), (27, 33), (28, 31), (28, 33), (29, 32), (29, 33), (30, 32), (30, 33), (31, 32), (31, 33), (32, 33)])
* 使用邻接矩阵,这通常是在内存中加载的方式: 对于图中的每一个可能的配对,如果两个节点有边相连,则设为 1。如果该图是无向图,则 A 是对称的。 ![](https://ai-studio-static-online.cdn.bcebos.com/2b34d2e63e2743709e2bba2ec869034a15131b1104134bf697ed030856a1a634)
* 使用邻接列表: 1 :[2, 3, 4] 2 :[1,3] 3 :[2, 4] ... 这三种表示方式都是等价的,我们可以根据使用场景来选择图的存储方式。
三. 图的类型和性质
图可以根据不同标准进行分类,我们在这里主要讲一种分类方法,同构图与异构图。了解更多可以查看博客,图论(二)--各种图介绍
- 同构图与异构图
两个图G和H是同构图(isomorphic graphs),能够通过重新标记图G的顶点而产生图H。
如果G和H同构,那么它们的阶是相同的,它们大小是相同的,它们个顶点的度数也对应相同。
异构图是一个与同构图相对应的新概念。
传统同构图(Homogeneous Graph)数据中只存在一种节点和边,因此在构建图神经网络时所有节点共享同样的模型参数并且拥有同样维度的特征空间。
而异构图(Heterogeneous Graph)中可以存在不只一种节点和边,因此允许不同类型的节点拥有不同维度的特征或属性。