对复杂网络节点重要性的排序方法

前言

在生物信息学的研究中我们经常或利用到各种各样的复杂网络，无论是蛋白质互作网络还是共表达网络，从建立的网络中筛选关键的节点是重要的一步。我们经常通过对网络中节点的重要性的排序筛选出关键的基因或者蛋白质等。那么复杂网络中节点重要性的排序有什么算法又都有什么样的优缺点呢？

1.基于局部属性

基于网络局部属性的节点重要性排序指标主要考虑节点自身信息和其邻居信息, 这些指标计算简单, 时间复杂度低, 可以用于大型网络。例如通过综合考虑每个节点的邻居数和连接紧密度，对节点进行打分。

2.基于全局属性

基于网络全局属性的节点重要性排序指标主要考虑网络全局信息, 这些指标一般准确性比较高,但时间复杂度高, 不适用于大型网络。例如特征向量就是一种基于全局评估节点重要性的一个指标，它指的是网络邻接矩阵对应的最大特征值的特征向量。特征向量指标是从网络中节点的地位或声望角度考虑将单个节点的声望看成是所有其他节点声望的线性组合, 从而得到一个线性方程组. 该方程组的最大特征值所对应的特征向量就是各个节点的重要性。

3.基于网络位置属性的指标

Kitsak 等人于 2010 年首次提出了节点重要性依赖于其在整个网络中的位置的思想, 并且利用 K-核分解获得了节点重要性排序指标 (k-shell),该指标时间复杂度低, 适用于大型网络, 而且比度、介数更能准确识别在疾病传播中最有影响力的节点。K-核分解方法通过递归地移去网络中所有度值小于或等于 k 的节点. K-核的定义如下: 由集合推导出的子网络H = (C;E|C), 满足 C 中的任意节点 V , 其度值均大于 k 的最大子网络被称为K-核, 其中满足 K-核值等于 k 小于 k + 1 的那部分节点称为k-shell, 简称 Ks. Ks 分解示意图如图所示, 该网络被划分为 3 个不同的层。

4.基于随机游走的节点重要性排序

基于随机游走的节点重要性排序方法主要是基于网页之间的链接关系的网页排序技术, 由于网页之间的链接关系可以解释为网页之间的相互关联和相互支持, 从而判断出网页的重要程度，这类典型的方法有 PageRank,LeaderRank 和HITS 算法等，其中PageRank是我们经常使用的随机游走算法。

参考文献：

1、Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62128901 (inChinese) [任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901

2、 Kitsak M, Gallos L K, Havlin S, LiljerosF, Muchnik L, Stanley H E,Makse H A 2010 Nat. Phys. 6 888

3、Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl.Acad. Sci.USA 104 11150

4、Bryan K, Leise T 2006 SIAM Rev. 48 569
5、 Berkhin P 2005 Int. Math. 2 73
6、 Lu L Y, Zhang Y C, Yeung C H, Zhou T 2011 ¨ PLoS One 6 e21202
7、Kleinberg J M 1999 ACM 46 604

8、复杂网络中节点重要性排序的研究进展刘建国,任卓明,郭强,汪秉宏物理学报 Acta Phys. Sin. Vol. 62, No. 17(2013) 178901

往期「精彩内容」，点击回顾

DNA测序历史 | CircRNA数据库 | Epigenie表观综合 | 癌症定位

BWA介绍 | 源码安装R包 | CancerLocator | lme4 | 450K分析

乳腺癌异质性 | BS-Seq | 隐马模型 | Circos安装 | Circos画图

KEGG标记基因 | GDSC | Meta分析 | R线性回归和相关矩阵

精彩会议及课程，点击回顾

计算表观遗传学大数据前沿学术论坛会议记实

哈尔滨医科大学2017年全国生物信息学暑期学校

2017龙星课程系列（一）

2017龙星课程系列（二）
2017龙星课程系列（三）

2017龙星课程系列（四）

2017龙星课程系列（五）

更多相关文章

随机推荐