【图论】计算图的n-hop邻居个数,并绘制频率分布直方图

计算图的n-hop邻居个数,并绘制频率分布直方图

在图论中,n-hop邻居(或称为K-hop邻居)是指从某个顶点出发,通过最短路径(即最少的边数)可以到达的所有顶点的集合,其中n(或K)是这个最短路径的长度。换句话说,n-hop邻居就是在图中,从一个顶点出发,经过n步可以到达的所有顶点。

举个日常生活中的例子,我们的朋友是我们的1-hop邻居,我们的朋友的朋友是我们的2-hop邻居,以此类推。如果我们想找到所有与我们最多只有三层朋友关系的人(包括我们的朋友、我们的朋友的朋友、以及我们的朋友的朋友的朋友),那么这些人就是我们的3-hop邻居。

在下图中对于中间的红色节点,玫红色的就是1-hop邻居,橙色2,粉色3。

Gaudelet, T. et al. Utilizing graph machine learning within drug discovery and development. doi:10.1093/bib/bbab159.

如何在networkx中计算n-hop邻居的数量?

由定义我们可以知道,只要找到某个节点通过最短路径为n的边就可以找到它的n-hop邻居了,那么我们就可以用nx.single_source_shortest_path_length

代码如下:

import networkx as nx
def n_hop_neighbors(G, n_hop):
    """
    Calculate n-hop neighbors for each node in the graph.
    """
    n_hop_counts = {}
    for node in G.nodes():
        # n_hop_counts[node] = len(list(nx.single_source_shortest_path_length(G, node, cutoff=n_hop))) - 1
        n_hop_counts[node] = len(list(nx.single_source_shortest_path_length(G, node, cutoff=n_hop).keys())) - 1
        
    n_hop_array = list(n_hop_counts.values())
    return n_hop_array

绘制分布直方图

我们使用seaborn的sns.histplot来进行绘制,代码如下:

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
# Assuming G is your NetworkX graph
# Example graph
# G = nx.Graph()
# G.add_edges_from([('v1', 'v2'), ('v2', 'v4'), ('v1', 'v3')])
plt.figure(figsize=(6, 3))

# Calculate n-hop neighbors for n=1
# n_hop_counts = n_hop_neighbors(G, 3)
# Step 1: Store n-hop counts in a dictionary
n_hop_counts_dict = {}
for i in range(1, 5): # Hop counts 1 through 4
    n_hop_counts_dict[f'{i}-hop'] = n_hop_neighbors(G, i)

# Step 2: Convert the dictionary to a DataFrame
n_hop_counts_df = pd.DataFrame(n_hop_counts_dict)

# Reshape the DataFrame to long format
n_hop_counts_long = n_hop_counts_df.melt(var_name='n-hop', value_name='Number of cells in n-hop neighbourhood')
# Plotting the histogram
sns.histplot(data=n_hop_counts_long, x="Number of cells in n-hop neighbourhood", hue="n-hop", kde=False, log_scale=False, stat="probability")
plt.xlim(0, 110)
plt.grid(False)
plt.show()

结果如下:

image-20240314161010809

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/457581.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

[linux]信号处理:信号编码、基本API、自定义函数和集合操作的详解

一、信号的概述 1、定义 信号是 Linux 进程间通信的最古老的方式。信号是软件中断,它是在软件层次 上对中断机制的一种模拟,是一种异步(不等待)通信的方式 。信号可以导致一个正在运行的进程被 另一个正在运行的异步进程中断&a…

Qt_vc++崩溃日志分析

环境 Clion :2019.3.6 Qt :5.9.6(vc2015) 编译工具:vs2015 update3 崩溃日志收集 自行百度,会查到很多,一下代码仅供参考(来自https://blog.csdn.net/weixin_45571586/article/…

修改vscode的相对路径计算逻辑

vscode的相对路径计算逻辑是,"./"表示当前项目的文件夹,而不是当前文件所在的文件夹 做出如下修改: File-->Preferences-->settings 搜索Execute in File Dir , 然后取消勾选

医学图像目标跟踪论文阅读笔记 2024.03.08~2024.03.14

“Inter-fractional portability of deep learning models for lung target tracking on cine imaging acquired in MRI-guided radiotherapy” 2024年 期刊 Physical and Engineering Sciences in Medicine 医学4区 没资源,只读了摘要,用的是U-net、a…

79岁TVB老戏骨宣布离巢另寻生计。

以童星身份出道的香港资深艺人冯素波(波姐)纵横影视圈超过70年,不少人认识她还是在TVB剧中,不过她昨日却突然宣布要离开TVB,令不少网友震惊。 其实早在几个月前已经有消息称波姐会离开TVB,不过本人一直没有…

爬虫逆向实战(35)-MyToken数据(MD5加盐)

一、数据接口分析 主页地址:MyToken 1、抓包 通过抓包可以发现数据接口是/ticker/currencyranklist 2、判断是否有加密参数 请求参数是否加密? 通过查看“载荷”模块可以发现有一个code参数 请求头是否加密? 无 响应是否加密&#xf…

【数学建模】线性规划

针对未来可能的数学建模比赛内容,我对学习的内容做了一些调整,所以先跳过灰色关联分析和模糊综合评价的代码,今天先来了解一下运筹规划类——线性规划模型。 背景: 某数学建模游戏有三种题型,分别是A,B&am…

架构实战--以海量存储系统讲解热门话题:分布式概念

关注我,持续分享逻辑思维&管理思维; 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导; 有意找工作的同学,请参考博主的原创:《面试官心得--面试前应该如何准备》,《面试官心得--面试时如何进行自…

Jmeter扩展开发--自定义java取样器

简介 jmeter内置了包括:http、https、tcp等各种协议的支持,通常情况只需要做简单的参数配置即可使用。但在某些特殊情况下,还是希望能做自定义压测处理,此时就涉及Jmeter的扩展开发自定义Java取样器,如下图所示&#…

QT 如何防止 QTextEdit 自动滚动到最下方

在往QTextEdit里面append字符串时,如果超出其高度,默认会自动滚动到QTextEdit最下方。但是有些场景可能想从文本最开始的地方展示,那么就需要禁止自动滚动。 我们可以在append之后,添加如下代码: //设置编辑框的光标位…

HTML 列表 || 表格 || 表单

目录 1. 列表1.1 无序列表1.2 有序列表1.3 定义列表 2. 表格2.1 表格基本标签2.2 表格结构标签2.3 合并单元格 3. 表单3.1 input 标签基本使用3.1.1 单选框 radio3.1.2 上传文件 file3.1.3 多选框 checkbox 3.2 表单下拉菜单3.3 表单文本域3.4 label 标签3.5 按钮 button 正文开…

想要自己制作一款游戏,需要掌握哪些基本技能?

你是否曾经沉浸在游戏的世界中,感受到游戏带来的无限乐趣?你是否曾经梦想能够亲手制作一款属于自己的游戏,为玩家带来独特的体验?然而,要实现自己的游戏创作梦想,并不是一件轻松的事情。需要掌握各种技能和…

mac【启动elasticsearch报错:can not run elasticsearch as root

mac【启动elasticsearch报错:can not run elasticsearch as root 问题原因 es默认不能用root用户启动,生产环境建议为elasticsearch创建用户。 解决方案 为elaticsearch创建用户并赋予相应权限。 尝试了以下命令创建用户,adduser esh 和u…

uniapp中人脸识别图片并圈起人脸

效果如上,我用的是阿里云的人脸识别。首先,我们先封装一个阿里云的请求js文件 faceRecognition.js import CryptoJS from crypto-js//SignatureNonce随机数字 function signNRandom() {const Rand Math.random()const mineId Math.round(Rand * 1000…

visual studio 中添加qt类报错问题

添加ImportSetting类,在构造函数声名处已经写Q_OBJECT宏,但仍然报错。 无法解析的外部符号"public::virtual struct QMetaObject const*_cdecl ImportSettingFromFile::metaObject(void)const "(?metaObjectImportSettingFromFileUEBAPEBUQM…

Spring boot创建第一个项目

作者简介: zoro-1,目前大二,正在学习Java,数据结构,spring等 作者主页: zoro-1的主页 欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖💖 Spring boot创建第一个项目 sp…

Python 基于 OpenCV 视觉图像处理实战 之 图像相关的基本概念,以及图像的基础操作 二

Python 基于 OpenCV 视觉图像处理实战 之 图像相关的基本概念,以及图像的基础操作 二 目录 Python 基于 OpenCV 视觉图像处理实战 之 图像相关的基本概念,以及图像的基础操作 二 一、简单介绍 二、图像的几何变换 三、插值算法 1、最近邻插值算法 …

Spring中的BeanFactory

BeanFactory,以Factory结尾,表示是一种工厂。 作用: 是一个接口,定义了生产Bean对象的工厂应有的方法,如下图,定义了一个Bean工厂,最基本的方法。 职责: 它是负责生产和管理bean的一个工厂&…

AJAX 05 axios拦截器、数据管理平台

AJAX 学习 AJAX 05 黑马头条-数据管理平台项目准备业务1:验证码登录bootstrap提示框实际业务中的验证码登录token 【注】HTML遗落的知识【注】JS遗漏的知识业务2:个人信息设置 & axios拦截器axios请求拦截器axios响应拦截器 业务3:发布文…

LabVIEW电磁阀特性测控系统

LabVIEW电磁阀特性测控系统 电磁阀作为自动化工程中的重要组成部分,其性能直接影响系统的稳定性和可靠性。设计一种基于LabVIEW的电磁阀特性测控系统,通过高精度数据采集和智能化控制技术,实现电磁阀流阻、响应时间及脉冲特性的准确测量和分…