四. 主要的图算法
目前大多数框架（比如 Python 的 networkx 或 Neo4J）支持的图算法类别主要有三个：
- Pathfinding（寻路）：根据可用性和质量等条件确定最优路径。我们也将搜索算法包含在这一类别中。这可用于确定最快路由或流量路由。
- Centrality（中心性）：确定网络中节点的重要性。这可用于识别社交网络中有影响力的人或识别网络中潜在的攻击目标。
- Community detection（社群检测）：评估群体聚类的方式。这可用于划分客户或检测欺诈等。
networkx 中的所有算法都可在这里找到：https://networkx.github.io/documentation/stable/reference/algorithms/index.html
我们只会介绍 networkx 中实现的最常见的基本算法。
1. 寻路和图搜索算法
- 寻路算法是通过最小化跳（hop）的数量来寻找两个节点之间的最短路径。
- 搜索算法不是给出最短路径，而是根据图的相邻情况或深度来探索图。这可用于信息检索。
1). 搜索算法
图搜索算法主要有两种：
- 宽度优先搜索（BFS）：首先探索每个节点的相邻节点，然后探索相邻节点的相邻节点；
- 深度优先搜索（DFS）：会尝试尽可能地深入一条路径，如有可能便访问新的相邻节点。
image
2). 寻路算法
a. 最短路径
最短路径计算的是一对节点之间的最短的加权（如果图有加权的话）路径。
这可用于确定最优的驾驶方向或社交网络上两个人之间的分离程度。
计算图中的最短路径的方法有很多，包括 Dijkstra 算法，这是 networkx 中的默认算法。更多有关最短路径问题的介绍请参阅：https://en.wikipedia.org/wiki/Shortest_path_problem
用空手道俱乐部图举例
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos) # 这会返回图中每个节点之间的最小路径的列表： all_shortest_path = nx.shortest_path(G_karate) # 这里打印了节点0与其余节点的最短路径 print(all_shortest_path[0]) print('---'*20) print(all_shortest_path[1]) # 例如节点0与节点26的最短路径是[0, 8, 33, 26] # 节点1与节点29的最短路径是[1, 2, 32, 29]
{0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5], 6: [0, 6], 7: [0, 7], 8: [0, 8], 10: [0, 10], 11: [0, 11], 12: [0, 12], 13: [0, 13], 17: [0, 17], 19: [0, 19], 21: [0, 21], 31: [0, 31], 30: [0, 1, 30], 9: [0, 2, 9], 27: [0, 2, 27], 28: [0, 2, 28], 32: [0, 2, 32], 16: [0, 5, 16], 33: [0, 8, 33], 24: [0, 31, 24], 25: [0, 31, 25], 23: [0, 2, 27, 23], 14: [0, 2, 32, 14], 15: [0, 2, 32, 15], 18: [0, 2, 32, 18], 20: [0, 2, 32, 20], 22: [0, 2, 32, 22], 29: [0, 2, 32, 29], 26: [0, 8, 33, 26]} ------------------------------------------------------------ {1: [1], 0: [1, 0], 2: [1, 2], 3: [1, 3], 7: [1, 7], 13: [1, 13], 17: [1, 17], 19: [1, 19], 21: [1, 21], 30: [1, 30], 4: [1, 0, 4], 5: [1, 0, 5], 6: [1, 0, 6], 8: [1, 0, 8], 10: [1, 0, 10], 11: [1, 0, 11], 12: [1, 0, 12], 31: [1, 0, 31], 9: [1, 2, 9], 27: [1, 2, 27], 28: [1, 2, 28], 32: [1, 2, 32], 33: [1, 13, 33], 16: [1, 0, 5, 16], 24: [1, 0, 31, 24], 25: [1, 0, 31, 25], 23: [1, 2, 27, 23], 14: [1, 2, 32, 14], 15: [1, 2, 32, 15], 18: [1, 2, 32, 18], 20: [1, 2, 32, 20], 22: [1, 2, 32, 22], 29: [1, 2, 32, 29], 26: [1, 13, 33, 26]}
b. 单源最短路径
单源最短路径（Single Source Shortest Path/SSSP）是找到给定节点与图中其它所有节点之间的最短路径。
这常用于 IP 网络的路由协议。
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos) # 返回对给定节点（源头）0与图中其他节点的最短路径 print(list(nx.single_source_shortest_path(G_karate, source=0)))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31, 30, 9, 27, 28, 32, 16, 33, 24, 25, 23, 14, 15, 18, 20, 22, 29, 26]
c. 所有配对最短路径
所有配对最短路径（All Pairs Shortest Path / APSP）算法是找到所有节点对之间的最短路径。
尽管能够提供相近的结果，但这比为每个节点对调用单源最短路径算法更快。该算法通常可用于确定交通网格的不同分区的流量负载。
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos) # 返回所有配对最短路径 all_path_length = list(nx.all_pairs_shortest_path_length(G_karate)) print(all_path_length[0])
(0, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 10: 1, 11: 1, 12: 1, 13: 1, 17: 1, 19: 1, 21: 1, 31: 1, 30: 2, 9: 2, 27: 2, 28: 2, 32: 2, 16: 2, 33: 2, 24: 2, 25: 2, 23: 3, 14: 3, 15: 3, 18: 3, 20: 3, 22: 3, 29: 3, 26: 3})
d. 最小权重生成树
最小权重生成树（minimum spanning tree）是图（一个树）的一个子图，其用权重和最小的边连接了图中的所有节点。
注意，最小生成树应该用于无向图。
from networkx.algorithms import tree mst = tree.minimum_spanning_edges(G_karate, algorithm='prim', data=False) edgelist = list(mst) edgelist = sorted(edgelist) G = nx.Graph()#创建空的网络图 G.add_edges_from(edgelist) plt.figure() nx.draw(G,pos = pos, node_color = 'b',edge_color = 'r',with_labels = True,font_size =18, node_size =20)
2. 社群检测
社群检测是根据给定的质量指标将节点划分为多个分组。
这通常可用于识别社交社群、客户行为或网页主题。
社区是指一组相连节点的集合。但是，目前关于社群还没有广泛公认的定义，只是社群内的节点应该要密集地相连。
image
Girvan Newman 算法是一个用于发现社群的常用算法。其通过逐步移除网络内的边来定义社区。我们将居间性称为「边居间性（edge betweenness）」。这是一个正比于穿过该边的节点对之间最短路径的数量的值。
该算法的步骤如下：
- 计算网络中所有已有边的居间性。
- 移除居间性最高的边。
- 移除该边后，重新计算所有边的居间性。
- 重复步骤 2 和 3，直到不再剩余边。
from networkx.algorithms import community import itertools k = 1 comp = community.girvan_newman(G_karate) for communities in itertools.islice(comp, k): print(tuple(sorted(c) for c in communities))
([0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21], [2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])
3. 分层聚类
在分层聚类（hierarchical clustering）中，我们构建聚类的层次结构。我们用树状图的形式表示聚类。
image
其思想是以不同的规模分析社群结构。我们通常自下而上构建树状图。我们从每个节点一个聚类开始，然后合并两个「最近」的节点。
但我们如何衡量聚类是否相近呢？我们使用相似度距离。令 d(i,j) 为 i 和 j 之间的最短路径的长度。
image
要得到最大连接，在每个步骤，被最短距离分开的两个聚类被组合到一起。相似度距离可用以下示意图阐释
image
下面回到我们的空手道示例。在应用分层聚类之前，我们需要定义每个节点之间的距离矩阵。
pcc_longueurs=list(nx.all_pairs_shortest_path_length(G_karate)) distances=np.zeros((n,n))# distances[i, j] is the length of the shortest path between i and j for i in range(n): for j in range(n): distances[i, j] = pcc_longueurs[i][1][j]
现在，我们将使用 sklearn 的 AgglomerativeClustering 函数来确定分层聚类。
from sklearn.cluster import AgglomerativeClustering clustering = AgglomerativeClustering(n_clusters=2,linkage='average',affinity='precomputed').fit_predict(distances) # 最后，根据聚类结果，用不同颜色绘出所得到的图： G.add_edges_from(edgelist) plt.figure() nx.draw(G_karate, node_color = clustering, pos=pos)
参考资料，以及更多图论经典算法
github.com/maelfabien/Graph_Analysis.ipynb
更多学习教程
github.com/maelfabien/Machine_Learning_Tutorials
五. 图机器学习的发展
将在PGL系列前置教程：图与图学习（下）展示。
