图(Graph)--经典图特征工程:节点分析

简介: 本文分享了关于学习参考多变博客文献后总结的 经典图特征工程 分析方法,以供参考学习

图分析--节点重要度

图节点重要性分析 是一种用于评估网络中节点重要性的方法,它可以帮助识别网络中最重要的节点,从而更好地理解网络的结构和功能。以下是图节点重要性分析的一些应用:

  • 社交网络分析:在社交网络中,节点重要性可以用来识别最具影响力的人物,例如社交网络中的“大V”或“意见领袖”。这些节点通常具有很高的中心性和影响力,可以帮助我们更好地理解社交网络中的信息传播和社交互动。
  • 交通网络分析:在交通网络中,节点重要性可以用来识别最重要的路口或交通枢纽,例如高速公路的收费站或机场的航站楼。这些节点通常具有很高的中心性和连通性,可以帮助我们更好地理解交通网络的结构和流量分布。
  • 生物网络分析:在生物网络中,节点重要性可以用来识别最重要的基因或蛋白质,例如在蛋白质相互作用网络中,具有很高介数中心性的蛋白质通常被认为是重要的调控因子。这些节点的识别可以帮助我们更好地理解生物网络的结构和功能。
  • 金融网络分析:在金融网络中,节点重要性可以用来识别最重要的金融机构或市场参与者,例如在股票市场中,具有很高度中心性的交易商通常被认为是市场的重要参与者。这些节点的识别可以帮助我们更好地理解金融网络的结构和风险传播。

总之,图节点重要性分析在各种领域都有广泛的应用,可以帮助我们更好地理解网络的结构和功能,从而更好地进行决策和规划。

1、度中心性(Degrree Centrality)

在网络分析中,常用 中心性(Centrality) 来判断网络中节点重要性或影响力。最直接的度量是度中心性(Degrree centrality),即一个节点的度越大就意味着这个节点越重要,这也是最简单的节点重要性排序方法。节点$i$的度 定义为该节点连接的邻居数目,一个节点的度值($k_i$)越大,从而表示其在网络中的作用越重要。这一指标背后的假设是:重要的节点就是拥有许多连接的节点。你的社会关系越多,你的影响力就越强。

在大多数社会网络中, 节点的度遵守幂律分布——度很大的结点的数量只占一个网络中结点总数量的少部分,而度较小的结点的数量却占大多数。这些度较大的结点自然比同一网络中的其他结点发挥着更大的作用。因此,可以认为它们是更重要的节点。
$$ C_{D}{(n_i)} = \sum_{j}{A_{ij}}$$
当需要比较不同网络中的结点的重要性时,可对度中心性的值实施规范化:
$$ C^{'}_{D}{(n_i)} = \frac {C_{D}{(n_i)}}{N-1} , \ \small {N表示节点 n_i 所属网络中节点的总数}$$
2、特征向量中心性( Eigenvector Centrality)

Eigenvector centrality 的基本想法是: 如果一个节点周围的节点很重要,那么当前节点在网络中的重要性也比较高。 换句话说,在一个社会网络中,如果一个人拥有很多重要的朋友,那么他也将是非常重要的。所以该指标同时考虑了一个节点的邻居节点数量(即该节点的度),也考虑了 邻居节点的重要性 来综合衡量当前节点的重要性。

适用场景: 特征向量中心性主要用来识别在网络中具有很高影响力的节点,例如社交网络中的“大V”或“意见领袖”。

该思想可表达为:
$$ c_{v_i} =\frac {1}{ \lambda} \sum_{j}{c_{v_j}}, \ \small {图中任意节点的重要度取决于其邻接节点的重要度之和, \lambda 作为归一化常量}$$
设图中每个节点的重要性为 $c = (c_1,c_2,...,c_n)$ ,则该计算可转换为 : $$ \lambda c = A*c ,\ \small {矩阵A为全图的邻接矩阵}$$
该数学变形式将一个递归问题变为了求 图邻接矩阵A 的特征向量的问题。

个人关于邻接矩阵A特征值的理解: 在线性代数理论中,矩阵可以看作某种运动(复杂变换),而且这种运动的某些特点可以透过矩阵的特征值和对应的特征向量所反映。将矩阵视为一种运动,则矩阵特征向量反映了对象在空间中的运动方向,特征值则反映了对应特征向量所代表的方向上的运动速率。所以对于一个代表复杂运动来说,它最大速率对应的运动方向一定程度上可以用来代表这个运动的核心特点。 在图分析层面,图的邻接矩阵 是一种社会关系的完备刻画,一种网络关系的形成通常也是由其中的骨干成员所领导的,所以从邻接矩阵提取它最大特征值对应的特征向量,这个 特征向量(eigenvector) 就反映了这个网络关系中的领导信息。特征向量的分量在数学层面,用来描述原特征向量在构造特征上的贡献率。放在图关系上,由于邻接矩阵的列方向特征反映了每个节点在图中的连接关系,所以邻接矩阵的特征向量的每个分量就描述了每个节点的社会关系与图的主要领导关系的相关性,分量越大,意味着节点的社会关系对于图关系网络越重要,所以也就代表了节点在图中的成员身份,反映了节点的重要性。

特征向量中心性和度中心性不同,一个度中心性高即拥有很多连接的节点,特征向量中心性不一定高,因为所有的连接者有可能特征向量中心性很低。同理,特征向量中心性高并不意味着它的点度中心性高,它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

使用 "特征向量中心性"指标更能反映一个网络中真实起重要作用的节点。

3、介数中心性(Betweenness Centrality)

该指标计算上反映了所有节点对经过该节点的最短路径数占所有最短路径数的比例。反映了该节点在图中是否充当交通咽喉的角色,一般具有高介数中心性的节点往往在图网络中扮演着重要的桥梁和连接器的角色,对网络的稳定性和信息传递起着至关重要的作用。

适用场景:介数中心性可以用来识别在网络中具有很高控制力的节点,例如交通网络中的关键路口或生物网络中的重要基因。

Betweenness Centrality的计算过程:
4、紧密中心性(Closeness Centrality)

该指标衡量了一个节点到其他节点的平均距离的倒数,即一个节点与其他节点之间的距离越短,它的紧密中心性就越高,反映了一个节点到哪都近的特点
Closeness Centrality的计算:
$$C_v = \frac {1}{\sum_{x \neq v}{d(x,v)}}$$

5、集群系数(Clustering Coefficient)

该指标用于衡量图中节点的聚集成团的程度。它衡量的是一个节点的邻居节点之间实际存在的边数与可能存在边数之间的比值,一个节点的集群系数越高,表示它的邻居节点之间越密集,形成的社区结构也就越明显。理解到现实生活社交网络中,该指标就是衡量了你的朋友之间相互认识的程度。
Cluster coefficient的计算:
$$e_v = \frac {v\small {节点相邻节点间的真实连接数}}{k_v(k_v -1),\small k_v为v节点的邻居数} \in [0,1]$$

拓展概念:自我中心网络(ego-network),这种网络中的所有节点都与中心节点相连,中心节点的邻居节点可能相连也可能不相连。

6、图元分析/小图拓扑结构分析(Graphlet Analysis)

观察大量现实网络都存在一定规律,即它们都由大量重复的小型拓扑结构(例如三角形、四元环等)组成。Graphlet 分析是一种用于研究网络拓扑结构的方法,它可以帮助我们理解网络中的模式和规律,发现网络中的社区结构和功能模块等。此外还能帮助区分图中节点重要性近似的节点。

基本思想: 图元分析主要是对图中的图元(Graphlet)进行计数从而得到图的特征向量表示(Graph Degree Vector,GDV),进而利用该 GDV 向量来衡量节点或图的相似性。5-node Graphlet 可以描述 73维 的节点邻域角色,基本上足以充分表征节点的邻域拓扑结构信息


Graphlet分析可以应用于各种类型的网络,例如社交网络、蛋白质相互作用网络、神经元网络等。在社交网络中,Graphlet分析可以帮助我们发现社交网络中的社区结构和关键节点;在蛋白质相互作用网络中,Graphlet分析可以帮助我们发现蛋白质复合物和信号通路等功能模块;在神经元网络中,Graphlet分析可以帮助我们发现神经元网络中的模式和规律,进而深入理解神经元网络的功能和行为。 拓展学习:传统图机器学习特征提取方法 -- 图元分析

经典图特征工程的局限


R语言中用来处理图数据的软件包为 library(igraph)
python 语言中推荐 NetworkX

Reference

图神经网络从入门到入门 - 知乎 (zhihu.com)
Yufan's Blog - Graph 图节点的重要性 ( Network Centrality ) 分析 (alphafan.github.io)
谁是社会网络中最重要的人? - 知乎 (zhihu.com)
度中心性(Degrree centrality)-介数中心性(Betweeness centrality)-特征向量中心性( Eigenvector centrality)-k-壳与k-核 - 言非 - 博客园
图谱论中的谱--拉普拉斯矩阵的应用
图谱卷积预备知识1:拉普拉斯矩阵_度矩阵

目录
相关文章
|
存储 供应链 安全
【区块链】智能交易模式下的数据安全流通模型
【区块链】智能交易模式下的数据安全流通模型
571 1
|
数据采集 机器学习/深度学习 自然语言处理
Masked Language Modeling,MLM
Masked Language Modeling(MLM)是一种预训练语言模型的方法,通过在输入文本中随机掩盖一些单词或标记,并要求模型预测这些掩盖的单词或标记。MLM 的主要目的是训练模型来学习上下文信息,以便在预测掩盖的单词或标记时提高准确性。
945 1
|
机器学习/深度学习 PyTorch 算法框架/工具
RGCN的torch简单案例
RGCN 是指 Relational Graph Convolutional Network,是一种基于图卷积神经网络(GCN)的模型。与传统的 GCN 不同的是,RGCN 可以处理具有多种关系(边)类型的图数据,从而更好地模拟现实世界中的实体和它们之间的复杂关系。 RGCN 可以用于多种任务,例如知识图谱推理、社交网络分析、药物发现等。以下是一个以知识图谱推理为例的应用场景: 假设我们有一个知识图谱,其中包含一些实体(如人、物、地点)以及它们之间的关系(如出生于、居住在、工作于)。图谱可以表示为一个二元组 (E, R),其中 E 表示实体的集合,R 表示关系的集合,每个关系 r ∈ R
1907 0
|
机器学习/深度学习 数据可视化 算法
图特征工程实践指南:从节点中心性到全局拓扑的多尺度特征提取
本文详细介绍了如何利用NetworkX库从图结构中提取重要特征。首先,通过定义辅助函数设置了图的可视化选项,并以Zachary网络数据集为例进行了可视化展示。接着,文章深入探讨了三类图特征:基于节点的特征(如节点度、中心性等)、基于边的特征(如最短路径、邻域重叠等)以及基于图的特征(如Graphlets、Weisfeiler-Leman特征等)。通过这些特征的提取与分析,可以全面理解网络结构,识别关键节点,分析信息流动模式,并发现潜在的隐藏模式。本文不仅展示了如何应用这些特征来揭示社交网络中的角色和联系,还强调了其在交通网络分析和生物系统研究等领域的广泛应用潜力。
491 12
图特征工程实践指南:从节点中心性到全局拓扑的多尺度特征提取
|
人工智能 API 决策智能
智胜未来:国内大模型+Agent应用案例精选,以及主流Agent框架开源项目推荐
【7月更文挑战第8天】智胜未来:国内大模型+Agent应用案例精选,以及主流Agent框架开源项目推荐
14963 134
智胜未来:国内大模型+Agent应用案例精选,以及主流Agent框架开源项目推荐
|
10月前
|
机器学习/深度学习 数据采集 算法
监督学习工作流程:从数据准备到模型部署
本文详细介绍了监督学习的工作流程,涵盖数据准备、模型选择、训练、评估与优化、部署等关键步骤,并结合具体代码示例,帮助读者全面掌握监督学习在实际项目中的应用方法。从数据收集、清洗到特征工程,再到模型训练与评估,最后部署模型,每个环节都提供了详细的指导和实践建议。适合初学者和有一定基础的读者深入学习。
445 2
|
安全 Linux 网络安全
【工具使用】几款优秀的SSH连接客户端软件工具推荐FinalShell、Xshell、MobaXterm、OpenSSH、PUTTY、Terminus、mRemoteNG、Terminals等
【工具使用】几款优秀的SSH连接客户端软件工具推荐FinalShell、Xshell、MobaXterm、OpenSSH、PUTTY、Terminus、mRemoteNG、Terminals等
116261 0
|
消息中间件 存储 NoSQL
MQ的顺序性保证:顺序队列、消息编号、分布式锁,一文全掌握!
【8月更文挑战第24天】消息队列(MQ)是分布式系统的关键组件,用于实现系统解耦、提升可扩展性和可用性。保证消息顺序性是其重要挑战之一。本文介绍三种常用策略:顺序队列、消息编号与分布式锁,通过示例展示如何确保消息按需排序。这些方法各有优势,可根据实际场景灵活选用。提供的Java示例有助于加深理解与实践应用。
752 2
|
网络协议 安全 Unix
什么是 Banner 抓取和 OS 指纹识别?
【8月更文挑战第31天】
408 0
|
编译器 开发工具 C语言
vscode安装+配置+使用+调试【保姆级教程】
vscode安装+配置+使用+调试【保姆级教程】
54542 8