图深度学习——2.图的理论知识

1.图

1.1 图的定义

图是由节点(顶点)和边构成的数学结构。图用于表示对象之间的关系,其中节点表示对象,边表示对象之间的关系。

一个图,记为 G = <V, E> ,它包括以下两个要素:

        1.节点(顶点)(Vertices):表示图中的对象或实体。通常用 V = {v1, v2, v3, …} 表示图的节点集合。

        2.边(Edges):表示对象之间的关系。通常用E = {e1, e2, e2,  …}表示图的边集合。也可用两个节点表示 E = {( v1, v2), (v2, v3), (v3, v4),  …}

例如,一个简单的无向图,其中包含一些城市和它们之间的道路。表示为二元组 G = (V, E),其中:

  • V = {a, b, c, d, e} 是城市的集合,分别代表着城市a, b, c, d, e
  • E = { (a, b), (a, c), (b, d), (c, d), (d, e) } 是道路的集合,每一对表示一条连接的道路。

节点和边的信息可以是类别型,数值型的,例如:

1.2 图的类型

根据节点和边等特征,图可以分为不同类型:

  • 有向图(Directed Graph):边有方向,从一个节点指向另一个节点。
  • 无向图(Undirected Graph):边没有方向,表示对等关系。
  • 加权图(Weighted Graph):边具有权重,代表关系的强度或成本。记为点 ???????? 到 ???????? 的权重为 ????????????​.
  • 无权图(Unweighted Graph):边没有权重。
  • 简单图(Simple Graph):每对节点之间最多只有一条边,且没有自环。
  • 多重图(Multigraph):允许多条边连接相同的节点。
  • 连通图(Connected Graph):所有节点都可以通过路径连接到其他节点。
  • 非连通图(Disconnected Graph):存在至少一个孤立节点或子图。

2.Python创建图

安装networkx库:

pip install -i https://pypi.tuna.tsinghua.edu.cn/simple networkx

networkx的中文教程 — NetworkX 2.8 文档https://www.osgeo.cn/networkx/tutorial.html创建图的基本步骤

  1. 导入NetworkX:首先,导入NetworkX库。
  2. 创建图:可以创建一个空图,或通过数据结构(如列表、字典)直接构建图。
  3. 添加节点:使用 add_node()add_nodes_from() 添加单个或多个节点。
  4. 添加边:使用 add_edge()add_edges_from() 添加单个或多个边。
  5. 操作图:可以查询节点和边、计算图的属性、执行算法等。

2.1 创建一个图:

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个空图
G = nx.Graph()

# 添加节点
G.add_nodes_from([1, 2, 3, 4, 5])

# 添加边
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

# 绘制图
nx.draw(G, with_labels=True, node_color='lightpink')
plt.show()

输出: 

3.2 创建有向图:

# 有向图
import networkx as nx
import matplotlib.pyplot as plt

# 创建一个空的有向图
G = nx.DiGraph()

# 添加节点
G.add_nodes_from([1, 2, 3, 4, 5])

# 添加有向边
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])  # 这些边是有方向的

# 绘制有向图
# with_labels:是否有节点标签,node_color:节点的颜色
nx.draw(G, with_labels=True, node_color='lightblue', arrowstyle='-|>')
plt.show()

输出:

2.3 创建有权图:

# 创建一个空的加权图
WG = nx.DiGraph()  # 也可以是 nx.Graph(),取决于是否需要有向

# 添加节点
WG.add_nodes_from([1, 2, 3, 4, 5])

# 添加加权边
WG.add_edge(1, 2, weight=0.5)
WG.add_edge(2, 3, weight=1.2)
WG.add_edge(3, 4, weight=0.8)
WG.add_edge(4, 5, weight=1.5)
WG.add_edge(5, 1, weight=2.0)

# 绘制加权图
# 使用边权重进行可视化
edge_labels = nx.get_edge_attributes(WG, 'weight')

nx.draw(WG, with_labels=True, node_color='lightgreen', arrowstyle='-|>')
nx.draw_networkx_edge_labels(WG, pos=nx.spring_layout(WG), edge_labels=edge_labels)
plt.show()

3.图的性质

3.1 邻接节点(neighbors)

  • 节点 ????????​ 的邻接节点是与节点 ???????? 直接相连的节点,其被记为 ????(????????)。
  • 节点 ???????? 的 ???? 跳远的邻接节点(neighbors with ????-hop)是到节点 ????????​ 要走 ???? 步的节点(一个节点的 2 跳远的邻接节点包含了自身)。

3.2 图的度(degree)

一个顶点在图中的 (degree)为与这个顶点相连接的边的数目。

如下图,武则天的度为6,上官婉儿的度为1。

在无向图中,节点的度表示与该节点直接相连的边的数量:

  • 度(Degree):无向图中节点的度是连接到该节点的边的数量。度越高,表示该节点越活跃。
  • 平均度:整个图中所有节点的平均度。
  • 最大度和最小度:图中节点的最高和最低度。

在有向图中,度分为两种:入度和出度:

  • 入度(In-degree):指向某个节点的边的数量,表示有多少条边进入该节点。
  • 出度(Out-degree):从某个节点发出的边的数量,表示有多少条边从该节点出去。
  • 总度(Total degree):入度和出度的总和。

我们使用一个 NetworkX 中自带的图 The Karate Club Network(空手道俱乐部网络)进行学习。空手道俱乐部网络描述了空手道俱乐部 34 名成员的社交网络,并记录了在俱乐部外互动的成员之间的链接。

# 创建一个空手道俱乐部网络
G = nx.karate_club_graph()

# G 是否是一个有向图
print(type(G))

# 可视化图
nx.draw(G, with_labels = True, node_color='Gold')
plt.show()

# 计算了每个节点的度,接着计算了度的总和,并用节点数量求平均
# 获取所有节点的度
degrees = dict(G.degree())

# 计算平均度
average_degree = sum(degrees.values()) / len(degrees)
print("空手道俱乐部网络的平均度是:", average_degree)

 3.3 行走(walk)和路径(path)

  • ????????????????(????1,????2)=(????1,????6,????5,????4,????1,????2),这是一次“行走”,它是一次从节点 ????1 出发,依次经过边 ????6,????5,????4,????1​,最终到达节点 ????2 的“行走”。
  • 下图所示为 ????????????????(????1,????2)=(????1,????6,????5,????4,????1,????2),其中红色数字标识了边的访问序号。
  • 在“行走”中,节点是允许重复的。
  • 路径是节点不可重复的行走。

3.4 节点间的距离和图的直径

节点距离(distance)指的是在图中两个节点之间的最短路径长度(shortest path)。对于无向图和有向图的距离计算略有不同:

  • 无向图:节点之间的距离是指通过最少的边连接这两个节点的路径长度。
  • 有向图:节点之间的距离是指沿着方向连接这两个节点的最短路径长度。

在NetworkX中,计算节点距离的方法有:

  • shortest_path_length(G, source, target): 计算两个特定节点之间的最短路径长度。
  • all_pairs_shortest_path_length(G): 计算所有节点对之间的最短路径长度。

直径(diameter):给定一个连通图 ????={????,????}G={V,E},其直径为其所有节点对之间的最短路径的最大值。

# 创建一个简单的无向图
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (1, 5)])

nx.draw(G, with_labels = True, node_color='LightGreen')
plt.show()

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

# 计算图的直径
graph_diameter = nx.diameter(G)

print("节点 1 和 3 之间的距离:", distance_1_3)
print("节点 1 和 4 之间的距离:", distance_1_4)

print("图的直径:", graph_diameter)

3.5 子图、连通分量,连通图

子图(Subgraph)

子图是从一个图中选择部分节点和边组成的新图。子图保留原始图中的连接关系,但通常包含更少的节点和边。

子图可以基于特定条件来构建,例如选择特定的节点或边。在NetworkX中,可以使用 subgraph() 方法从一个图中提取子图。例如:

# 创建一个空手道俱乐部网络
G = nx.karate_club_graph()

# 可视化完整的空手道俱乐部网络
nx.draw(G, with_labels=True, node_color='Gold', edge_color='gray')
plt.show()

# 创建子图,包括节点 0 到 5 及其连接的边
sub_G = G.subgraph([0, 1, 2, 3, 4, 5])

# 可视化子图
nx.draw(sub_G, with_labels=True, node_color='lightgreen', edge_color='blue')
plt.show()

# 打印子图中的节点和边
print("子图中的节点:", list(sub_G.nodes()))
print("子图中的边:", list(sub_G.edges()))

连通分量(Connected Component)

连通分量是指图中所有节点之间都有路径可以到达的最大子图。在无向图中,连通分量是图的一个重要性质,表示节点之间的连通性。在有向图中,有弱连通分量和强连通分量。弱连通分量是将有向图视为无向图后得到的连通分量,强连通分量则是指在有向图中,所有节点之间有路径可以到达的子图。

在NetworkX中,可以使用 connected_components() 方法找到无向图中的连通分量例如:

# 找到空手道俱乐部网络(无向图)中的连通分量
connected_components = list(nx.connected_components(G))
print("连通分量:", connected_components)

 使用 strongly_connected_components()weakly_connected_components() 方法找到有向图中的强连通和弱连通分量,例如:

# 创建一个有向图,让图中一些点不连接
# 找到有向图中的强连通分量

DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (4, 5)])

# 可视化图
nx.draw(DG, with_labels = True, node_color='Gold')
plt.show()

strongly_connected_components = list(nx.strongly_connected_components(DG))
print("强连通分量:", strongly_connected_components)

# 找到有向图中的弱连通分量
weakly_connected_components = list(nx.weakly_connected_components(DG))
print("弱连通分量:", weakly_connected_components)

连通图(Connected Graph)

连通图是指一个无向图中,所有节点之间都存在至少一条路径。连通图只有一个连通分量。

在NetworkX中,可以使用 is_connected() 方法检查一个无向图是否是连通图。例如:

# 检查无向图是否是连通图
is_connected = nx.is_connected(G)
print("该图是否是连通图:", is_connected)

3.6 聚类系数(Clustering Coefficient)

# 创建一个空手道俱乐部网络
G = nx.karate_club_graph()

# 计算每个节点的局部聚类系数
local_clustering = nx.clustering(G)

# 计算全局聚类系数(平均局部聚类系数)
global_clustering = nx.average_clustering(G)

print("局部聚类系数:", local_clustering)  # 打印所有节点的局部聚类系数
print("全局聚类系数:", global_clustering)  # 打印全局聚类系数

3.7 接近中心度 (closeness centrality)

接近中心度(Closeness Centrality)是一种度量图中节点的重要性或影响力的指标。它衡量了一个节点与其他所有节点之间的距离,也即最短路径的平均距离。接近中心度的值越高,意味着该节点与其他节点之间的距离越短,具有更大的影响力。

接近中心性计算:计算一个节点与其他节点之间的最短路径之和,再对得到的和求倒数,得到该节点的接近中心性得分。

更常见的做法是将该得分归一化,以此表示最短路径的平均长度,而不是最短路径之和。利用这一修正方法可以比较在不同规模的图中节点的接近中心性。

在NetworkX中,可以使用 closeness_centrality() 方法计算节点的接近中心度:

# 创建一个图
G= nx.Graph()

# 添加节点和边
G.add_edges_from([(1, 2),(1, 3),(2, 3),(2, 4),(3, 4),(4,5)])

# 计算接近中心度
closeness = nx.closeness_centrality(G)
# 将接近中心度转换为列表
closeness_values =list(closeness.values())

# 绘制条形
plt.bar(range(len(closeness_values)),closeness_values)
plt.xlabel("节点")
plt.ylabel("接近中心度")
plt.title("接近中心度条形图")

# 标记节点
plt.xticks(range(len(closeness_values)),closeness.keys())
# 显示图形
plt.show()

4. 邻接矩阵、关联矩阵、拉普拉斯矩阵

4.1 邻接矩阵

邻接矩阵(Adjacency Matrix)是图的一种常用表示方式,它是一个方阵,用于表示图中的节点和边的关系。邻接矩阵的大小为 ????×????,其中 ???? 是图中的节点数量。

1.无向图的邻接矩阵

在无向图中,邻接矩阵是对称的。若节点 ???? 和节点 ???? 之间存在边,则矩阵的相应位置为 1,否则为 0。

2.有向图的邻接矩阵

在有向图中,邻接矩阵不一定是对称的。若从节点 ???? 到节点 ???? 有边,则矩阵的位置 [????,????]为 1,否则为 0。

3.加权图的邻接矩阵

在加权图中,邻接矩阵的位置值是边的权重。如果没有边,则该位置的值可以设置为 0、无穷大或其他特殊值。

4.生成邻接矩阵

在NetworkX中,可以使用 to_numpy_array()adjacency_matrix() 方法来生成图的邻接矩阵。

1.无向图的邻接矩阵: 

# 创建一个图
G= nx.Graph()

# 添加节点和边
G.add_edges_from([(1, 2),(1, 3),(2, 4),(3, 4),(4,5)])
nx.draw(G, with_labels = True, node_color='yellow')
plt.show()

# 生成邻接矩阵
adj_matrix = nx.to_numpy_array(G)
print("无向图的邻接矩阵:\n", adj_matrix)

2.有向图的邻接矩阵 

# 创建一个有向图
DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (4, 5)])
nx.draw(DG, with_labels = True, node_color='Lightblue')
plt.show()

# 生成邻接矩阵
adj_matrix = nx.to_numpy_array(DG)
print("有向图的邻接矩阵:\n", adj_matrix)

 

3.加权有向图的邻接矩阵:

# 创建一个空的加权图
WG = nx.DiGraph()  # 也可以是 nx.Graph(),取决于是否需要有向

# 添加节点
WG.add_nodes_from([1, 2, 3, 4])

# 添加加权边
WG.add_edge(1, 2, weight=0.5)
WG.add_edge(2, 3, weight=1.2)
WG.add_edge(3, 4, weight=0.8)
WG.add_edge(4, 1, weight=0.5)


# 绘制加权图
# 使用边权重进行可视化
edge_labels = nx.get_edge_attributes(WG, 'weight')

nx.draw(WG, with_labels=True, node_color='lightgreen', arrowstyle='-|>')
nx.draw_networkx_edge_labels(WG, pos=nx.spring_layout(WG), edge_labels=edge_labels)
plt.show()

# 生成加权邻接矩阵
adj_matrix = nx.to_numpy_array(WG, weight='weight')

print("加权图的邻接矩阵:\n", adj_matrix)

 4.2 关联矩阵

关联矩阵(Incidence Matrix)是图的一种表示方式,展示了节点和边之间的关系。对于给定的图,关联矩阵是一个大小为 ????×????n×m 的矩阵,其中 ????n 是节点的数量,????m 是边的数量。

1.无向图的关联矩阵

在无向图中,关联矩阵的每一行对应一个节点,每一列对应一条边。如果某条边连接了节点 ???? 和节点 ????,那么对应的列中这两个节点的行将设置为 1。

2.有向图的关联矩阵

在有向图中,关联矩阵不仅表示节点和边之间的关系,还表明边的方向。如果边从节点 ???? 指向节点 ????,那么对应的列在节点 ???? 的行中设置为 -1,而在节点 ???? 的行中设置为 1。

3.生成关联矩阵

在NetworkX中,您可以使用 incidence_matrix() 方法生成关联矩阵。

# 创建一个有向图
DG = nx.DiGraph([(1, 2), (2, 3), (3, 1), (4, 5)])
nx.draw(DG, with_labels = True, node_color='Lightblue')
plt.show()

# 生成关联矩阵
inc_matrix = nx.incidence_matrix(DG, oriented=True).toarray()
print("有向图的关联矩阵:\n", inc_matrix)

# 创建一个空的加权图
WG = nx.DiGraph()  # 也可以是 nx.Graph(),取决于是否需要有向

# 添加节点
WG.add_nodes_from([1, 2, 3, 4])

# 添加加权边
WG.add_edge(1, 2, weight=0.5)
WG.add_edge(2, 3, weight=1.2)
WG.add_edge(3, 4, weight=0.8)
WG.add_edge(4, 1, weight=0.5)
WG.add_edge(2, 4, weight=0.1)

# 绘制加权图
# 使用边权重进行可视化
edge_labels = nx.get_edge_attributes(WG, 'weight')

nx.draw(WG, with_labels=True, node_color='lightgreen', arrowstyle='-|>')
nx.draw_networkx_edge_labels(WG, pos=nx.spring_layout(WG), edge_labels=edge_labels)
plt.show()

# 生成加权关联矩矩阵
inc_matrix = nx.incidence_matrix(WG, oriented=True, weight='weight').toarray()
print("加权图的关联矩阵:\n", inc_matrix)

4.3 拉普拉斯矩阵

拉普拉斯矩阵(Laplacian Matrix)是基于图的度矩阵和邻接矩阵定义的。设 ???? 为度矩阵,是一个对角矩阵,其中每个对角线元素表示相应节点的度;设 ???? 为邻接矩阵,表示图中节点之间的连接关系。

拉普拉斯矩阵定义为: ????=????−????

拉普拉斯矩阵的性质:

  • 拉普拉斯矩阵是对称矩阵。
  • 对于无向图,拉普拉斯矩阵的每一行和每一列的和都是零。
  • 拉普拉斯矩阵的特征值可以反映图的性质,例如第二小的特征值(通常称为 Fiedler 值)与图的连通性相关。

生成拉普拉斯矩阵

在NetworkX中,可以使用 laplacian_matrix()normalized_laplacian_matrix() 方法生成拉普拉斯矩阵。

5. 图的类型

  • 按照不同的划分规则,图可以被划分为很多不同的种类。在 2.2 节中,我们根据边是否具有指向性,区分得到了有向图和无向图。下面,我们会根据更多不同的属性来对图进行划分。

5.1 图的拓扑结构

图的拓扑结构是指图中节点和边的组织方式,以及它们之间的连接关系。拓扑结构反映了图的整体布局和性质,揭示了图的某些特征和行为。

例如,环(Cycle):节点和边形成的闭合路径。 树(Tree):无环连通无向图。 森林(Forest):不连通的树的集合等。

根据图的拓扑结构,规则网络(regular network)可以分为

  • 全连接网络(fully-connected network)(下图左)
  • 环形网络(ring-shape network)(下图中)
  • 星形网络(start-shape network)(下图右)

图的拓扑结构在分析网络、社交关系、数据流、任务依赖等方面具有重要意义。理解图的拓扑结构可以帮助我们理解系统的行为和特征。 

5.2 同质图和异质图

质图(Homogeneous Graph)和异质图(Heterogeneous Graph)是根据图中节点和边的性质分类的两种概念。这两个概念主要用来区分网络中节点和边的同质性或异质性。

  • 同质图(Homogeneous Graph):只有一种类型的节点和一种类型的边的图。
  • 异质图(Heterogeneous Graph):存在多种类型的节点和多种类型的边的图。

5.3 二分图

二分图是一类特殊的图,又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集合 U 和 V 的图,使得所有边都是连结一个 U 中的点和一个 V 中的点。

也就是,节点分为两类,只有不同类的节点之间存在边

二分图在很多实际应用中都发挥着重要作用,包括:

  • 匹配问题:如婚配问题、工作分配问题。
  • 社交网络:表示两类不同节点的关系,例如用户和兴趣、学生和课程。
  • 生物信息学:表示蛋白质与基因、药物与靶标的关系。

 创建二分图:

# 创建一个二分图
B = nx.Graph()

# 添加左组节点
B.add_nodes_from([1, 2, 3, 4], bipartite=0)  # bipartite=0 表示左组
# 添加右组节点
B.add_nodes_from(['A', 'B', 'C', 'D'], bipartite=1)  # bipartite=1 表示右组

# 添加边,连接左右组
B.add_edges_from([(1, 'A'), (1, 'C'), (2, 'C'), (3, 'D'), (3, 'C'), (1, 'B'), (4, 'D')])

# 检查是否是二分图
is_bipartite = nx.is_bipartite(B)

# 确定布局
# data=True: bipartite为 1
left_nodes = {n for n, d in B.nodes(data=True) if d["bipartite"] == 0}
pos = nx.bipartite_layout(B, left_nodes)

# 设置颜色
node_colors = ['lightblue' if node in left_nodes else 'lightgreen' for node in B.nodes()]

# 可视化二分图
plt.figure(figsize=(8, 6))
nx.draw(B, pos, with_labels=True, node_color=node_colors, edge_color='gray')
plt.title("二分图的可视化")
plt.show()  # 显示图形

 在分配问题中,我们通常有两个节点组:一个是资源或任务的提供者,另一个是需求者或接收者。二分图的特性使其非常适合表示这些分配问题。分配问题的目标通常是将左组和右组的节点进行最佳匹配,以满足某种条件或优化某个目标。在实际应用中,分配问题经常涉及优化,例如:

  • 最大化匹配:找到在二分图中将两个组连接最多的匹配方式。
  • 最小成本匹配:找到一种匹配方式,使总成本最小化(每条边有权重表示成本)。
  • 任务-人员分配:在一个组织中,将任务有效分配给合适的人员。

解决分配问题的常用算法包括:

  • 匈牙利算法:一种用于求解最大匹配和最小成本匹配的有效算法。
  • Hopcroft-Karp算法:用于求解二分图最大匹配的高效算法。

eg. 匈牙利法求解指派问题(运筹学):

上一篇:【Java EE】依赖注入DI详解


下一篇:艾体宝观察 | 2024,如何开展网络安全风险分析