【复杂网络】关于复杂网络中的动力学系统重构的文献资料整理

问题描述

现实世界中的各式复杂系统往往可以被抽象为一组单元，它们通过一个网络相连，并按照一定的动力学法则发生相互作用。传统的复杂系统研究思路是根据我们面对的实际现象，例如天气系统，我们人类科学家对其进行抽象，描述为一组网络动力学方程（例如Lorenz方程组），然后再对这一组方程（模型）进行模拟，从而产生一组时间序列，即可以反映这一系统在各个时间点的样子。

然而，这种研究方法存在着一些弊端。首先，现实中的系统五花八门、多种多样，如果所有系统都要靠有经验的科学家去建立抽象方程则不仅费时，而且强烈受限于建模者的经验；其次，随着技术的发展，我们已经积累了关于一个复杂系统运转的大量数据，特别是系统所产生的时间序列数据则更是多见，而传统的系统建模方法却很难与这样的微观数据相结合。

那么，我们的问题就是能否开发一种方法，它能够根据系统运行的时间序列数据，来自动构建系统运行的模型呢？这是一种逆向工程，也被称为网络动力学重构问题。

原始的重构问题是要同时推断出完整的动力学以及背后的网络结构。但是，在现实中，这种问题又有可能出现多个变种。例如，在有些情况下，我们并不需要知道整个系统的网络结构，所以，能够给出一套动力学方程，甚至于动力学方程的某种近似拟合即可，这就是动力学重构问题（Dynamics Reconstruction）；有的时候，我们只需要把我们感兴趣的动力系统的吸引子重构出来就好了，这就是吸引子重构问题（Attractor reconstruction），或叫做相空间重构问题（Phase space reconstruction）。

关于相空间重构，可以参考：

• 吸引子重构：http://www.scholarpedia.org/article/Attractor_reconstruction

或者参考wikipedia上的Taken theorem词条：

• Taken理论：https://en.wikipedia.org/wiki/Takens%27s_theorem

另外，有关一般的网络动力系统的重构问题，可参考的中文书有：

中文书：《数据驱动的复杂动态系统建模》

也可以参考中文综述：从数据到结构——动力学网络重构 [2019]张朝阳1,2, 陈阳3, 弭元元4, 胡岗5 点击获取原文

大数据是一笔越来越重要并不断快速增长的财富, 合理利用这一财富的关键是有效的分析手段.大 数据中一大类数据是由复杂网络代表的实际动力学系统产生的, 其中网络各个单元的输出数据可以测量, 但产生数据的网络结构却不为所知; 而了解这些网络结构对我们理解、预测和控制实际系统功能极为重要. 因此, 从分析网络数据出发揭示网络结构的重构问题就成为数学物理特别是统计物理以及一系列交叉领域 对网络研究的核心问题之一. 网络重构的重要性还来源于解决实际网络重构中所面对的各种困难的理论要求. 网络结构的复杂性、网络节点动力学的非线性、未知噪声对网络动力学演化数据的影响以及测量中有 效数据的缺失等都是在实际网络重构中要面对的常见且非常重要的困难. 本综述介绍并讨论了如何有效克 服这些困难的方法, 特别是通过数据扩张充分利用数据信息的方法, 针对不同的系统特征和重构任务选择 合适的关联量计算方法, 以及利用噪声帮助克服重构困难的方法等. 网络重构研究将逐步解决实际复杂系 统重构问题并引起复杂网络相关学者越来越多的关注和研究兴趣.

在另一些情况下，我们并不需要知道系统的演化动力学，而只要推断出哪些节点存在着连边即可，这就是典型的 网络重构问题（Network Reconstruction）。还有一种情况，我们可能已经具备一部分网络的结构，而还有一部分网络是未知的，甚至于这一部分未知网络的节点时间序列信息也是未知的，那么这种问题就称为 网络补全（Network Completion）。有的时候，我们明确地知道我们的网络或者动力学是属于几类之中的一类，那么根据时间序列数据推测出到底属于哪一种类别，这种问题叫做 系统辨识（System Identification）。

关于网络补全，这是一篇好文章：The Network Completion Problem: Inferring Missing Nodes and Edges in Networks

在一般的系统中，噪音随处可见，因此随机性不可避免。甚至在一些极端的情况下，系统本身就是一组相互耦合的随机变量，这些随机变量本身并不一定遵循固定的系统动力学，而它们的耦合和相互作用仅仅体现为一个联合概率分布，而我们希望根据系统的运行表现（往往也体现为时间序列），从而利用统计、贝叶斯推断（Bayesian Inference）、**概率图模型（Probabilistic Graphical Models）**等手段将这些变量的相互作用结构给推断出来，那么这种问题就叫做 网络推断（Network Inference）。

关于概率图模型，可参考这本书：

在统计学中，与此相关的另一个名词就叫因果推断（Causal Inference）。在概率图模型中，一条有向（在贝叶斯网上面）或无向（在马尔可夫网上面）的连边表示的是被连接的两个变量之间存在着直接联系。而所谓的因果关系首先必须是概率图一条普通的有向连边，其次，这条连边还需要满足进一步的要求，即如果将起点节点的状态更换（即反事实），会对终止节点造成显著影响（概率值改变）。如何在概率图的理论框架下根据数据来推断出因果连边则被称为因果推断，这在统计学、人工智能等学科中都是一个重要的任务。如果我们将一个网络动力学上的节点看作是随机变量，动力学规则则看作是条件概率或联合概率分布，那么动力学网络上的连边就是一种因果联系的连边。这样说，网络重构其实就是在做因果推断，这二者并无本质区别。但是，对于更一般的随机变量（不一定存在着动力学联系），则因果联系则必须借助反事实才能刻画清楚，从这个意义上来说，因果推断又会比网络重构具有更多的内涵。

关于因果推断，可参考 Judea Pearl 的两本书：
《为什么》

《因果》

有的时候，它们也都可以统称为网络推断。因为，所谓的推断就是指根据一部分已知信息，来推测未知信息，所以，网络重构与网络推断并没有太大的区别。

方法

尽管按照上述的内容不同领域的人定义了非常多不同的名词来概括一个网络动力学系统的重构问题，但是其实它们的本质都非常类似。

下面，我们在论述的过程中，将不再对这些不同的问题作区分。那么，如何解决这些问题呢？人们提出了各种各样的方法。目前来看，这些方法基本可以概括为两大类，即
（1）无模型（Model free）的通用类方法；
（2）基于特定模型（Model based）方法。

其中通用类方法是指我们可以将复杂网络动力学重构问题抽象成一套统一的数学或计算框架，因此，我们便可以对这一统一框架进行数学或计算机求解，而不必再去区分到底这一框架背后的具体领域问题是什么。因此，这里的统一框架可以用来解决基因调控网络重构，也可以解决神经网络重构等问题的。
而第二类特定方法则与其相反，它往往针对一类特定问题，例如给定网络上的传播动力学模型为 SIR 模型，然后在这一特定的模型上来去做网络结构的重构或推断。

下面，我们就分这两个类别来对文献做综述。

1. 通用方法

目前，人们开发出的通用方法也有很多，但是它们基本上可以划分为如下几类。我们将大体按照时间顺序进行罗列、综述。

1. 相关性方法

所谓的相关性方法就是只根据相关性来度量构建网络。例如，有多个时间序列，那么，可以计算任意两个时间序列的相关性，这就构成了这两个时间序列（节点）之间的一条连边。

比较早地运用相关性建立网络的文章可以参考这篇Science的文章：A Gene-Coexpression Network for Global Discovery of Conserved Genetic Modules，它讨论了3182种从人类、果蝇、蠕虫和酵母菌中通过测序得到的基因表达的数据所构建的相关性网络。其中，有22163种这样的共表达关系是在进化中被保留的，这意味着这些基因对传递了一种选择的优势，它们是彼此功能相关的。

A Gene-Coexpression Network for Global Discovery of Conserved Genetic Modules Joshua M. Stuart,Eran Segal,Daphne Koller.science (2003)

在经济和金融领域，相关性也是一种常用的方法，例如，文章"Hierarchical structure in financial markets"利用股票时间序列构建了一个加权网络，然后再利用最小生成树的方法，获得股票之间的层级结构信息。

Hierarchical structure in financial markets R. N. Mantegna.The European Physical Journal B - Condensed Matter and Complex Systems (2012)

除此之外，也有利用平面图的方式来将关联矩阵转换成网络的方式：

A tool for filtering information in complex systems M. Tumminello, T. Aste, T. Di Matteo.Proceedings National Academy of Sciences of United States of America (2005)

另外，当考虑到相互影响的延迟效应的时候，也可以考虑用两个时间序列的延迟相关性。比如，我们考虑雾霾从A地传播到B地，那么如果仅仅计算A(t)和B(t)这两个时间序列，它们的相关性也许并不大。但是，如果我们计算时间序列$A(t-\tau )$与$B(t)$，那么它们的相关性就会很高。这是因为雾霾的传播需要时间。

下面的文献就计算了这种延迟相关性，它的思路就是暴力搜索所有可能的$\tau$的取值，从而选择让两个时间最大的一种$\tau$，同时如果相关性足够大，就给出相应的连边：

Time-dependent cross-correlations between different stock returns: A directed network of influence L. Kullmann, J. Kerte ́sz, K. Kaski.Physical Review E (2002)

下面这篇文献给出了在快速变化噪声的情境下，如何根据时间延迟相关性来重构网络：

Reconstruction of dynamic networks with time-delayed interactions in the presence of fast-varying noises Z. Zhang, Y. Chen, Y. Mi.Physical Review E (2019)

这篇文章利用一种时间对齐的方法来重构短时间序列之中的因果联系：

Inner Composition Alignment for Inferring Directed Networks from Short Time Series S. Hempel, A. Koseska, J. Kurths.Physical Review Letters (2011)

2. 基于信息论的方法

与相关系数的方法相比，利用信息论提供的指标是一种更好的度量相关性的手段，因为相关系数只能反映两个变量是否线性相关，而这些信息论指标则能够应对更一般的情形。

比如，常用的一种方法是互信息（Mutual Information），它提供了相关性的另一种度量。
互信息定义为：$$I(X;Y)=\sum _{y\in Y}\sum _{x\in X}p(x,y)log(\frac{p(x,y)}{p(x)p(y)})$$
这篇文章用互信息的方法定义了全球气候网络：

The backbone of the climate network [2009]J. F. Donges, Y. Zou, N. Marwan, J. Kurths

另外一个常用于时间序列的方法是传递熵（Transfer Entropy），它能够刻画引入另一个变量对预测当前变量的贡献，因此它可以在一定程度上衡量因果联系。

在信息理论中，信息是根据不确定性定义的，这种不确定性是根据等式$H(X)=-{\sum }_{x\in X}p(x){\log }_{2}p(x)$中定义的概率来衡量的。回顾熵和互信息的概念，从它们来看，可以建立与方差和协方差的统计量度相似的关系。方差和熵是多样性的度量，而协方差和互信息建立了变量之间的关联程度。从这个类比来看，我们注意到与协方差或相关性相同，互信息不能暗示变量之间的因果关系，而是一种对称度量，揭示了相互的影响。

Variance and entropy are measures of diversity, while covariance and mutual information establish the degree of association between variables. From this analogy we notice that the same as covariance or correlation, mutual information can’t imply a cause-effect relationship between variables, instead it is a symmetrical measure that reveals mutual influence.

Schreiber（2000）试图通过变量的关联来解决方向性的概念，提出了传递熵的概念，将其定义为条件互信息。利用引入马尔可夫屏蔽的三个变量之间的延迟来调节互信息，因此，通过时间延迟来调节方向性。

实际上，可以使用条件熵之间的差来计算传递熵（Transfer Entropy）:

上图显示了我们感兴趣的信息流，即传递熵，它可以用数学公式表示为：$$T_{Y\to X}(t)=I(X_t:Y_{t-1}|X_{t-1})=H(X_t|X_{t-1})-H(X_t|X_{t-1},Y_{t-1})$$
将上述公式中熵的定义替换掉，得到：$$T_{Y\to X}(t)=\sum p(x_t,x_{t-1},y_{t-1})\ast {\log }_2\frac{p(x_t|x_{t-1},y_{t-1})}{p(x_t|x_{t-1})}$$
传递熵可以视为Granger Causality的非参数等效，其差异也适用于非线性分类变量。原则上，两者之间的互信息都是对称的（无方向性），但是实验引入的时间延迟可以建立方向性。

传递熵由于考虑的是变量间的信息量传递，而不需要假定变量间具有特定形式的关系，因此具有比Wiener-Granger因果性更好的适用性，尤其是对于非线性系统。

传递熵可以衡量两个时间序列之间的联系，也就是说如果把X的历史信息引入进来，会比只用Y的历史信息能更好地提供关于Y的未来信息。实际上我们马上会看到，这种思想和后面讲的格兰杰因果检验的思想异曲同工。可以证明，当把传递熵应用到线性向量自回归模型上的时候，传递熵就变成了格兰杰因果检验的度量。

这篇文章将传递熵用于神经回路的重构：

Model-Free Reconstruction of Excitatory Neuronal Connectivity from Calcium Imaging Signals [2012]O. Stetter, D. Battaglia, J. Soriano, T. Geisel

3. 格兰杰因果检验（Granger Causality）方法

格兰杰因果检验是最早提出的一种著名的因果推断方法，用于判断两个随机变量之间是否存在着因果箭头。它的基本思想是，如果引入了X变量对预测Y变量是否可以进行性能提升。更具体的，如果根据Y自己的历史和X的历史数据能够比仅根据Y自己的历史数据更好地预测Y的未来，那么就说X是Y的Granger因，Y是X的Granger果。

更严格的数学表达可以用下面的式子：$$\mathbb{P}[Y(t+1)\in A|\mathcal{T}(t)]\ne \mathbb{P}[Y(t+1)\in A|{\mathcal{T}}_{-X}(t)]$$
这是Granger提出Granger Causality Test的原始论文：

Investigating Causal Relations by Econometric Models and Cross-spectral Methods [1969]C. W. J. Granger

Wikipedia和Scholarpedia给出了关于此方法的历史、发展、局限的很好综述：

格兰杰因果检验wikipedia页面：https://en.wikipedia.org/wiki/Granger_causality
Scholarpedia上的介绍： http://www.scholarpedia.org/article/Granger_causality

下面这篇文章将格兰杰因果检验方法应用于气候系统中

Inferring causation from time series in Earth system sciencesJakob Runge, Sebastian Bathiany, Erik Bollt.et al.Nature Communications（2019）

这篇文章综述了此方法失效的情形：

A review of the Granger-causality fallacy [2015]M. Maziarz

目前，该方法已被应用于大量的经济、社会、神经科学领域中。

另外，下面这篇文章很好地展示了格兰杰因果方法可以用于非线性系统：

Causal and Structural Connectivity of Pulse-Coupled Nonlinear Networks [2013]D. Zhou, Y. Xiao, Y. Zhang, Z. Xu, D. Cai

4. 相空间重构方法

当我们利用时间序列数据重构吸引子通常都是根据Taken定理，可参考：

Detecting strange attractors in turbulence [2006]F. Takens

用Taken定理做重构，主要的想法就是利用已有的时间序列数据，来直接构成原始的相空间中的轨迹。例如，我们的动力系统是一个三维的系统，$\frac{d(x,y,z)}{dt}=f(x(t),y(t),z(t))$，并假设我们仅能够获得一个变量的时间序列数据$x(1),x(2),...,x(t),..$。那么，利用这一个时间序列，我们就能够重构出原始的三维动力学在相空间中的轨迹。基本思想就是利用一个三阶延迟的序列，比如$s(t)=(x(t-1),x(t-2),x(t-3)),s(t-1)=(x(t-4),x(t-5),x(t-6)),...$。这个新序列$s(t)$就是一个三维空间中的轨迹，那么它在三维空间中的轨迹将与原始的三维动力学相空间中的轨迹同胚（拓扑等价）。
如图展示了洛伦兹吸引子的重构：
洛伦兹吸引子产生的时间序列
利用2阶延迟的时间序列重构洛伦兹吸引子

关于这一重构方法很好地概括在下面的文章中:

Geometry from a Time SeriesN. H. Packard, J. P. Crutchfield, J. D. Farmer.et al.Physical Review Letters（1980）

关于如何选定延迟时间，可以参考：

Proper choice of the time delay for the analysis of chaotic time seriesW.Liebert, H.G.SchusterPhysics Letters A（1989）

关于如何选择最好的维度，可以参考：

EmbedologyT. D. Sauer, J. A. Yorke, M. CasdagliJournal of Statistical Physics（1991）

如何用重构的吸引子来进行时间序列的预测，可以参考：

Predicting chaotic time seriesJ. D. Farmer, J. J. SidorowichPhysical Review Letters（1987）

这篇论文讨论了一种利用混沌自同步来进行参数估计的方法：

Estimating Model Parameters from Time Series by AutosynchronizationU. ParlitzPhysical Review Letters（1996）

5. 收敛交叉映射(Convergent Cross Mapping, CCM)方法

所谓的CCM是指收敛交叉映射（Convergent Cross Mapping）方法，它来源于相空间重构理论。只不过，CCM的目标并非重构动力学或吸引子，而是希望找到变量之间的“CCM因果联系”。

CCM方法指出，如果一个事件A是B的因，并不意味着A一定会在B之前发生。一个著名的例子就是A=鸡打鸣和B=太阳升起。显然，我们每天都会观测到A会在B发生前发生，那么，我们可以说A是B的因吗？显然不行。因为，我们都知道，太阳升起才是让公鸡打鸣的原因，只不过由于常年的学习进化，公鸡已经学会了预测太阳升起这一事件，于是公鸡可以在太阳升起前打鸣。CCM方法声称，如果用该方法分析公鸡打鸣和太阳升起这样的时间序列，它可以准确地判别出正确的因果关系。

它的指导思想来源于相空间重构的Taken定理。我们知道，一个两变量的动力系统可以写成$\frac{dx}{dt}=f(x,y)$, $\frac{dy}{dt}=g(x,y)$。它们共同构成了一个动力学吸引子记做M。Taken定理说，一个吸引子在任何一个子空间中的投影都有可能重构出吸引子本身。于是，我们可以选择两个特殊的投影，一个是在x变量的子空间上投影，另一个是在y变量的子空间上。既然，这两个空间都是吸引子M的投影，那么x和y这两个子空间中的时间序列就必然会存在着一定的联系。

下面我们考虑时间延迟的时间序列重构。假设x的时间延迟序列可以重构出一个相空间$M_X$，y的时间延迟序列可以重构出相空间$M_y$，那么对于任意一个时刻，这两个相空间流形$M_x,M_y$上的对应点附近的邻域必然存在着很强的相关性，因为它们都来自M上的同一个邻域。如下图：

正是基于这一性质，CCM就可以通过$M_x$和$M_y$邻域的相关性来计算此二者是否有因果联系。具体的方法可以参考这篇Science文章：

Detecting Causality in Complex EcosystemsGeorge Sugihara, Robert May, Hao Ye.et al.（2012）

后续也有不少工作进行了改进，例如，下面这篇文章就给出了考虑到延迟效应之后的因果连边探测：

Detection of time delays and directional interactions based on time series from complex dynamical systemsH. Ma, S. Leng, C. Tao.et al.Physical Review E（2017）

也有学者指出CCM原始方法中的弊端，以及一些失败的case，并提出了改进方法：

Convergent Cross-Mapping and Pairwise Asymmetric InferenceJ. M. McCracken, R. S. WeigelPhysical Review E（2014）

6. 线性化方程求解

这一思路的核心在于将一个非线性的动力学方程组转化为一个线性系统，从而来进行重构。

具体地，假设系统的非线性动力系统为：$\frac{dx}{dt}=f(x(t))+r(t)$，其中$x$是多维变量，即多个节点，$A$是节点之间的相互作用矩阵，$f$是非线性函数，$r(t)$为一个高斯白噪声过程。那么，我们可以先把这个动力学函数$f$做简化，即利用泰勒展开，或者在任何一组函数基上做展开，把动力系统变为一个线性动力系统，即$\frac{dx}{dt}=Ax+r(t)$这样的形式，其中$A$是各个线性项的级数展开的系数，也就是$x$中各个变量相互作用的网络。

于是，我们的问题就是，如果假设这个系统就是这样一个线性系统，那么我们如何根据其生成的时间序列而将这个网络$A$给重构出来呢？答案就在于可以直接求得解析解。利用白噪声的性质，我们可以求各个不同变量的时间序列的相关性，从这些相关性度量就可以显式地求解出$A$。

这一方法可以有很多推广，包括非线性系统和包括缺失节点的网络补全问题的求解。关于这一方法，下文给出了很精彩的综述：

从数据到结构——动力学网络重构张朝阳, 陈阳, 弭元元.et al.《中国科学》杂志社（2019）

当然，我们也可以不用解析求解，而是直接运用线性回归的方式来对方程组进行求解，从而解决网络的重构问题。例如，Nature Communications在2017年发表的这篇文章就是这么干的：

Model-free inference of direct network interactions from nonlinear collective dynamicsJose Casadiego,Mor Nitzan,Sarah Hallerberg.et al.nature communications（2017）

这篇文章有比较清晰的例子：

Dynamical networks reconstructed from time seriesZ. LevnajićarXiv（2012）

这篇文章提出了一种可以应付数据量小、稀疏网络的算法：

Reconstructing the topology of sparsely connected dynamical networksD. Napoletani, T. D. SauerPhysical Review E（2008）

7. 压缩感知（Compress Sensing）

另一个与方法6非常类似的思路就是 压缩感知方法。其实，该方法同样也是要先将系统动力学法则$f$简化成一组线性的函数，然后，在求解方式上，可以使用更加先进的压缩感知算法。

压缩感知，其实是发展自信号处理领域的一套方法，它专门解决一个欠定（undetermined）线性系统的求解问题，简单讲，它可以描述乘如下矩阵的求解：

压缩感知方法示意图

其中$x$是需要重构的原始信号，$D$是一个已知的观测矩阵，$y$则是我们能够观测到的信号。注意，在很多系统中，$x$是一个非常高维的稀疏向量（也就是$x$中存在大量的0元素）。由于x的维度远远高于y的维度，这就使得该系统欠定，也就是无法给出方程的解，因为未知数的个数远大于方程组的方程个数。但是，如果我们充分利用x是稀疏向量这个条件，那么这一方程是可以利用一定的优化算法进行求解的。例如，我们可以定义一个目标函数为$|y-Dx|$的值，并将它最小化，同时考虑稀疏性约束，这样就可以求解这个问题了。

在信号处理领域，这样的稀疏解是非常接近原始的真实解的。因此，可以利用远小于奈奎斯特采样频率（Nyquist frequency）的方式对原信号采样，然后用压缩感知方法对原信号进行重构了。

那么，如何将压缩感知方法应用于网络重构中呢？重要的一步就是要把一个动力学系统转化成压缩感知那样的欠定线性系统。具体来讲，未知的邻接矩阵，以及一些耦合在动力学中的参数，这些就构成了原始的未知信号$x$，而动力学规则等就构成了观测矩阵$D$，那么可观测到的时间序列就构成了那个观测信号$y$。于是，要想利用压缩感知算法，必须要求重构的网络$x$具有稀疏性，这样就可以利用压缩感知算法了。

关于压缩感知方法如何用于网络重构，可以参考北师大系统科学学院王文旭老师发表在Physics Reports上面的一篇综述文章：

Data based identification and prediction of nonlinear and complex dynamical systems [2016]W.-X. Wang,Y.-C. Lai, Celso Grebogi

通过之前类似的方法将非线性方程组转化为线性，然后进行重构：

Time-series–based prediction of complex oscillator networks via compressive sensing [2011]W.-X. Wang, R. Yang, Y.-C. Lai, V. Kovanis, M. A. F. Harrison

另外，除了将原始的非线性动力学方程线性化以外，还可以通过一些技巧将问题转化为压缩感知算法可以处理的线性化方式。它不仅可以重构出传播网络，还可以定位传播源头。例如王文旭组的另一篇文章：

Reconstructing propagation networks with natural diversity and identifying hidden sourcesZhesi Shen,Wen-Xu Wang,Ying Fan.et al.nature communications（2014）

这篇文章用压缩感知重构混沌吸引子：

Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing [2011]W.X. Wang, R.Yang, Y.-C. Lai, V. Kovanis, C. Grebogi

这篇则通过博弈行为数据重构了背后的博弈网络：

Network Reconstruction Based on Evolutionary-Game Data via Compressive Sensing [2011]W.-X. Wang, Y.-C. Lai, C. Grebogi, J. Ye

下面这篇文章指出，如果动力学系统中存在着噪声，有可能提升压缩感知算法的重构能力：

Reconstruction of Complex Network based on the Noise via QR Decomposition and Compressed Sensing [2017]Lixiang Li,Dafei Xu,Haipeng Peng,Jürgen Kurths,Yixian Yang

另外，这篇文章将压缩感知方法扩充到了时间可变的非线性动力学系统中：

Forecasting the future: Is it possible for adiabatically time-varying nonlinear dynamical systems? [2012]R. Yang, Y.-C. Lai, C. Grebogi

这篇PNAS文章对压缩感知法做了很好的概括和总结：

Discovering governing equations from data by sparse identification of nonlinear dynamical systems S. L. Brunton, J. L. Proctor, J. N. Kutz.Proceedings of National Academy of Sciences of U.S.A. (2016)

8. 驱动响应方法

前面讲述的方法大多数都是被动的接受数据，并进行模型的构建。另外一种方法则是可以主动地干预系统，并根据系统的反馈来重构网络或者动力学。

这一方法的基本思路是，假设系统演化达到稳态的时候，给其中某一个节点加上一个冲击信号（一个delta分布函数）。然后，就可以将整个系统的演化方程在稳态附近进行级数展开，从而将各个变量之间的相互影响关系推测出来。这是发表在Science advance上的一篇用驱动响应方式进行网络重构的文章：

Revealing physical interaction networks from statistics of collective dynamics M. Nitzan, J. Casadiego, M. Timme.Science Advances (2017)

这篇文章的第一部分对驱动响应方法进行了综述:

Revealing networks from dynamics: an introduction Marc Timme, Jose Casadiego.Journal of Physics A: Mathematical and Theoretical (2014)

然而上面的很多例子都需要实现给定系统演化的动力学法则而重构相互作用网络，所以严格讲它应该归类于基于模型（Model based）的重构方法。然而，这一点并不是必须的，例如下文最后提供的例子：

从数据到结构——动力学网络重构 [2019]张朝阳, 陈阳, 弭元元, 胡岗*

该文还指出，当干预节点之外的其他节点是不可观测的情况下，我们仍然可以重构出我们感兴趣的部分网络。

9. 概率图模型

概率图模型（Probabilistic Graphical Models），包括贝叶斯网络（Bayesian Network）以及马尔可夫网络（Markov Network），它们是一种集推理、学习于一体的模型。它们通过将待研究的系统看作是一个相互作用的网络，其中每一个节点都是一个随机变量。这些随机变量的动力学完全由它们的联合概率分布所决定，而整个概率图模型所表达的恰恰就是对这种联合概率分布的一种分解方法。连边就表示这两个节点随机变量彼此有直接的联系。

尽管概率图模型通常并非是表达动态系统的，但也可以将动力系统与概率图模型做一个比较。整个系统的“动力学”就体现为整个概率图的联合概率分布。“动力学规则”就是节点概率分布之间的某种制约。联合概率给定，它就可以稳定地输出时间序列数据，根据这些时间序列数据，即可重构原始的网络。

以贝叶斯网为例，如下图所示：

图中每个节点旁边的表都是一个条件概率表，表示的是该节点的父节点在取定某一个值的条件下，该节点取定某一个值的概率。这些条件概率就相当于是“动力学规则”。假设在 t 时刻，三个节点的状态分别为 Rain=T, Sprinkler=F, Grass=T，则根据概率规则表，在 t+1 时刻，Rain有可能取 F，Sprinkler有可能取 F，而Grass有可能取 T。

在这样的网络中，根据观测到的时间序列推断出这些变量背后的条件概率表，就相当于是在学习这个系统的动力学。另外，根据数据也可以推断背后的网络链接，这在贝叶斯网中被称为"结构学习”（Structure Learning）"。

另外，这里有一篇关于贝叶斯网学习的综述：

A guide to the literature on learning probabilistic networks from data W. Buntine.IEEE Transactions on knowledge and data engineering (1996)

下面这篇文章利用贝叶斯网络的结构学习来重构秀丽线虫的神经网络：

Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans Hexuan Liu, Jimin Kim and Eli Shlizerman.Philosophical Transactions of the Royal Society B (2018)

10. 因果网络

如果系统存在着确定性的演化方程，并且如果某个变量$x$出现在另一个变量$y$的演化方程中，那么就认为$x$构成了$y$的一个原因，也就是说，$x$和$y$之间存在着因果联系。然而，当我们考虑的系统是随机的不确定系统的时候，这种联系则没有那么显然。

在概率图模型的框架下，人们将因果联系赋予了更多的内涵。例如，如果随机变量$X$构成了随机变量$Y$的原因就不仅要求，在$X$的条件下$Y$的概率更高，而且还要求在主动对$X$进行干预的条件下，能够让$Y$出现的概率出现显著变化。

下面这两篇文章综述了从时间序列数据重构因果网络的方法：

Causal network reconstruction from time series: From theoretical assumptions to practical estimation Runge J…Chaos: An Interdisciplinary Journal of Nonlinear Science (2018)
A survey of learning causality with data: Problems and methods Guo, R, Cheng.et al…arXiv preprint arXiv:1809.09337 (2018)

下面这篇Science Advance上的文章介绍了一种通过延迟机制寻找因果关系的做法：

Detecting and quantifying causal associations in large nonlinear time series datasets Runge, J, Nowack.et al…Science Advances (2019)

下面这篇介绍了因果推断方法在生态网络中的应用：

CAUSAL LINK ESTIMATION UNDER HIDDEN CONFOUNDING IN ECOLOGICAL TIME SERIES Trifunov V.T., Shadaydeh M., Runge J…et al…9th International Workshop on Climate Infomatics (2019)

11. 演化计算方法

本质上讲，寻求系统背后的相互作用网络结构以及动力学可以看作是在所有可能的网络结构和动力学空间中找到最能够解释数据的方案，因此，这类问题也可以被看作是一种搜索问题。演化算法是解决搜索问题的一种强有力的方法，它的好处就是通用性。

下面这篇PNAS文章就用遗传编程的手段来解决动力系统的重构问题：

Automated reverse engineering of nonlinear dynamical systems J. Bongard, H. Lipson.Proceedings of the National Academy of Sciences of U.S.A. (2007)

另外，下面这篇文章则用演化计算的手段寻找合适的网络结构，从而像神经网络一样来拟合任意的从输入到输出的映射。一般的神经网络是通过优化网络的权重参数，从而完成从输入到输出的拟合的，而该文章中将网络节点的动力学及参数固定，而优化网络的结构以完成类似的任务。

Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning Rise Ooi,Chao-Han Huck Yang,Pin-Yu Chen.arXiv:1811.05592 (2018)

12. 图神经网络方法

上面的各类方法虽然都能很好地工作，但在一般情况下都并不能给出比较高的预测精度。特别是，当我们考虑的动力学过程非常复杂的时候，由于这些模型本身的简单性，所以不能够把握具有复杂模式的数据。而神经网络则恰恰最擅长于捕捉复杂的相互作用关系，并给出较高准确度的预测。然而，传统的机器学习算法，特别是神经网络，往往无法给出很好的解释。特别是，神经网络各个神经元之间的联系并不能反映各个变量之间的相互作用关系。

图神经网络（Graph Neural Network）或简称图网络（Graph Network）是一种近年来新提出的一种神经网络架构，可以用来学习一个图上的动力学，也可以学习图本身的结构，它相对于传统方法来说具有很高的预测准确度。而相对于普通的神经网络来说，它多出了一个先验的图结构，这种图就能很好地反映变量之间的相互作用模式，要学习的仅仅是节点上的动力学，因此，这种模型或方法具有很好的可解释性。有关图神经网络的综述，可以参考：

Relational inductive biases, deep learning, and graph networks Peter W. Battaglia,Jessica B. Hamrick,Victor Bapst (2018)

在这篇文章中，作者将事先给定的网络结构称为关系归纳偏见（Relational Inductive Bias）。这相当于是说，建模者可以将自己对问题的先验知识放到图结构之中，从而和强大的基于神经网络的机器学习算法耦合到一起。

当系统背后的网络已知的时候，可以学习网络上的动力学。也就是学习从$x_t$到$x_{t+1}$的映射。基本思路是，我们首先将$x_t$作为节点的输入特征，将$x_{t+1}$看作是我们要学习的target。利用图网络将$x_t$转换为对$x_{t+1}$的预测，这个转换过程一般可以分为从节点到连边，再从连边汇集到节点这样的过程，如下图所示：

图神经网络解决动力学预测的架构

下面这篇文章是利用图神经网络解决动力学学习的一个经典论文：

Graph networks as learnable physics engines for inference and control Alvaro Sanchez-Gonzalez,Nicolas Heess,Jost Tobias Springenberg (2018)

还可以根据已知的物理约束，再来学习背后的动力学：

Differentiable Physics-informed Graph Networks Sungyong Seo,Yan Liu.arXiv:1902.02950 (2019)

这类推断动力学的工作很多，并已经应到了很多实际问题中，例如，用用图神经网络的方法来：

预测交通流：
GMAN: A Graph Multi-Attention Network for Traffic Prediction Chuanpan Zheng, Xiaoliang Fan, Cheng Wang (2019)

预测网约车数量：
Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting[C]// Geng, X, Li.Proceedings of the AAAI Conference on Artificial Intelligence (2019)

雾霾预报：
PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting Shuo Wang,Yanran Li,Jiang Zhang.arXiv:2002.12898 (2020)

但是，上面介绍的工作存在着一个最大的弊端，就是图结构需要实现给定的，但在很多时候，网络结构都不能事先给定。能不能利用图神经网络直接将网络结构和动力学一起重构呢？下面的这篇Neural Relational Inference（NRI）的文章就对这一问题进行了解决。

Neural Relational Inference for Interacting Systems Thomas Kipf,Ethan Fetaya,Kuan-Chieh Wang.arXiv:1802.04687, 2018. (2018)

它将变分自编码器架构进行了改造，利用编码器生成推断的图结构，解码器则利用图结构来推断动力学，其架构如下图所示：
NRI架构示意图

然而，NRI的系统比较庞大，从而导致训练效果也不是很好，它只能在比较小规模的网络上。可以对NRI架构做了改动，将编码器改造成了一个轻量级的网络生成器，并用Gumbel softmax机制生成网络，模型称为Gumbel Graph Network（简称：GGN）

A general deep learning framework for network reconstruction and dynamics learning Zhang Zhang, Yi Zhao, Jing Liu (2019)

GGN架构如下图所示，该架构可以在离散、连续以及布尔等不同类型的动力学网络重构中都取得很好的效果。

另外，还可以将不同的约束，包括网络稀疏性、度分布等特性引入到图神经网络的框架中，从而更好地帮助我们对系统进行重构，例如：

Structure-informed Graph Auto-encoder for Relational Inference Li, Y, Meng. ICML 2019 Workshop on Learning and Reasoning with Graph-Structured Data (2019)

下面两篇文章则用类似的架构在具有部分观测节点的情况下进行学习和预测：

Neural Relational Inference with Fast Modular Meta-learning Ferran Alet, Erica Weng, Tomás Lozano Pérez (2019)
Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network Mengyuan Chen,Jiang Zhang,Zhang Zhang (2020)

下面这篇则讨论了在具有部分观测节点下进行动力学预测的问题：

Learning Dynamical Systems from Partial Observations Ibrahim Ayed,Emmanuel de Bézenac,Arthur Pajot.arXiv:1902.11136 (2019)

有了这种网络结构的学习，人们不仅能够进行动力学网络重构，也能够改进诸如节点分类等传统的图网络机器学习任务。例如：

Learning discrete structures for graph neural networks Franceschi, L, Niepert.arXiv preprint arXiv:1903.11960 (2019)

图神经网络的方法也可以把握处于变化之中的网络结构。例如，下面这篇文章就利用Transformer中的自注意力机制来把握动态连边，并针对元胞自动机、鸟群模型等经典的复杂系统模型进行重构。

Towards Automated Statistical Physics : Data-driven Modeling of Complex Systems with Deep Learning Seungwoong Ha,Hawoong Jeong (2020)

2. 基于模型的方法

上面介绍的各种方法都是通用的，它们并不依赖于待建模系统的具体模型。下面介绍的一系列方法则需要利用系统的具体模型，并在给定模型的基础上来对网络或动力学进行重构。

例如，下面这篇文章根据网络传播模型来进行网络结构的推断：

A statistical inference approach to structural reconstruction of complex networks from binary time series C. Ma, H.-S. Chen, Y.-C. Lai.Physical Review E (2018)

下面这篇文章基于SIS模型重构多重网络：

Data Based Reconstruction of Duplex Networks C. Ma , H.-S. Chen, X. Li.SIAM Journal on Applied Dynamical Systems (2019)

下面这篇文章则通过ISING模型来重构符号网络：

Reconstructing signed networks via Ising dynamics B.B. Xiang, C. Ma, H.S. Chen.Chaos (2018)

下面的文章在线性化假设的前提下利用贝叶斯方法重构生物网络，并给出通用的解法：

Network Inference and Biological Dynamics C.J. Oates, S. Mukherjee.Annual Applied Statistics (2012)

下面这篇文章利用传播模型和贝叶斯方法进行网络补全的研究：

Hidden network reconstruction from information diffusion F. W. Crawford.18th International Conference on Information Fusion (2015)

通常的网络重构工作都需要利用节点的时间序列来重构整个网络结构，而下面的这篇文章讨论了一种仅根据节点的状态，而不需要用到时间序列数据就可以重构网络的方法：

Reconstructing complex networks without time series C. Ma, H.-F. Zhang, Y.-C. Lai.Physical Review E (2017)

下面这篇文章在一种脉冲耦合协振子模型的基础上来讨论网络的重构。该方法可以根据脉冲类型的信号，从而重建出原始的网络结构：

Reconstructing networks of pulse-coupled oscillators from spike trains Rosenblum, M…Physical Review E (2017)

应用

动力系统、网络重构是属于一种跨学科的研究领域，它的方法自然也可以扩展到各个学科之中。下面，分几个领域来分别介绍这些应用的情况。

1. 经济领域

网络重构在经济、金融领域的应用可以算一个经典的场景，然而，这部分的研究大多关注的是网络的应用，包括社区划分、风险扩散、风险预警等，而并不太关心重构网络的质量。

下面这篇文章对经济、金融领域中的网络重构工作进行了很好的综述，然而，这篇文章讨论的网络重构与上面讨论的各类网络重构方法具有很大的区别，它并没有涉及时间序列和动力学，而更多地是在利用最大熵方法来对网络进行重构。

Reconstruction methods for networks: The case of economic and financial systems Squartini T, Caldarelli G, Cimini G

下面这篇文章讨论了在重构的网络上进行风险传播的可能情景：

Spread of risk across financial markets: better to invest in the peripheries F. Pozzi, T. Di Matteo, T. Aste.Scientific Reports (2013)

下面这篇文章首先利用最大熵这种密集联系的网络重构方法重构了金融机构之间的网络，并在这个网络之上探讨了系统性风险等问题：

Systemic risk analysis on reconstructed economic and financial networks[J] Cimini, G, Squartini.Scientific reports (2015)

下面这篇文章运用压缩感知方法构建了银行间网络：

Estimating global bank network connectedness M. Demirer, F. X. Diebold, L. Liu.Journal of Applied Econometrics (2017)

2. 基因调控网络和生物学网络

蛋白质（Protein）是生命活动的主要执行单位,，不同的蛋白质参与不同的生化过程。生物体内执行不同功能的细胞会表达不同种类的蛋白质。蛋白质的表达受到转录因子（Transcription factors, TF）特异性地调控。转录因子通过互相调节，以及调控下游的效应基因，进而构成基因调控网络（Gene Regulatory Network，GRN）。

基因调控网络在细胞发育，细胞分化状态确定方面发挥着重要作用。重构基因调控网络是揭示生物体复杂性的关键一步，也是研究的热点。重构基因调控网络可以通过实验的方法，例如探测转录因子在基因组上的结合位点来实现。同时，也可以通过计算的方法从基因表达数据中推测基因调控网络的结构。常用的重构算法通常利用基因表达之间相关性，互信息，以及高斯图模型，回归模型，贝叶斯模型等等来推断网络的结构。

很多方法只是针对调控网络结构的重建，并不涉及到基因表达变化的动力学（Dynamics）。了解基因表达变化的动力学，可以预测细胞状态地转变，更好地刻画细胞状态转换轨迹(Cell Trajectory)，进一步为合成生物学（Synthetic Biology）的发展，如基因回路（Gene Circuit）设计，提供帮助。这里，我们开发了一种新的网络重构和动力学预测的方法。

下面这篇发表在Nature Methods上面的一篇对基因调控网络进行重构的文章，系统地比较了不同基因重构的方法，并综合讨论了评价重构质量的指标。在这篇文章中，作者专门提出了一种能够模拟基因调控网络中的布尔动力学的微分动力学模型：BoolODE: converting Boolean models to ODEs，然后用它作为试金石来评判、比较不同的基因网络重构算法。与此同时，它还生成了一系列数据集，方便作为Benchmark来使用。

Benchmarking algorithms for gene regulatory network inference from single-cell transcriptomic data Pratapa, A, Jalihal.Nature Methods (2020)

下面这篇也是发表在Nature Methods上的一个较早的文章。作者则比较好地对各种重构方法进行了归类和比较。特别是，作者详细地分析了重构网络中的各种模体（Motif），以及观察不同重构方法更倾向于实现何种模拟。

Wisdom of crowds for robust gene network inference[J] Marbach, D, Costello.Nature methods (2012)

3. 脑网络

人脑是一个典型的由大量相互作用单元构成的复杂系统，通过观察大脑的部分运行数据来重构大脑中的网络则是帮助我们理解大脑结构的重要一环。

当我们谈及脑网络的链接的时候，实际上会涉及几种不同的链接概念，它们分别是结构链接（structual connectivity）、功能链接（functional connectivity）和有效链接（effective connectivity）。这一概念最早来源于**功能神经成像（functional neuroimaging）**技术中，但也同样可以用于其它层级组织的神经网络之中。

• 结构链接：通常是指物理上实际存在的或能够链接一组神经元或其它神经要素的突触链接，以及这些链接中包含的相关生物物理属性。
• 功能链接：通常情况下则是一个统计意义上的概念。一般的，功能链接能够捕捉到神经单元在统计意义上的相互关联。
• 有效链接：则可以看作是结构与功能链接的并集，它描述了一个神经单元到另一个单元的直接效应。原则上，我们可以用一些因果推断的方式推测出这样的有效链接，例如前面介绍的格兰杰因果检验以及传递熵等方法。

关于脑网络链接的更详细讨论，可以参考：

Scholarpedia上的词条Brain_connectivity： http://www.scholarpedia.org/article/Brain_connectivity

下面这篇文章对脑功能网络进行了综述，包括如何从功能成像中构建出这一网络，以及这一网络的拓扑性质等：

Exploring the brain network: a review on resting-state fMRI functional connectivity Van Den Heuvel M P, Pol H E H…European neuro psycho pharmacology (2010)

下面这篇文章利用贝叶斯网络的方法重构秀丽线虫的功能脑网络：

Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans Hexuan Liu, Jimin Kim and Eli Shlizerman.Philosophical Transactions of the Royal Society B (2018)

也有不少文献聚焦在大脑有效链接的重构上。例如，下面这篇文章直接根据脑影像信号（fMRI），利用格兰杰因果检验技术重构出大脑内部相互作用的网络：

Mapping directed influence over the brain using Granger causality and fMRI Roebroeck, A, Formisano.Neuroimage (2005)

下面这篇文章利用Transfer entropy的方法讨论了神经系统中的有效连接：

Transfer entropy—a model-free measure of effective connectivity for the neurosciences Vicente R., Wibral M., Lindner M…Journal of Computational Neural Science (2011)

下面这篇文章利用发放的时间序列重构神经网络：

Reconstruction of a neural network from a time series of firing rates Pikovsky, A…Physical Review E (2016)

4. 气候与天气系统

随着全球变暖的趋势进一步加强，气候系统已经成为了人们普遍关注的焦点。理解气候运作背后的基本规律是处理全球变暖问题的重要环节。利用动力学与网络重构技术来分析大规模气候系统的时间序列数据则有望捕捉到气候系统的相互影像规律。

与真实世界中的网络，气候网络的节点并非实体，而是气象观测格点，因此，它可以因空间分辨率而变化。两个节点如果它们的时间序列具有一定的统计相似性，就把它们链接上边。可以根据气候网络来讨论气候系统在不同空间、时间尺度上的动力学特性。

最早用复杂网络研究气候系统的是 Tsonis 等人：

The architecture of the climate network Tsonis, A.A., Roebber.Physica A: Statistical Mechanics and Its Applications (2004)

之后，Havlin等人利用交叉相关，并考虑到了不同时间的延迟等手段构建了更为精确的气候网络模型：

Climate Networks around the Globe are Significantly Affected by El Niño Yamasaki, K., Gozolchiani.Physical Review Letters (2008)
Emergence of El Niño as an Autonomous Component in the Climate Network Gozolchiani, A., Havlin.Physical Review Letters (2011)

利用气候网络的性质，可以讨论气候系统中的Rossby波现象：

Dominant Imprint of Rossby Waves in the Climate Network Wang, Shlomo.Physical Review Letters (2013)

下面这篇文章利用相关网络的方法分析了气候系统的骨架：

The backbone of the climate network J. F. Donges, Y. Zou, N. Marwan.Europhysics Letters (2009)

有趣的是，气候网络存在着长生关联的现象，也就是地理距离相隔很远的两个观测掉可能存在着比较强的相关性，这在气候网络中称为“超距链接路径”（Teleconnection Paths）。下面这篇就讨论了如何通过气候网络的联系探测这种超距链接路径：

Detecting and quantifying causal associations in large nonlinear time series datasets Jakob Runge,Peer Nowack, Marlene Kretschmer.Science Advances (2019)

更进一步，在获得了相互作用网络之后，我们还希望对气候系统的运行进行预测。下面这篇文章就针对厄尔尼诺现象进行了早期的预警：

Very early warning of next El Nino Ludescher, J., Gozolchiani.Proceedings of the National Academy of Sciences (2014)

利用图神经网络等机器学习技术，我们还可以做到更加微观而精准的预测，下面这篇文章利用图神经网络的方法在中国东部地区跨城市界别上，尝试对PM2.5浓度值进行预测：

PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting Shuo Wang,Yanran Li,Jiang Zhang.arXiv:2002.12898 (2020)

总之，将网络重构的技术运用在气候领域尚是一个新兴的领域。尽管目前绝大部分的工作仍然是利用相关性来构建网络的研究偏多，但我们期待着看到更多这方面的应用。

总结

本文尝试针对目前比较常见的动力学和网络重构的方法进行了梳理和概括，并针对几个常见的应用领域进行了介绍。

随着大数据的发展和计算能力的进一步提升，这类重构方法将会得到更进一步的发展。

这一领域的一个终极发展目标则是对复杂系统的自动建模。这样，我们在这些算法的帮助下对复杂系统的理解有可能完成巨大的飞跃。

参考资料

[1] 张江：怎样搞定复杂系统动力学重构？百篇资料一站获取
[2] 复杂网络动力学系统重构文献
[3] 互信息（Mutual Information)
[4] Transfer Entropy
[5] Granger Causality

本文主要内容来自 北京师范大学系统科学学院教授 张江老师， 并在此基础上补充一些细枝末节。