热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

networkx学习与使用——(6)图划分与介数计算

networkx学习与使用——(5)图划分与介数计算摘要图划分例子生成介数定义及计算定义networkx计算边介数通过networkx的最短路算法实现使用networkx的内置函数




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/



推荐阅读
  • 社交网络中的级联行为 ... [详细]
  • 本文介绍如何利用 Python 中的 NumPy 和 Matplotlib 库,从 NumPy 数组中绘制线图。通过具体的代码示例和详细解释,帮助读者理解并掌握这一技能。 ... [详细]
  • 本文介绍了SVD(奇异值分解)和QR分解的基本原理及其在Python中的实现方法。通过具体代码示例,展示了如何使用这两种矩阵分解技术处理图像数据和计算特征值。 ... [详细]
  • Redux入门指南
    本文介绍Redux的基本概念和工作原理,帮助初学者理解如何使用Redux管理应用程序的状态。Redux是一个用于JavaScript应用的状态管理库,特别适用于React项目。 ... [详细]
  • 本文旨在探讨如何利用决策树算法实现对男女性别的分类。通过引入信息熵和信息增益的概念,结合具体的数据集,详细介绍了决策树的构建过程,并展示了其在实际应用中的效果。 ... [详细]
  • C#设计模式学习笔记:观察者模式解析
    本文将探讨观察者模式的基本概念、应用场景及其在C#中的实现方法。通过借鉴《Head First Design Patterns》和维基百科等资源,详细介绍该模式的工作原理,并提供具体代码示例。 ... [详细]
  • 二维几何变换矩阵解析
    本文详细介绍了二维平面上的三种常见几何变换:平移、缩放和旋转。通过引入齐次坐标系,使得这些变换可以通过统一的矩阵乘法实现,从而简化了计算过程。文中不仅提供了理论推导,还附有Python代码示例,帮助读者更好地理解这些概念。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • Java 实现二维极点算法
    本文介绍了一种使用 Java 编程语言实现的二维极点算法。该算法用于从一组二维坐标中筛选出极点,适用于需要处理几何图形和空间数据的应用场景。文章不仅详细解释了算法的工作原理,还提供了完整的代码示例。 ... [详细]
  • 深入解析Java枚举及其高级特性
    本文详细介绍了Java枚举的概念、语法、使用规则和应用场景,并探讨了其在实际编程中的高级应用。所有相关内容已收录于GitHub仓库[JavaLearningmanual](https://github.com/Ziphtracks/JavaLearningmanual),欢迎Star并持续关注。 ... [详细]
  • 历经三十年的开发,Mathematica 已成为技术计算领域的标杆,为全球的技术创新者、教育工作者、学生及其他用户提供了一个领先的计算平台。最新版本 Mathematica 12.3.1 增加了多项核心语言、数学计算、可视化和图形处理的新功能。 ... [详细]
  • 本文将探讨2015年RCTF竞赛中的一道PWN题目——shaxian,重点分析其利用Fastbin和堆溢出的技巧。通过详细解析代码流程和漏洞利用过程,帮助读者理解此类题目的破解方法。 ... [详细]
  • 本文详细介绍了如何在 Android 中使用值动画(ValueAnimator)来动态调整 ImageView 的高度,并探讨了相关的关键属性和方法,包括图片填充后的高度、原始图片高度、动画变化因子以及布局重置等。 ... [详细]
  • 搭建Jenkins、Ant与TestNG集成环境
    本文详细介绍了如何在Ubuntu 16.04系统上配置Jenkins、Ant和TestNG的集成开发环境,涵盖从安装到配置的具体步骤,并提供了创建Windows Slave节点及项目构建的指南。 ... [详细]
  • 当unique验证运到图片上传时
    2019独角兽企业重金招聘Python工程师标准model:public$imageFile;publicfunctionrules(){return[[[na ... [详细]
author-avatar
wwjieabc_584
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有