lyao222lll的个人博客分享 http://blog.sciencenet.cn/u/lyao222lll

博文

网络分析概述之网络拓扑属性-节点和边特征

已有 816 次阅读 2019-8-17 11:44 |个人分类:概述|系统分类:科研笔记| _网络分析

网络分析概述之网络拓扑属性-节点和边特征

 

前述网络简介中提到,在数学中,“网络”(networks)通常被称为“图”(graphs),一个图G=(V,E)是一种包含“节点”集合V与“边”集合E的数学结构,其中E的元素是不同节点的无序组合{u,v}u,vV

网络图中的基本元素是节点和边。节点和边通常会存在多种属性,代表了系统中元素的自身属性,以帮助我们更好地识别网络结构。关于节点和边属性的简要描述同样可见“网络基础简介”。通常情况下,这些属性往往是系统中元素所固有的,与这些元素本身有关。除了固有属性,当元素存在于网络结构中时,会被赋予一些重要的“节点特征”;同样地,边也被赋予了重要的“边特征”。这些可帮助我们进一步分析网络的拓扑结构。

 


节点和边特征



节点特征


关于网络图中节点的很多问题,本质上是在试图理解它在网络中的“重要性”。例如在微生物网络中,有一些节点(物种)处于枢纽位置,这些核心节点(常被解读为关键种)的缺失可能会引起模块和网络的分解,因此在维持网络结构的稳定性(微生物群落结构稳定性)中发挥重要作用。

1.png

以下几种节点属性常用来量化节点“重要性”。

 

节点度(Degree

在一个网络G=(V,E)中,节点v的度(degreedv指的是与v关联的边的数量。给定一个网络图G,定义fd为度dv=d的节点vV所占的比例。{fd}d0的集合称为G的“度分布”(degree distribution),在原始的度序列(degree sequence)基础上对度值频率集合进行了缩放。

对于有向网络,节点度可以进一步分为“入度”(in-degree,记作dvin)与“出度”(out-degree,记作dvout),分别代表了指向与离开一个节点的边的数量。

2.png

 

在不同类型的网络中,节点的度(频率)分布具有不同的特征,即服从不同的分布模式。网络度分布模式反映了该网络特殊的结构特征。如微生物共发生网络的度一般符合幂律分布,大部分物种具有少量的连接数,极个别的物种具有非常多的连接数,表明微生物群落构建方式是非随机的过程。

如下展示了两种类型网络的度分布(degree distribution)。

3.png

4.png

 

加权度(Weighted degree

对于含权网络,度的一个有用的推广是节点的“强度”(strength),即与某个节点相连的边的权重之和,称为加权度(weighted degree)。强度分布与普通的节点度分布定义类似,有时也称为加权度分布(weighted degree distribution)。

5.png

 

接近中心性(Closeness centrality

接近中心性(closeness centrality)度量的思想是:如果一个节点与许多其他节点都很“接近”(close),那么节点处于网络中心位置(central)。根据Sabidussi1966)描述的标准计算方法,这一中心性定义为某节点到其它所有节点距离之和的倒数(见上文描述,网络图中节点间的“距离”(distance)这一概念,被定义为节点间最短路径的长度,若不存在路径则为正无穷;因此即为节点与图中所有其他节点之间的最短路径的长度之和的倒数),即:

image.png

其中dist(v,u)是节点u,vV的捷径距离。通常这一度量会乘以系数Nv-1归一化到[0,1]区间,用于不同图之间以及不同中心性度量之间的比较。

 

接近中心性它反映了网络中某一节点与其他节点之间的接近程度。即对于一个节点,它距离其他节点越近,那么它的接近性中心性越大,也就越“重要”。

6.png

我们设想一个实际生活中的场景(原描述出处),比如你要建一个大型的娱乐商场,你可能会希望周围的顾客到达这个商场的距离都可以尽可能地短,这个就涉及到接近中心性的概念。一般来说,那种需要让尽可能多的人使用的设施,它的接近中心度一般是比较高的。

需要注意,在有向图中,方向是很重要的,它可以产生完全不同的结果。例如,某节点可以具有外向链路(outgoing link)的高度接近中心性,但是却具有传入链路(incoming links)的低接近中心性。而在无向图中,这是无关紧要的。

 

介数中心性(Betweenness centrality

介数中心性(betweenness centrality)度量试图概括的是某个节点在多大程度上“介于”(between)其它节点对之间。该中心性基于这样一种观点:节点的“重要性”与其在网络路径中的位置有关。如果我们将这些路径视作进行通信所需的渠道,那么处于多条路径上的节点就是通信过程中的关键环节。Freeman1977)给出了最常用的介数中心性定义,即:

image.png

其中σ(s,t|v)st之间通过v的最短路径数量,而σ(s,t)st之间(无论是否通过v)的最短路径总数。当最短路径唯一时,cB (v)仅计算通过v的最短路径数量。这一中心性度量可以通过除以系数(Nv-1) (Nv-2)/2归一化到单位区间。

 

下图展示了具有较高介数中心性节点的重要性。

7.png

由于介数中心性与“路径中的流”有关,因此,高介数中心性的节点并不一定具有很高的“度”。

8.png

 

特征向量中心性(Eigenvector centrality

其它的中心性度量多基于“状态”、“声望”或“排名”的概念给出。它们试图表达的是:如果一个节点的邻居中心性越高,节点本身的中心性也越高。这类度量本质上是隐式定义的,通常可以表达为某种恰当定义的线性系统方程的特征向量形式。特征向量中心性(eigenvector centrality)的度量方法很多,例如,Bonacich1972)在前人工作的基础上,定义了以下形式的中心性度量:

image.png

向量cEi=(cEi (1),…, cEi (Nv))T是特征值问题AcEi-1cEi的解,A是网络图G的邻接矩阵。Bonacich称,α-1的最优值是A的最大特征值,而cEi是对应的特征向量。当G是无向连通图时,A的最大特征值是实数,对应的特征向量所有元素非零且同号。通常所报告的中心性度量值是特征向量元素的绝对值,由于特征向量的正交性该值会自然处于01之间。

 

下图形象地反映了“如果一个节点的邻居中心性越高,节点本身的中心性也越高”这么一种关系。

9.png

 

模块内连通性(Within-module connectivityZi)与模块间连通性(Among-module connectivityPi

模块内连通性(Within-module connectivityZi)和模块间连通性(Among-module connectivityPi)的公式如下(Guimerà and Nunes 2005):

image.png

image.png

对于ZiKi是节点i在模块Si中与其它节点的连接数,`KSi是模块Si中所有节点的K值的平均值(K值为该节点在Si中与其它节点的连接数),σKSi是模块Si中所有节点的K值的标准差。

对于PiKis是节点i在模块S中与其它节点的连接数,ki是节点i的度。M代表模块,NM即代表了所有的模块。根据公式可知,如果与某节点有关的边在所有模块中均匀分布,则该节点的Pi值接近于1;如果与某节点有关的所有的边都在其所属的模块内,则该节点的Pi值为0

 

依据节点的的拓扑特征可将节点属性分为4种类型,包括:Module hubs(模块中心点,在模块内部具有高连通度的节点,Zi > 2.5Pi <0.62),Connectors(连接节点,在两个模块之间具有高连通度的节点,Zi < 2.5Pi > 0.62),Network hubs(网路中心点,在整个网络中具有高连通度的节点,Zi < 2.5Pi > 0.62)以及Peripherals(外围节点,在模块内部和模块之间均不具有高连通度的节点,Zi > 2.5Pi <0.62)。通常将除Peripherals外的其余3种类型的节点归为关键节点(Deng et al. 2012)。

Shi等(2016)据此在野燕麦根际网络中寻找核心OTUs,文献部分截图如下。

10.png

 

边特征


上文我们讨论了几种用于确立“关键节点”的属性,事实上,与重要性有关的问题也通常是与网络节点有关。但同样地,边也具有“重要性”,有些问题自然地和边联系到一起。

 

权重(Weighted

边属性在很多分析中可以认为是权重(weighted)。但是需要注意,权重并不一定能够反映重要性的边,取决于用作权重的属性特征。例如在基因共表达网络中,如果边的权重代表了基因间表达量的相关性,那么权重对识别重要性的边就没有多大参考性。

 

介数中心性Edge betweenness centrality

边介数中心性(Edge betweenness centrality)对节点介数中心性进行了直观推广,为每条边赋予了一个值,表示通过它的最短路径数量。

11.png

 


参考资料


Eric D Kolacayk, Gabor Csardi, 网络数据的统计分析:R语言实践(李杨 译). 西安交通大学出版社, 2016.

Math Insighthttps://mathinsight.org/index/general

Network analysis of protein interaction data: an introductionhttps://www.ebi.ac.uk/training/online/course/network-analysis-protein-interaction-data-introduction/graph-theory-some-basic-definitions

Closeness Centralityhttps://www.geeksforgeeks.org/closeness-centrality-centrality-measure/

Betweenness Centralityhttps://www.sci.unich.it/~francesc/teaching/network/betweeness.html

Network Centrality Measures and Their Visualizationhttps://aksakalli.github.io/2017/07/17/network-centrality-measures-and-their-visualization.html

 

Bonacich P F. Factoring and Weighting Approaches to Status Scores and Clique Identification. Journal of Mathematical Sociology, 1972, 2(1):113-120.

Deng Y, Jiang Y H, Yang Y, et al. Molecular ecological network analyses. Bmc Bioinformatics, 2012, 13(1):113.

Freeman L C. A Set of Measures of Centrality Based on Betweenness. Sociometry, 1977, 40(1):35-41.

Guimerà R, Nunes A, Luís A. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028):895-900.

Sabidussi G. The centrality index of a graph. Psychometrika, 1966, 31(4):581-603.

Shi S, Nuccio E E, Shi Z J, et al. The interconnected rhizosphere: High network complexity dominates rhizosphere assemblages. Ecology Letters, 2016, 19(8):926-936.

Harcombe, W. Novel cooperation experimentally evolved between species. Evolution, 2010, 64(7), 0-0.

 



http://blog.sciencenet.cn/blog-3406804-1193906.html

上一篇:网络分析概述之网络基础简介
下一篇:网络分析概述之网络拓扑属性-网络特征

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-10-16 22:30

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部