网络拓扑结构-节点和边特征的简介和R计算

网络拓扑结构-节点和边特征

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

网络图中的基本元素是节点和边。当元素存在于网络结构中时，会被赋予一些重要的“节点特征”或“边特征”，可帮助进一步分析网络的拓扑结构。识别网络拓扑结构是网络分析的要点，本篇就一些重要的节点或边特征作简介。

重要的节点和边特征

节点特征

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

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

节点度（Degree）

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

对于有向网络，节点度可以进一步分为“入度”（in-degree，记作d_vⁱⁿ）与“出度”（out-degree，记作d_v^out），分别代表了指向与离开一个节点的边的数量。

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

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

加权度（Weighted degree）

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

接近中心性（Closeness centrality）

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

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

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

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

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

介数中心性（Betweenness centrality）

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

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

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

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

特征向量中心性（Eigenvector centrality）

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

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

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

边特征

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

权重（Weighted）

某些特定的边属性在很多分析中常被视为权重（weighted）对待。但是需要注意，权重并不一定能够反映重要性的边，取决于用作权重的属性特征。例如在基因共表达网络中，如果边的权重代表了基因间表达量的相关性，那么权重对识别重要性的边就没有多大参考性（因为通常我们只需识别到显著的相关性就可认为在网络中的两个基因间存在关系了，很少关注这种关系的强弱）。   

边的介数中心性（Edge betweenness centrality）

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

R语言计算节点和边特征

接下来，展示使用R的igraph包计算上述提到的重要节点和边特征的方法。

网络文件以邻接矩阵作为输入，文件基本格式及igraph包的入门操作可见前文网络基础概述。

示例数据和R代码链接（提取码：4n6b）：

https://pan.baidu.com/s/15r5T75HlUfomuc-GoPP2jw

library(igraph)

#输入数据示例，邻接矩阵
#这是一个微生物相关性网络，数值表示了微生物 OTU 之间的相关系数（正负相关以及相关性的大小）
adjacency_weight <- read.delim('adjacency_weight.txt', row.names = 1, sep = '\t', check.names = FALSE)
head(adjacency_weight)[1:6] #邻接矩阵类型的网络文件

#邻接矩阵 -> igraph 的邻接列表，获得含权的无向网络
igraph = graph_from_adjacency_matrix(as.matrix(adjacency_weight), mode = 'undirected', weighted = TRUE, diag = FALSE)
igraph #igraph 的邻接列表

#上述将相关系数转化为边的权重
#由于相关系数有负值，而权重正常都应为正值，所以对由相关系数得到的权重取绝对值
#新生成一列边属性记录相关系数
E(igraph)$corr <- E(igraph)$weight
E(igraph)$weight <- abs(E(igraph)$weight)
##节点特征
#节点数量
length(V(igraph)$name)
#或
vcount(igraph)

#节点度（Degree）
#由于本示例是个无向网络，故无出度和入度之分
V(igraph)$degree <- degree(igraph)
V(igraph)$degree

#查看度分布
#可观察到微生物相关网络通常服从幂律分布，这个下节再讲怎样通过计算验证
degree_dist <- degree.distribution(igraph)[-1]
degree_num <- 1:max(V(igraph)$degree)

par(mfrow = c(1, 2))
hist(V(igraph)$degree, xlab = 'Degree', ylab = 'Frequency',
main = 'Degree distribution')
plot(degree_num, degree_dist, log = 'xy', xlab = 'Log-degree',
ylab = 'Log-intensity', main = 'Log-log degree distribution')

#查看节点度与其“邻居”的平均度的关系
#微生物网络中高度值的节点更倾向连接在一起，是普遍现象吗？
neighbor_degree <- graph.knn(igraph, V(igraph))$knn
plot(V(igraph)$degree, neighbor_degree, log = 'xy',
xlab = 'Log degree', ylab = 'Log average neighbor degree')

#加权度（Weighted degree）
V(igraph)$weight_degree <- strength(igraph)
V(igraph)$weight_degree

#接近中心性（Closeness centrality）
V(igraph)$closeness_centrality <- closeness(igraph)
V(igraph)$closeness_centrality

#介数中心性（Betweenness centrality）
V(igraph)$betweenness_centrality <- betweenness(igraph)
V(igraph)$betweenness_centrality

#特征向量中心性（Eigenvector centrality）
V(igraph)$eigenvector_centrality <- evcent(igraph)$vector
V(igraph)$eigenvector_centrality

#探索三种描述节点中心性的特征的关系
library(car)

scatter3d(V(igraph)$closeness_centrality, V(igraph)$betweenness_centrality, V(igraph)$eigenvector_centrality,
xlab = 'Closeness centrality', ylab = 'Betweenness centrality', zlab = 'Eigenvector centrality',
surface = FALSE)

#探索节点度和节点中心性的关系，如与特征向量中心性的关系
plot(V(igraph)$degree, V(igraph)$eigenvector_centrality,
xlab = 'Degree', ylab = 'Eigenvector centrality')

#输出列表
node_list <- data.frame(
node_id = V(igraph)$name,
degree = V(igraph)$degree,
weight_degree = V(igraph)$weight_degree,
closeness_centrality = V(igraph)$closeness_centrality,
betweenness_centrality = V(igraph)$betweenness_centrality,
eigenvector_centrality = V(igraph)$eigenvector_centrality)

head(node_list)
write.table(node_list, 'node_list.txt', sep = '\t', row.names = FALSE, quote = FALSE)
##边特征
#边的数量
ecount(igraph)

#权重（Weighted），已在数据读入时转化获得
E(igraph)$weight

#边介数中心性（Edge betweenness centrality）
E(igraph)$betweenness_centrality <- edge.betweenness(igraph)
E(igraph)$betweenness_centrality

#输出列表
edge <- data.frame(as_edgelist(igraph)) #igraph 的邻接列表转为边列表

edge_list <- data.frame(
source = edge[[1]],
target = edge[[2]],
weight = E(igraph)$weight,
correlation = E(igraph)$corr,
betweenness_centrality = E(igraph)$betweenness_centrality
)
head(edge_list)

write.table(edge_list, 'edge_list.txt', sep = '\t', row.names = FALSE, quote = FALSE)

参考资料

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

Math Insight：https://mathinsight.org/index/general

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

Closeness Centrality：https://www.geeksforgeeks.org/closeness-centrality-centrality-measure/

Betweenness Centrality：https://www.sci.unich.it/~francesc/teaching/network/betweeness.html

Network Centrality Measures and Their Visualization：https://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.

友情链接

相关性和网络分析基础

网络分析概述之网络基础简介 

降维分析

非约束排序（描述性的探索性分析）：

非约束排序中被动添加解释变量：被动添加解释变量

约束排序（将解释变量通过回归方程拟合响应变量的统计模型）：

RDA、CCA的变差分解（VAP） 

对称分析（这类方法意在描述两个或多个矩阵之间的相关性）：

多元因子分析（MFA）

监督降维（带监督的降维方法，常用于分类）：

判别分析（DA）

聚类和分类

层次聚类（无监督，描述性的探索性分析）：

层次聚合：层次聚合分类    层次聚类结果的比较和评估

层次分划：双向指示种分析（TWINSPAN） 

非层次聚类（无监督，描述性的探索性分析）：

划分聚类：k均值划分（k-means）    围绕中心点划分（PAM）

模糊聚类：模糊c均值聚类（FCM）

避免不存在的类

潜变量分类（无监督，潜变量也可视为某种意义上的“降维”）：

潜类别分析（LCA）    潜剖面分析（LPA）约束聚类（无监督，将解释变量通过回归方程“约束”响应变量的模型）：多元回归树 

监督分类（通过已知先验分组构建分类器模型）：

决策树    随机森林分类