张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
导语

复杂系统的对象是包含很多构成组元的系统,范围极广,包括物理系统、生态系统和社会系统等。这些现实世界中的各式复杂系统往往可以被抽象为一组单元,并且它们按照一定的动力学法则相互作用着。那么我们如何自动构建系统运行的模型呢?这是一种逆向工程,也被称为网络动力学重构问题。基于这一问题我们整理了这份结合多门基础课程、多篇经典论文的学习路径,供你参考。


本文首发于集智斑图,扫码查看资料详情列表
https://pattern.swarma.org/path?id=28&from=wechat


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部


目录

一. 问题描述

  • 通用方法:

    相关性方法

    基于信息论的方法

    格兰杰因果检验(Granger Causality)方法

    相空间重构方法

    CCM方法

    线性化方程求解

    压缩感知(Compress Sensing)

    驱动响应方法

    概率图模型

    因果网络

    演化计算方法

    图神经网络方法

  • 基于模型的方法

  • 应用:

    经济领域

    基因调控网络与生物学

    大脑网络

    气候与天气系统

二、结束语




问题描述


现实世界中的各式复杂系统往往可以被抽象为一组单元,它们通过一个网络相连,并按照一定的动力学法则发生相互作用。传统的复杂系统研究思路是根据我们面对的实际现象,例如天气系统,我们人类科学家对其进行抽象,描述为一组网络动力学方程(例如 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

另外,有关一般的网络动力系统的重构问题,可参考这本中文书:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
图1:数据驱动建模


也可以参见综述::

论文题目:

从数据到结构——动力学网络重构

论文地址:

http://engine.scichina.com/publisher/scp/journal/SSPMA/50/1/10.1360/SSPMA2019-0127?slug=abstract


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1189?from=wechat


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


关于网络补全,这是一篇好文章:

论文题目:

The Network Completion Problem: Inferring Missing Nodes and Edges in Networks

论文地址:

https://digital.library.unt.edu/ark:/67531/metadc837635/m2/1/high_res_d/1035599.pdf


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


关于概率图模型,可参考这本书:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图2:概率图模型


概率图模型:

https://www.amazon.com/Probabilistic-Graphical-Models-Principles-Computation/dp/0262013193


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


关于因果推断,可参考 Judea Pearl 的两本书:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图3:为什么


为什么:

https://www.amazon.com/-/zh/dp/046509760X/ref=sr_1_3?__mk_zh_CN=%E4%BA%9A%E9%A9%AC%E9%80%8A%E7%BD%91%E7%AB%99&keywords=why&qid=1582185453&s=books&sr=1-3


相关阅读:

因果之箭指向何方?| 图灵奖得主珀尔的《为什么》


另一本是:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图4:因果

Causality:

https://www.amazon.com/-/zh/dp/052189560X/ref=sr_1_1?__mk_zh_CN=%E4%BA%9A%E9%A9%AC%E9%80%8A%E7%BD%91%E7%AB%99&keywords=causality&qid=1582185500&s=books&sr=1-1


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




方法


尽管按照上述的内容不同领域的人定义了非常多不同的名词来概括一个网络动力学系统的重构问题,但是其实它们的本质都非常类似。下面,我们在论述的过程中,将不再对这些不同的问题作区分。那么,如何解决这些问题呢?人们提出了各种各样的方法。目前来看,这些方法基本可以概括为两大类,即(1)、无模型(Model free)的通用类方法;(2)基于特定模型(Model based)方法。其中通用类方法是指我们可以将复杂网络动力学重构问题抽象成一套统一的数学或计算框架,因此,我们便可以对这一统一框架进行数学或计算机求解,而不必再去区分到底这一框架背后的具体领域问题是什么。因此,这里的统一框架可以用来解决基因调控网络重构,也可以解决神经网络重构等问题的。而第二类特定方法则与其相反,它往往针对一类特定问题,例如给定网络上的传播动力学模型为 SIR 模型,然后在这一特定的模型上来去做网络结构的重构或推断。下面,我们就分这两个类别来对文献做综述。



通用方法


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



相关性方法


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


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

论文题目:

A Gene-Coexpression Network for Global Discovery of Conserved Genetic Modules

论文地址:

https://science.sciencemag.org/content/302/5643/249


在经济和金融领域,相关性也是一种常用的方法,例如下面这篇文章利用股票时间序列构建了一个加权网络,然后再利用最小生成树的方法,获得股票之间的层级结构信息:

论文题目:

Hierarchical structure in financial markets

论文地址:

https://link.springer.com/article/10.1007/s100510050929


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

论文题目:

A tool for filtering information in complex systems

论文地址:

https://www.pnas.org/content/102/30/10421


另外,当我们考虑到相互影响的延迟效应的时候,也可以考虑用两个时间序列的延迟相关性。比如,我们考虑雾霾从 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

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.66.026125


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

论文题目:

Reconstruction of dynamic networks with time-delayed interactions in the presence of fast-varying noises

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.99.042311


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

论文题目:

Inner Composition Alignment for Inferring Directed Networks from Short Time Series

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.107.054101


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1601?from=wechat


基于信息论的方法

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


比如,常用的一种方法是互信息(Mutual Information),它提供了相关性的另一种度量。


互信息定义为:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
互信息的数学定义

这篇文章用互信息的方法定义了全球气候网络:

论文题目:

The backbone of the climate network

论文地址:

https://iopscience.iop.org/article/10.1209/0295-5075/87/48007


另外一个常用于时间序列的方法是传输熵(Transfer Entropy),它能够刻画引入另一个变量对预测当前变量的贡献,因此它可以在一定程度上衡量因果联系,这与后面介绍的格兰杰因果检验方法可以说是一脉相承。


传输熵的定义为:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

传输熵的数学表达式


它进一步可以转化为条件互信息(conditional mutual information)的形式:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

传输熵的条件互信息的形式


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


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

论文题目:

Model-Free Reconstruction of Excitatory Neuronal Connectivity from Calcium Imaging Signals

论文地址:

https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1002653


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1399?from=wechat



格兰杰因果检验(Granger Causality)方法


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


更严格的数学表达可以用下面的式子:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

格兰杰因果检验(X和Y具有因果关系的定义式)


这是格兰杰提出格兰杰因果检验的原始论文:

论文题目:

Investigating Causal Relations by Econometric Models and Cross-spectral Methods

论文地址:

https://www.jstor.org/stable/1912791?seq=1


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1522?from=wechat


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 sciences

论文地址:

https://www.nature.com/articles/s41467-019-10105-3


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1399?from=wechat


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

论文题目:

A review of the Granger-causality fallacy

论文地址:

https://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=229894


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


这篇文章很好地展示了格兰杰因果方法可以用于非线性系统:

论文题目:

Causal and Structural Connectivity of Pulse-Coupled Nonlinear Networks

论文地址:

https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.111.054102


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

论文题目:

Detecting strange attractors in turbulence

论文地址:

https://link.springer.com/chapter/10.1007/BFb0091924


用 Taken 定理做重构,主要的想法就是利用已有的时间序列数据,来直接构成原始的相空间中的轨迹。例如,我们的动力系统是一个三维的系统,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) 就是一个三维空间中的轨迹,那么它在三维空间中的轨迹将与原始的三维动力学相空间中的轨迹同胚(拓扑等价)。


如图展示了洛伦兹吸引子的重构:

张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图5:洛伦兹吸引子产生的时间序列


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图6:利用2阶延迟的时间序列重构洛伦兹吸引子


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

论文题目:

Geometry from a Time Series

论文地址:

http://journals.aps.org/prl/pdf/10.1103/PhysRevLett.45.712


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1379?from=wechat


关于如何选定延迟时间,可以参考:

论文题目:

Proper choice of the time delay for the analysis of chaotic time series

论文地址:

https://www.sciencedirect.com/science/article/abs/pii/0375960189901692


关于如何选择最好的维度,可见:

论文题目:

Embedology

论文地址:

https://link.springer.com/article/10.1007/BF01053745


如何用重构的吸引子来进行时间序列的预测:

论文题目:

Predicting chaotic time series

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.59.845


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1379?from=wechat


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

论文题目:

Estimating Model Parameters from Time Series by Autosynchronization

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.76.1232



CCM方法


所谓的 CCM 是指收敛交叉映射(Convergent Cross Mapping)方法,它来源于相空间重构理论。只不过,CCM 的目标并非重构动力学或吸引子,而是希望找到变量之间的“CCM因果联系”。CCM 方法指出,如果一个事件 A 是 B 的因,并不意味着 A 一定会在 B 之前发生。一个著名的例子就是 A=鸡打鸣和 B=太阳升起。显然,我们每天都会观测到 A 会在 B 发生前发生,那么,我们可以说 A 是 B 的因吗?显然不行。因为,我们都知道,太阳升起才是让公鸡打鸣的原因,只不过由于常年的学习进化,公鸡已经学会了预测太阳升起这一事件,于是公鸡可以在太阳升起前打鸣。CCM 号称,如果用该方法分析公鸡打鸣和太阳升起这样的时间序列,它可以准确地判别出正确的因果关系。


它的指导思想来源于相空间重构的 Taken 定理。我们知道,一个两变量的动力系统可以写成 dx/dt=f(x,y), dy/dt=g(x,y)。它们共同构成了一个动力学吸引子记做 M。Taken 定理说,一个吸引子在任何一个子空间中的投影都有可能重构出吸引子本身。于是,我们可以选择两个特殊的投影,一个是在x变量的子空间上投影,另一个是在 y 变量的子空间上。既然,这两个空间都是吸引子 M 的投影,那么 x 和 y 这两个子空间中的时间序列就必然会存在着一定的联系。下面我们考虑时间延迟的时间序列重构。假设 x 的时间延迟序列可以重构出一个相空间 M_X,y 的时间延迟序列可以重构出相空间 M_y,那么对于任意一个时刻,这两个相空间流形 M_x,M_y 上的对应点附近的邻域必然存在着很强的相关性,因为它们都来自 M 上的同一个邻域。如下图:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图7:CCM原理说明


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

论文题目:

Detecting Causality in Complex Ecosystems

论文地址:

https://science.sciencemag.org/content/338/6106/496


相关阅读:
Science经典论文:如何检测复杂生态系统中的因果关系?


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

论文题目:

Detection of time delays and directional interactions based on time series from complex dynamical systems

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.96.012221


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1383?from=wechat


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

论文题目:

Convergent Cross-Mapping and Pairwise Asymmetric Inference

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.90.062903


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1383?from=wechat



线性化方程求解


这一思路的核心在于将一个非线性的动力学方程组转化为一个线性系统,从而来进行重构。具体地,假设系统的非线性动力系统为:dx/dt=f(x(t))+r(t),其中 x 是多维变量,即多个节点,A 是节点之间的相互作用矩阵,f是非线性函数,r(t) 为一个高斯白噪声过程。那么,我们可以先把这个动力学 f 做简化,即利用泰勒展开,或者在任何一组函数基上做展开,把动力系统变为一个线性动力系统,即 dx/dt=Ax+r(t) 这样的形式,其中 A 是各个线性项的级数展开的系数,也就是 x 中各个变量相互作用的网络。于是,我们的问题就是,如果假设这个系统就是这样一个线性系统,那么我们如何根据其生成的时间序列而将这个网络 A 给重构出来呢?答案就在于可以直接求得解析解。利用白噪声的性质,我们可以求各个不同变量的时间序列的相关性,从这些相关性度量就可以显式地求解出 A。


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

论文题目:
从数据到结构——动力学网络重构

论文地址:

http://engine.scichina.com/publisher/scp/journal/SSPMA/50/1/10.1360/SSPMA2019-0127?slug=abstract


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1189?from=wechat


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

论文题目:

Model-free inference of direct network interactions from nonlinear collective dynamics

论文地址:

https://www.nature.com/articles/s41467-017-02288-4


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1365?from=wechat


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

论文题目:

Dynamical networks reconstructed from time series

论文地址:

https://arxiv.org/abs/1209.0219


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

论文题目:

Reconstructing the topology of sparsely connected dynamical networks

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.77.026103



压缩感知(Compress Sensing)


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


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


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图8:压缩感知方法示意图


其中 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

论文地址:

https://www.sciencedirect.com/science/article/abs/pii/S037015731630134X


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部https://campus.swarma.org/course/1200?from=wechat


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

论文题目:

Time-series–based prediction of complex oscillator networks via compressive sensing

论文地址:

https://iopscience.iop.org/article/10.1209/0295-5075/94/48006


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

论文题目:

Reconstructing propagation networks with natural diversity and identifying hidden sources

论文地址:

https://www.nature.com/articles/ncomms5323


相关阅读:

为了研究因果关系,原来科学家在这么多方向上都有尝试

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

论文题目:

Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.106.154101


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

论文题目:

Network Reconstruction Based on Evolutionary-Game Data via Compressive Sensing

论文地址:

https://journals.aps.org/prx/abstract/10.1103/PhysRevX.1.021021


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

论文题目:

Reconstruction of Complex Network based on the Noise via QR Decomposition and Compressed Sensing

论文地址:

https://www.nature.com/articles/s41598-017-15181-3


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

论文题目:

Forecasting the future: Is it possible for adiabatically time-varying nonlinear dynamical systems?

论文地址:

https://aip.scitation.org/doi/abs/10.1063/1.4740057?journalCode=cha


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1365?from=wechat


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

论文题目:

Discovering governing equations from data by sparse identification of nonlinear dynamical systems

论文地址:

https://www.pnas.org/content/113/15/3932



驱动响应方法


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


这一方法的基本思路是,假设系统演化达到稳态的时候,我们给其中某一个节点加上一个冲击信号(一个 delta 分布函数)。然后,我们就可以将整个系统的演化方程在稳态附近进行级数展开,从而将各个变量之间的相互影响关系推测出来。


这是近期发表在 Science Advances 上的一篇用驱动响应方式进行网络重构的文章:

论文题目:

Revealing physical interaction networks from statistics of collective dynamics

论文地址:

https://advances.sciencemag.org/content/3/2/e1600396


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

论文题目:

Revealing networks from dynamics: an introduction

论文地址:

https://arxiv.org/abs/1408.2963


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部https://campus.swarma.org/course/1200?from=wechat


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

论文题目:

从数据到结构——动力学网络重构

论文地址:

http://engine.scichina.com/publisher/scp/journal/SSPMA/50/1/10.1360/SSPMA2019-0127?slug=abstract


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1189?from=wechat


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



概率图模型


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


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


以贝叶斯网为例,如下图所示:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图9:贝叶斯网示例


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


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


有关概率图模型最好的资料就是这本书:


关于概率图模型,可参考这本书:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图10:概率图模型


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

论文题目:

A guide to the literature on learning probabilistic networks from data

论文地址:

https://ieeexplore.ieee.org/abstract/document/494161


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

论文题目:

Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans

论文地址:

https://royalsocietypublishing.org/doi/full/10.1098/rstb.2017.0377



因果网络


如果系统存在着确定性的演化方程,并且如果某个变量x出现在另一个变量 y 的演化方程中,那么我们就认为 x 构成了 y 的一个原因,也就是说,x 和 y 之间存在着因果联系。然而,当我们考虑的系统是随机的不确定系统的时候,这种联系则没有那么显然。在概率图模型的框架下,人们将因果联系赋予了更多的内涵。例如,如果随机变量 X 构成了随机变量 Y 的原因就不仅要求,在 X 的条件下 Y 的概率更高,而且还要求在主动对 X 进行干预的条件下,能够让 Y 出现的概率出现显著变化。


关于什么是因果,以及它与普通概率图模型之间的关系可以重点参考 Pearl 的这两本书:

为什么:

https://www.amazon.com/-/zh/dp/046509760X/ref=sr_1_3?__mk_zh_CN=%E4%BA%9A%E9%A9%AC%E9%80%8A%E7%BD%91%E7%AB%99&keywords=why&qid=1582185453&s=books&sr=1-3


另一本是:

Causality:

https://www.amazon.com/-/zh/dp/052189560X/ref=sr_1_1?__mk_zh_CN=%E4%BA%9A%E9%A9%AC%E9%80%8A%E7%BD%91%E7%AB%99&keywords=causality&qid=1582185500&s=books&sr=1-1


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

论文题目:

Causal network reconstruction from time series: From theoretical assumptions to practical estimation

论文地址:

https://aip.scitation.org/doi/full/10.1063/1.5025050

论文题目:

A survey of learning causality with data: Problems and methods

论文地址:

https://arxiv.org/abs/1809.09337


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

论文题目:

Detecting and quantifying causal associations in large nonlinear time series datasets

论文地址:

https://advances.sciencemag.org/content/5/11/eaau4996.abstract


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1573?from=wechat


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

论文题目:

Causal Link Estimation Under Hidder Confounding in Ecological Time Series

论文地址:

https://advances.sciencemag.org/content/5/11/eaau4996.abstract



演化计算方法


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


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

论文题目:

Automated reverse engineering of nonlinear dynamical systems

论文地址:

https://www.pnas.org/content/104/24/9943


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

论文题目:

Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning

论文地址:

https://arxiv.org/abs/1811.05592



图神经网络方法


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


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


有关图神经网络的综述,可以看这篇:

论文题目:

Relational inductive biases, deep learning, and graph networks

论文地址:

https://arxiv.org/abs/1806.01261


相关阅读:

图网络入门路径:从网络科学视角出发,上手深度学习前沿技术


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


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


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

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


下面这篇就是利用图神经网络解决动力学学习的一个经典作品:

论文题目:

Graph networks as learnable physics engines for inference and control

论文地址:

https://arxiv.org/abs/1806.01242


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/955?from=wechat


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

论文题目:

Differentiable Physics-informed Graph Networks

论文地址:

https://arxiv.org/abs/1902.02950


这类推断动力学的工作很多,并已经应到了很多实际问题中,例如,用图神经网络的方法来预测交通流:

论文题目:

GMAN: A Graph Multi-Attention Network for Traffic Prediction

论文地址:

https://arxiv.org/abs/1911.08415


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1130?from=wechat

预测网约车数量:

论文题目:

Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting

论文地址:

http://www-scf.usc.edu/~yaguang/papers/aaai19_multi_graph_convolution.pdf


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/955?from=wechat


还有雾霾预报:

论文题目:

PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting

论文地址:

https://arxiv.org/abs/2002.12898


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1573?from=wechat


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

论文题目:

Neural Relational Inference for Interacting Systems

论文地址:

https://arxiv.org/abs/1802.04687


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


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图12:NRI结构示意图


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

论文题目:

A general deep learning framework for network reconstruction and dynamics learning

论文地址:

https://appliednetsci.springeropen.com/articles/10.1007/s41109-019-0194-4


其架构如下图:


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

图13:GGN架构示意图


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


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

论文题目:

Structure-informed Graph Auto-encoder for Relational Inference

论文地址:

https://graphreason.github.io/papers/22.pdf


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

论文题目:

Neural Relational Inference with Fast Modular Meta-learning

论文地址:

http://papers.nips.cc/paper/9353-neural-relational-inference-with-fast-modular-meta-learning.pdf


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1053?from=wechat


论文题目:

Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network

论文地址:

https://arxiv.org/abs/2001.06576


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

论文题目:

Learning Dynamical Systems from Partial Observations

论文地址:

https://arxiv.org/abs/1902.11136


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

论文题目:

Learning discrete structures for graph neural networks

论文地址:

https://arxiv.org/abs/1903.11960


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

论文题目:

Towards Automated Statistical Physics : Data-driven Modeling of Complex Systems with Deep Learning

论文地址:

https://arxiv.org/abs/2001.02539


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1109?from=wechat


基于模型的方法


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


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

论文题目:

A statistical inference approach to structural reconstruction of complex networks from binary time series

论文地址:

http://journals.aps.org/pre/abstract/10.1103/PhysRevE.97.022301


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部
https://campus.swarma.org/course/1601?from=wechat


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

论文题目:

Data Based Reconstruction of Duplex Networks

论文地址:

https://epubs.siam.org/doi/abs/10.1137/19M1254040


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

论文题目:

Reconstructing signed networks via Ising dynamics

论文地址:

https://pubmed.ncbi.nlm.nih.gov/30599526/


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

论文题目:

Network Inference and Biological Dynamics

论文地址:

https://arxiv.org/abs/1112.1047


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

论文题目:

Hidden network reconstruction from information diffusion

论文地址:

https://ieeexplore.ieee.org/document/7266560


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

论文题目:

Reconstructing complex networks without time series

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.96.022320


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

论文题目:

Reconstructing networks of pulse-coupled oscillators from spike trains

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.96.012209



应用


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



经济领域


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


下面这篇文章对经济、金融领域中的网络重构工作进行了很好的综述:

论文题目:

Reconstruction methods for networks: The case of economic and financial systems

论文地址:

https://www.sciencedirect.com/science/article/abs/pii/S0370157318301509?via=ihub


然而,这篇文章讨论的网络重构与上面讨论的各类网络重构方法具有很大的区别,它并没有涉及时间序列和动力学,而更多地是在利用最大熵方法来对网络进行重构。


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

论文题目:

Spread of risk across financial markets: better to invest in the peripheries

论文地址:

https://www.nature.com/articles/srep01665


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

论文题目:

Systemic risk analysis on reconstructed economic and financial networks

论文地址:

https://www.nature.com/articles/srep15758


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

论文题目:

Estimating global bank network connectedness 

论文地址:

https://onlinelibrary.wiley.com/doi/full/10.1002/jae.2585



基因调控网络与生物学


蛋白质(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 

论文地址:

https://www.nature.com/articles/s41592-019-0690-6


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

论文题目:

Wisdom of crowds for robust gene network inference

论文地址:

https://www.nature.com/articles/nmeth.2016



大脑网络


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


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


结构链接通常是指物理上实际存在的或能够链接一组神经元或其它神经要素的突触链接,以及这些链接中包含的相关生物物理属性。


功能链接通常情况下则是一个统计意义上的概念。一般的,功能链接能够捕捉到神经单元在统计意义上的相互关联。


有效链接则可以看作是结构与功能链接的并集,它描述了一个神经单元到另一个单元的直接效应。原则上,我们可以用一些因果推断的方式推测出这样的有效链接,例如前面介绍的格兰杰因果检验以及传输熵等方法。


关于大脑网络链接的更详细讨论,请参看:


scholarpedia上的词条:

http://www.scholarpedia.org/article/Brain_connectivity


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

论文题目:

Exploring the brain network: a review on resting-state fMRI functional connectivity

论文地址:

https://www.sciencedirect.com/science/article/pii/S0924977X10000684


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

论文题目:

Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans 

论文地址:

https://royalsocietypublishing.org/doi/full/10.1098/rstb.2017.0377


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

论文题目:

Mapping directed influence over the brain using Granger causality and fMRI 

论文地址:

https://www.sciencedirect.com/science/article/abs/pii/S1053811904006688


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

论文题目:

Transfer entropy—a model-free measure of effective connectivity for the neurosciences

论文地址:

https://pubmed.ncbi.nlm.nih.gov/20706781/


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

论文题目:

Reconstruction of a neural network from a time series of firing rates 

论文地址:

https://journals.aps.org/pre/abstract/10.1103/PhysRevE.93.062313



气候与天气系统


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


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


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

论文题目:

The architecture of the climate network

论文地址:

https://www.sciencedirect.com/science/article/pii/S0378437103009646


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

论文题目:

Climate Networks around the Globe are Significantly Affected by El Niño

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.100.228501

论文题目:

Emergence of El Niño as an Autonomous Component in the Climate Network

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.107.14850


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

论文题目:

Dominant Imprint of Rossby Waves in the Climate Network

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.111.138501


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

论文题目:

The backbone of the climate network

论文地址:

https://iopscience.iop.org/article/10.1209/0295-5075/87/48007


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

论文题目:

Teleconnection Paths via Climate Network Direct Link Detection

论文地址:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.115.268501


然而,这些文章的讨论大多局限在对相关关系的讨论。人们要想彻底理解气候系统背后的相互作用机制,还需要搞懂它们背后的因果联系。下面这篇文章就用一种所谓的 PCMCI 算法,它能够捕捉到气候系统背后的因果联系:

论文题目:

Detecting and quantifying causal associations in large nonlinear time series datasets

论文地址:

https://advances.sciencemag.org/content/5/11/eaau4996


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1573?from=wechat




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

论文题目:

Very early warning of next El Nino

论文地址:

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3926055/


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

论文题目:

PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting

论文地址:

https://arxiv.org/abs/2002.12898


张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

https://campus.swarma.org/course/1573?from=wechat


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




结束语


本文尝试针对目前比较常见的动力学和网络重构的方法进行了梳理和概括,并针对几个常见的应用领域进行了介绍。随着大数据的发展和计算能力的进一步提升,这类重构方法将会得到更进一步的发展。这一领域的一个终极发展目标则是对复杂系统的自动建模。这样,我们在这些算法的帮助下对复杂系统的理解有可能完成巨大的飞跃。


       

参考文献:

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

[2] M. Kim, J. Leskovec: The Network Completion Problem: Inferring Missing Nodes and Edges in Networks ,Proceedings of the Eleventh SIAM International Conference on Data Mining, SDM 2011,2011

[3] Joshua M. Stuart,Eran Segal,Daphne Koller.et al.: A Gene-Coexpression Network for Global Discovery of Conserved Genetic Modules ,science,2003,302(5643): 249-255

[4] R. N. Mantegna: Hierarchical structure in financial markets ,The European Physical Journal B - Condensed Matter and Complex Systems,2012

[5] M. Tumminello, T. Aste, T. Di Matteo.et al.: A tool for filtering information in complex systems ,Proceedings National Academy of Sciences of United States of America,2005,102(30): 10421-10426

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

[7] Z. Zhang, Y. Chen, Y. Mi.et al.: Reconstruction of dynamic networks with time-delayed interactions in the presence of fast-varying noises ,Physical Review E,2019,99042311

[8] S. Hempel, A. Koseska, J. Kurths.et al.: Inner Composition Alignment for Inferring Directed Networks from Short Time Series ,Physical Review Letters,2011,107054101

[9] J. F. Donges, Y. Zou, N. Marwan.et al.: The backbone of the climate network ,Europhysics Letters,2009,87(4): 48007

[10] O. Stetter, D. Battaglia, J. Soriano.et al.: Model-Free Reconstruction of Excitatory Neuronal Connectivity from Calcium Imaging Signals ,PloS Computational Biology,2012,8e1002653

[11] C. W. J. Granger: Investigating Causal Relations by Econometric Models and Cross-spectral Methods,Econometrica,1969,37(3): 424-438

[12] Inferring causation from time series in Earth system sciences[论文未入库] ,Nature

[13] M. Maziarz: A review of the Granger-causality fallacy ,The Journal of Philosophical Economics: Reflections on Economic and Social Issues.,2015,VIII(2): 1843-2298

[14] D. Zhou, Y. Xiao, Y. Zhang.et al.: Causal and Structural Connectivity of Pulse-Coupled Nonlinear Networks ,Physical Review Letters,2013,111054102

[15] F. Takens: Detecting strange attractors in turbulence ,Dynamical Systems and Turbulence,2006366-381

[16] N. H. Packard, J. P. Crutchfield, J. D. Farmer.et al.: Geometry from a Time Series ,Physical Review Letters,1980,45(9): 712-716

[17] W.Liebert, H.G.Schuster: Proper choice of the time delay for the analysis of chaotic time series ,Physics Letters A,1989,142(2-3): 107-111

[18] T. D. Sauer, J. A. Yorke, M. Casdagli: Embedology ,Journal of Statistical Physics,1991,65579–616

[19] J. D. Farmer, J. J. Sidorowich: Predicting chaotic time series ,Physical Review Letters,1987,59845

[20] U. Parlitz: Estimating Model Parameters from Time Series by Autosynchronization ,Physical Review Letters,1996,761232

[21] H. Ma, S. Leng, C. Tao.et al.: Detection of time delays and directional interactions based on time series from complex dynamical systems ,Physical Review E,2017,96012221

[22] J. M. McCracken, R. S. Weigel: Convergent Cross-Mapping and Pairwise Asymmetric Inference ,Physical Review E,2014,90062903

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

[24] Jose Casadiego,Mor Nitzan,Sarah Hallerberg.et al.: Model-free inference of direct network interactions from nonlinear collective dynamics ,nature communications,2017,8(1): 1-10

[25] Z. Levnajić: Dynamical networks reconstructed from time series ,arXiv:1209.0219,2012arXiv:1209.0219

[26] D. Napoletani, T. D. Sauer: Reconstructing the topology of sparsely connected dynamical networks ,Physical Review E,2008,77026103

[27] W.-X. Wang,Y.-C. Lai, Celso Grebogi: Data based identification and prediction of nonlinear and complex dynamical systems ,Physics Reports,2016,644(12): 1-76

[28] W.-X. Wang, R. Yang, Y.-C. Lai.et al.: Time-series–based prediction of complex oscillator networks via compressive sensing ,European Physics Letters,2011,94(4): 48006

[29] Zhesi Shen,Wen-Xu Wang,Ying Fan.et al.: Reconstructing propagation networks with natural diversity and identifying hidden sources ,Nature,2014

[30] W.X. Wang, R.Yang, Y.-C. Lai.et al.: Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing,Physics Review Letters,2011,106154101

[31] W.-X. Wang, Y.-C. Lai, C. Grebogi.et al.: Network Reconstruction Based on Evolutionary-Game Data via Compressive Sensing ,Physical Review X,2011,1021021

[32] Lixiang Li,Dafei Xu,Haipeng Peng.et al.: Reconstruction of Complex Network based on the Noise via QR Decomposition and Compressed Sensing ,scientific reports,2017,7(1): 1-13

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

[34] S. L. Brunton, J. L. Proctor, J. N. Kutz: Discovering governing equations from data by sparse identification of nonlinear dynamical systems ,Proceedings of National Academy of Sciences of U.S.A.,2016,113(15): 3932-3937

[35] M. Nitzan, J. Casadiego, M. Timme: Revealing physical interaction networks from statistics of collective dynamics,Science Advances,2017,3(2): e1600396

[36] Marc Timme, Jose Casadiego: Revealing networks from dynamics: an introduction ,Journal of Physics A: Mathematical and Theoretical,2014,41(37):

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

[38] W. Buntine: A guide to the literature on learning probabilistic networks from data ,IEEE Transactions on knowledge and data engineering,1996,8(2): 195-210

[39] Liu, H, Kim.et al.: Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans ,Philosophical Transactions of the Royal Society B: Biological Sciences,2018,37320170377

[40] Runge J.: Causal network reconstruction from time series: From theoretical assumptions to practical estimation,Chaos: An Interdisciplinary Journal of Nonlinear Science,2018,28075310

[41] Guo, R, Cheng.et al.: A survey of learning causality with data: Problems and methods ,arXiv preprint arXiv:1809.09337,2018

[42] Runge, J, Nowack.et al.: Detecting and quantifying causal associations in large nonlinear time series datasets ,Science Advances,2019,5eaau4996

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

[44] J. Bongard, H. Lipson: Automated reverse engineering of nonlinear dynamical systems ,Proceedings of the National Academy of Sciences of U.S.A.,2007,104(24): 9943-9948

[45] Rise Ooi,Chao-Han Huck Yang,Pin-Yu Chen.et al.: Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning ,arXiv:1811.05592,2018

[46] Peter W. Battaglia,Jessica B. Hamrick,Victor Bapst.et al.: Relational inductive biases, deep learning, and graph networks ,arxiv,2018

[47] Alvaro Sanchez-Gonzalez,Nicolas Heess,Jost Tobias Springenberg.et al.: Graph networks as learnable physics engines for inference and control ,arxiv,2018

[48] Sungyong Seo,Yan Liu: Differentiable Physics-informed Graph Networks ,arXiv:1902.02950,2019

[49] Chuanpan Zheng, Xiaoliang Fan, Cheng Wang.et al.: GMAN: A Graph Multi-Attention Network for Traffic Prediction,arxiv,2019

[50] Spatiotemporal multi-graph convolution network for ride-hailing demand forecasting[C]//[论文未入库]

[51] Shuo Wang,Yanran Li,Jiang Zhang.et al.: PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting ,arXiv:2002.12898,2020

[52] Thomas Kipf,Ethan Fetaya,Kuan-Chieh Wang.et al.: Neural Relational Inference for Interacting Systems,arXiv:1802.04687, 2018.,2018

[53] Zhang Zhang, Yi Zhao, Jing Liu.et al.: A general deep learning framework for network reconstruction and dynamics learning ,2019

[54] Yaguang Li,Chuizheng Meng,Cyrus Shahabi.et al.: Structure-informed Graph Auto-encoder for Relational Inference and Simulation ,2016

[55] Ferran Alet, Erica Weng, Tomás Lozano Pérez.et al.: Neural Relational Inference with Fast Modular Meta-learning,2019

[56] Mengyuan Chen,Jiang Zhang,Zhang Zhang.et al.: Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network ,arXiv:2001.06576,2020

[57] Ibrahim Ayed,Emmanuel de Bézenac,Arthur Pajot.et al.: Learning Dynamical Systems from Partial Observations,arXiv:1902.11136,2019

[58] Luca Franceschi,Mathias Niepert,Massimiliano Pontil.et al.: Learning Discrete Structures for Graph Neural Networks,arXiv:1903.11960,2019

[59] Seungwoong Ha,Hawoong Jeong: Towards Automated Statistical Physics : Data-driven Modeling of Complex Systems with Deep Learning ,arxiv,2020

[60] C. Ma, H.-S. Chen, Y.-C. Lai.et al.: A statistical inference approach to structural reconstruction of complex networks from binary time series ,Physical Review E,2018,97(022301):

[61] C. Ma , H.-S. Chen, X. Li.et al.: Data Based Reconstruction of Duplex Networks ,SIAM Journal on Applied Dynamical Systems,2019,19(1): 124–150

[62] B.B. Xiang, C. Ma, H.S. Chen.et al.: Reconstructing signed networks via Ising dynamics ,Chaos,2018,12123117[63] C.J. Oates, S. Mukherjee: Network Inference and Biological Dynamics ,Annual Applied Statistics,2012,6(3): 1209–1235

[64] F. W. Crawford: Hidden network reconstruction from information diffusion ,18th International Conference on Information Fusion,2015180-185

[65] Ma, C, Zhang H F.et al.: Reconstructing complex networks without time series ,2017,96022320

[66] Rosenblum, M., Review.et al.: Reconstructing networks of pulse-coupled oscillators from spike trains ,2017,96012209

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

[68] Pozzi, F, Di Matteo.et al.: Spread of risk across financial markets: better to invest in the peripheries ,Scientific reports,2013,31665

[69] Giulio Cimini,Tiziano Squartini,Diego Garlaschelli.et al.: Systemic Risk Analysis on Reconstructed Economic and Financial Networks ,scientific reports,2015,5(1): 1-12

[70] Demirer, M, Liu.et al.: Estimating global bank network connectedness[J] ,Journal of Applied Econometrics,2018,331--15

[71] Pratapa, A, Jalihal.et al.: Benchmarking algorithms for gene regulatory network inference from single-cell transcriptomic data[J] ,Nature Methods,20201--8

[72] Marbach, D, Costello.et al.: Wisdom of crowds for robust gene network inference[J] ,Nature methods,2012,9(8): 796

[73] Van Den Heuvel M P, Pol H E H.: Exploring the brain network: a review on resting-state fMRI functional connectivity,European neuro psycho pharmacology,2010,20519--534

[74] Liu, H, Kim.et al.: Functional connectomics from neural dynamics: probabilistic graphical models for neuronal network of Caenorhabditis elegans ,Philosophical Transactions of the Royal Society B: Biological Sciences,2018,37320170377

[75] Roebroeck, A, Formisano.et al.: Mapping directed influence over the brain using Granger causality,Neuroimage,2005,25230--242

[76] Vicente, R, Wibral.et al.: Transfer entropy—a model-free measure of effective connectivity for the neurosciences[J],Journal of computational neuroscience,2011,3045--67

[77] Pikovsky A, Review, E: Reconstruction of a neural network from a time series of firing rates[J] ,2016,93062313

[78] Tsonis, A A, Roebber P J.: The architecture of the climate network ,Physica A: Statistical Mechanics and its Applications,2004,333497--504

[79] Yamasaki, K, Gozolchiani.et al.: Climate networks around the globe are significantly affected by El Nino[J] ,Physical review letters,2008,100228501

[80] Gozolchiani, A, Havlin.et al.: Emergence of El Niño as an autonomous component in the climate network ,Physical review letters,2011,107148501

[81] Wang, Y, Gozolchiani.et al.: Dominant imprint of Rossby waves in the climate network[J] ,Physical review letters,2013,111138501

[82] J. F. Donges, Y. Zou, N. Marwan.et al.: The backbone of the climate network ,Europhysics Letters,2009,87(4): 48007

[83] Zhou D, Gozolchiani A, Ashkenazy Y: Teleconnection paths via climate network direct link detection ,Physical review letters,2015,115268501

[84] Jakob Runge,Peer Nowack, Marlene Kretschmer.et al.: Detecting and quantifying causal associations in large nonlinear time series datasets ,Science,2019

[85] Ludescher J, Gozolchiani A, Bogachev M I: Very early warning of next El Niño ,Proceedings of the National Academy of Sciences,2014,1112064-2066

[86] Shuo Wang,Yanran Li,Jiang Zhang.et al.: PM2.5-GNN: A Domain Knowledge Enhanced Graph Neural Network For PM2.5 Forecasting ,arXiv:2002.12898,2020


(参考文献可上下滑动)



作者:张江

编辑:张爽


推荐阅读


多层网络的动力学:从结构依赖到历史依赖
因果观念新革命?万字长文,解读复杂系统背后的暗因果
超越简单规则——用图神经网络对复杂系统进行自动建模
Science经典论文:如何检测复杂生态系统中的因果关系?
加入集智,一起复杂!



张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部


集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

◆ ◆ 

搜索公众号:集智俱乐部


加入“没有围墙的研究所”

张江:怎样搞定复杂系统动力学重构?百篇资料一站获取-集智俱乐部

让苹果砸得更猛烈些吧!



👇点击“阅读原文”,查看百篇论文资料