成为VIP
复杂网络基本概念(4)—最小生成树
01
引言
Introduction
前面我们介绍了小世界网络，无标度网络和社团结构，这些都是建立在连通图上去考虑的，通常会包含很多个环或回路。而本节针对不包含环的连通图(称为“树”)去展开讨论。本节主要给大家介绍一种特殊的“树”—最小生成树。
02
基本概念
Concept
生成树是指在连通图的基础上断掉一些环，最终形成的无环连通图。如图1，图(B)和图(C)是图(A)的生成树。
图 1 连通图(A)及其生成树(B)(C)
那么我们要怎么样从带环图变成生成树呢？大家很容易想到的是破环法，即将有环的边断掉，同时要保证整个图的连通性，根据某种规则可以得到生成树。另外一个是避环法，即从一个节点开始和其它节点建立连接，连接的过程中，需要有个判断语句最小生成树算法，即如果下一个连接的边会使得原本的图形成环，则舍弃该连接，继续跳转下一个节点去连接。
图 2 构造生成树的两种方法(破环法和避环法)
最小生成树定义为加权网络中连接所有节点的无环子图，该子图具有最小的连接成本。根据定义，我们知道，最小生成树中包含着原始网络中的主要骨架连接(或称为主干网)，同时也包含着Hub节点的一些信息。
这里简单提一下最小生成树被应用到脑疾病数据分析的一个由来：最小生成树被作为小世界网络的一种替代去刻画脑网络。从1998年到2010年左右，小世界网络被广泛地应用到神经科学的研究中，然而弊端也渐渐暴露，如通常小世界网络需要在一系列阈值(或网络密度)下去讨论，而阈值的选择并不固定。另外尽管全连接的加权网络能避免阈值的选择问题，但是小世界网络本身对于解释神经科学的一些现象提供不了丰富的信息。在国外如CJ Stam研究组逐渐将最小生成树应用到脑网络的研究中，他们从模拟数据和实际临床数据分析中也证明了最小生成树是一种比较好的替代方案。下面介绍一下最小生成树的构造算法和基本指标，及其在临床研究中的一些例子。
03
最小生成树构造算法
Algorithm
通常可以用Kruskal或Prim算法构造最小生成树。这里介绍一下Kruskal算法的核心步骤：(1) 将脑连接矩阵按连接强度从大到小排序，选择最大的连接强度(对应最小边距离)对应的节点和边加入到最小生成树的节点集和边集；(2) 从剩下的边中选择权值最大的加入最小生成树集合中；(3) 重复步骤(2)最小生成树算法，但是要注意在遍历的过程中，不能和已有的边形成环；(4) 经过有限次迭代步骤后，N*N的连接矩阵就被转换为N个节点和N-1条边的无向无环图，所有的连接距离加起来最小，即构造了一颗成本最小的树。
图 3 Kruskal算法生成最小生成树过程
04
基本指标
Basic Indexes
通常我们用叶子分数(leaf fraction, LF)和树的层级(tree hierarchy, TH)去刻画最小生成树的特性。在图论中，叶子节点表示度为1的节点，最小生成树的叶子节点数目取值从2到N-1(N为节点总数)。最小生成树有三种特殊的拓扑结构，即星型结构(star-like)、分层拓扑结构和线型结构(line-like)。其中，线型结构的树叶子节数目为2，星型结构的树叶子节点数目为N-1。为了让读者更好地理解这几种特殊的拓扑结构，我们用一张示意图来给出更直观的刻画(图4)。
图 4 三种特殊的最小生成树
而叶子分数则表示一颗树上叶子节点的比例。树的层级用来刻画最小生成树中大规模整合和中心节点的负载平衡能力的指标。它定义为如下：
其中，LN为最小生成树的叶子数量，BCmax是节点中最大的介数中心性。通常BC取值范围从0到1，介数中心性越大表示在网络中的重要性越大(即hub节点)。这里我们为什么不直接用介数中心性去度量节点的重要性呢？是因为越重要的节点其负载也越大，等hub节点被去除后，网络极易受到攻击(前面无标度网络有提到)，而人脑之前被证明是对抵抗网络攻击方面具有弹性。相比之下，树的层级能很好地平衡网络的负载和大规模整合能力。
当然刻画最小生成树的指标还有诸如树的直径，Kappa等等一些指标，本文由于篇幅有限，就不再展开，有兴趣的读者可以找一些相关文献去深入研究。
05
总结
Summary
本节介绍了最小生成树的基本概念由来以及构造算法和基本指标。目前在临床研究中也有一些最小生成树的例子。如有学者在对ECoG的最小生成树研究，发现生成树中的Hub节点对于定位病灶有一定帮助。另外在自闭症的脑网络中发现存在去中心化的网络模式。而在儿童发育过程中的最小生成树结果显示，随着儿童的年龄增长，网络拓扑结构由线状模式转变为分层模式，资源配置偏向更优。此外，CJ Stam研究组在癫痫的脑网络研究和帕金森患者的脑网络研究中，也揭示了最小生成树的潜在价值。后续具体能否应用到临床中解决实际问题，还有待更多研究人员去发掘。
参考文献
[1] 华中科技大学计算机学院《离散数学》课程PPT—第六章(图论).
[2] 普林斯顿大学计算机系：
[3] Achard, S. (2006). A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs.J. Neurosci.,26(1), 63.
[4] Tewarie, P. , Van Dellen, E. , Hillebrand, A. , & Stam, C. J. . (2015). The minimum spanning tree: an unbiased method for brain network analysis.Neuroimage,104, 177-188.
[5] Kruskal, & Joseph, B. . (1956). On the shortest spanning subtree of a graph and the traveling salesman problem.Proceedings of the American Mathematical Society,7(1), 48-48.
[6] Stam, C. J. , Tewarie, P. , Van Dellen, E. , Van Straaten, E. C. W. , Hillebrand, A. , & Van Mieghem, P. . (2014). The trees and the forest: characterization of complex brain networks with minimum spanning trees.International Journal of Psychophysiology,92(3), 129-138.
[7] Boersma, M. , Smit, D. J. A. , Boomsma, D. I. , De Geus, E. J. C. , Delemarre-Van, d. W. H. A. , & Stam, C. J. . (2013). Growing trees in child brains: graph theoretical analysis of electroencephalography-derived minimum spanning tree in 5- and 7-year-old children reflects brain maturation.Brain Connectivity,3(1), 50-60.
[8] Ortega, G. J. , Sola, R. G. , & Jesús Pastor. (2008). Complex network analysis of human ecog data.Neuroence Letters,447(2-3), 129-133.
[9] Otte, W. M. , Van Diessen, E. , Paul, S. , Ramaswamy, R. , Subramanyam Rallabandi, V. P. , & Stam, C. J. , et al. (2015). Aging alterations in whole-brain networks during adulthood mapped with the minimum spanning tree indices: the interplay of density, connectivity cost and life-time trajectory.Neuroimage,109, 171-189.
[10] He, W., Sowman, P. F., Brock, J., Etchell, A. C., Stam, C. J., & Hillebrand, A. (2018). Topological segregation of functional networks increases in developing brains.bioRxiv, 378562.
限时特惠：本站每日持续更新海量设计资源，一年会员只需29.9元，全站资源免费下载
站长微信：ziyuanshu688
htebazile
