networkx学习与使用——（6）图划分与介数计算

networkx学习与使用——（5）图划分与介数计算

• 摘要
• 图划分
• • 例子生成
  
  
• 介数定义及计算
• • 定义
  • networkx计算边介数
  • • 通过networkx的最短路算法实现
    • 使用networkx的内置函数计算
    
    
  • 结果分析
  
  
• 参考

图划分按照一定规则将一个连通图划分成几个连通分量，看上去有点像聚类的感觉。从网络的角度，会根据一些重要的节点或边来进行划分，这里介绍划分图的指标——边介数。

图划分一般有两种方法，“删边法"和"聚集法”。删边法通过删除某条"重要"的边进行划分。聚集法通过将最"接近"的节点聚集起来构成不同的区域。这里介绍依据边介数进行删边的图划分方法。

例子生成

import networkx as nx #载入networkx包
import matplotlib.pyplot as plt #用于画图
#生成图
G = nx.Graph() #无向图
G_edges = [(1,2),(1,3),(2,3),(3,7),(4,5),
(4,6),(5,6),(6,7),(7,8),(8,9),
(8,12),(9,10),(9,11),(10,11),(12,13),
(12,14),(13,14)]
G.add_edges_from(G_edges)
labels={}
for node in G.nodes():
labels[node]=str(node)
#画图
pos = nx.kamada_kawai_layout(G)
plt.rcParams['figure.figsize']= (6, 4) # 设置画布大小
nx.draw_networkx_nodes(G,pos) # 画节点
nx.draw_networkx_edges(G,pos) # 画边
nx.draw_networkx_labels(G,pos,labels) # 画标签
plt.axis('off') # 去掉坐标刻度
plt.show()


如果要将上图中的图用删边法将图一分为二，我们会删除哪条边呢？我们一从图中一眼就会选择删除7-8这条边，这是为什么呢？当然我们可以说是因为这条边是割边，但6-7,3-7,8-9和8-12这些边也是割边，为什么我们会更倾向于7-8这条边呢？介数通过某条边传递信息的数量来描述边的重要性给出了一种解释。

定义

百度百科：介数通常分为边介数和节点介数两种，其中节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例，而边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。

以上图为例，上图共有14个节点，因此存在1413/2=91条最短路径(上图不存在两个节点间存在多条最短路径的情况)。然后我们计算经过7-8边的最短路径的数量：可以这样考虑，只有上面的节点到达下面的节点需要经过7-8，因此经过7-8的最短路径为77=49条最短路径。所以7-8的边介数为




49


/


91


≈


0.5385



49/91\approx0.5385


49/91≈0.5385。

networkx计算边介数

通过networkx的最短路算法实现

通过定义我们发现可以通过最短路路径的算法来实现介数的计算，在networkx学习与使用——（3）路与圈中我们介绍了如何使用networkx对图的最短路进行计算。接下来我们根据最短路的一些函数来设计介数的函数：

def betweeness(G):
all_shortest_path = []
result_dict = {}
node_list = list(G.nodes)
for i in range(len(node_list)):
for j in range(i+1,len(node_list)):
u = node_list[i]
v = node_list[j]
all_shortest_path += list(nx.all_shortest_paths(G, u, v))
all_shortest_path_num = len(all_shortest_path)
for edge in G.edges:
u, v = edge
result_dict[(u,v)] = 0
for path in all_shortest_path:
if u in path and v in path:
result_dict[(u,v)] += 1
result_dict[(u,v)] /= all_shortest_path_num
return result_dict


out:
{(1, 2): 0.01098901098901099,
(1, 3): 0.13186813186813187,
(2, 3): 0.13186813186813187,
(3, 7): 0.3626373626373626,
(4, 5): 0.01098901098901099,
(4, 6): 0.13186813186813187,
(5, 6): 0.13186813186813187,
(7, 6): 0.3626373626373626,
(7, 8): 0.5384615384615384,
(8, 9): 0.3626373626373626,
(8, 12): 0.3626373626373626,
(9, 10): 0.13186813186813187,
(9, 11): 0.13186813186813187,
(10, 11): 0.01098901098901099,
(12, 13): 0.13186813186813187,
(12, 14): 0.13186813186813187,
(13, 14): 0.01098901098901099}


使用networkx的内置函数计算

nx.edge_betweenness()


{(1, 2): 0.01098901098901099,
(1, 3): 0.13186813186813187,
(2, 3): 0.13186813186813187,
(3, 7): 0.3626373626373627,
(4, 5): 0.01098901098901099,
(4, 6): 0.13186813186813187,
(5, 6): 0.13186813186813187,
(7, 6): 0.3626373626373627,
(7, 8): 0.5384615384615385,
(8, 9): 0.3626373626373627,
(8, 12): 0.3626373626373627,
(9, 10): 0.13186813186813187,
(9, 11): 0.13186813186813187,
(10, 11): 0.01098901098901099,
(12, 13): 0.13186813186813187,
(12, 14): 0.13186813186813187,
(13, 14): 0.01098901098901099}


结果分析

恩，结果一样，没啥大bug，小bug出现了再说。所以我们可以看到7-8的介数最大，即通过7-8的信息是最多的；其次是6-7,3-7,8-9和8-12这些割边，即使都不是割边，我们也能发现1-3和2-3是比1-2重要的边。

networkx官网地址：https://networkx.org/