经典图特征工程---节点分析

作者: 倪桦 | 来源:发表于2023-05-12 11:18 被阅读0次

图分析--节点重要度

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

社交网络分析：在社交网络中，节点重要性可以用来识别最具影响力的人物，例如社交网络中的“大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

拓展阅读

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

经典图特征工程---节点分析

图分析--节点重要度

1、度中心性(Degrree Centrality)

2、特征向量中心性( Eigenvector Centrality)

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

3、介数中心性(Betweenness Centrality)

4、紧密中心性(Closeness Centrality)

5、集群系数(Clustering Coefficient)

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

经典图特征工程的局限

拓展阅读

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读