导语
复杂网络中的因果涌现是指对于一个复杂网络来说，在合适的粗粒化处理之后能得到一个宏观的网络，该网络能够比原始网络展现出更强的因果特性，即有效信息（Effective Information，简称EI）更高，则称原始网络发生了因果涌现。复杂网络是一种用图的方式建模复杂系统的模型，广泛应用于多种领域。这些网络通常由大量节点和具有一定随机性的连边组成，节点可以代表个体或元素，而边则代表它们之间的相互作用或联系。因果涌现理论最初是由Erik Hoel[1]等人提出，该理论使用有效信息来量化离散马尔科夫动力学系统的因果性强弱。2020 年，Klein 等人[2]尝试将因果涌现的概念扩展到复杂网络上，核心思路是将复杂网络上的随机游走模型视作一个马尔科夫链，从而应用有效信息比较粗粒化后的更宏观尺度的网络和原始网络上的有效信息（EI）有何变化，当粗粒化网络（宏观尺度）比原始网络 （微观尺度）具有更高的EI时，则说明该网络发生了因果涌现。
近年来，张江老师带领研究组开始聚焦基于新兴 AI 技术进行数据驱动的自动建模研究，并立志破解复杂系统的涌现之谜。我们希望创建一个叫做"复杂AI次方"的开放实验室，实现思想共享、资源共享、跨学科交叉，共同为复杂系统自动建模而奋进。欢迎对复杂系统自动建模领域有热情，且认可这个领域发展前景的朋友一起来合作，促进这一领域的快速发展。
关键词：因果涌现，复杂网络，有效信息，复杂系统
王志鹏、刘易明 | 作者
张江、王志鹏、刘易明 | 审校
目录
1. 方法概述
2. 基本理论
2.1 基本思想
2.2 随机游走动力学
2.3 定义有效信息
2.3.1 网络实例
2.4 粗粒化复杂网络
2.4.1 粗粒化算法
2.4.1.1 贪婪算法
2.4.1.2 谱分解方法
2.4.1.3 梯度下降方法
2.5 定义复杂网络中的因果涌现
3. 数值结果
3.1 人工网络
3.2 真实网络
4. 应用
4.1 在元胞自动机上的应用
4.2 在生物网络上的应用
1. 方法概述
2013年，Erik Hoel等人首次提出了因果涌现理论[1]，并使用有效信息（Effective Information, EI）来量化离散马尔科夫动力学系统的因果性强弱。2020年Klein等人尝试将因果涌现理论拓展到复杂网络[2]上。这一扩展的主要思路为将复杂网络转变为一个马尔科夫链，从而可以直接应用Erik Hoel等人的原始方法来判断因果涌现。具体地，Klein等人的方法包括如下几个步骤：
1. 定义复杂网络上的动力学：引入随机游走子（Random Walker），该随机游走子可以沿着网络的连边随机跳转，从而构建该随机游走子的马尔科夫链（其中随机游走子的所有可能状态对应为复杂网络上的所有节点，而状态间的转移概率数值可以定义为每条有向连边的权值占比，即该边上的权重占该节点所有出边的权重的比例）；
2. 定义复杂网络上的有效信息：基于随机游走子的概率转移矩阵计算有效信息，如此便可以将原本刻画马尔科夫链的有效信息指标扩展到复杂网络上；
3. 粗粒化复杂网络（即将所有网络上的节点进行分组，转化为一系列宏观节点，并将连边也进行归并）得到宏观的复杂网络，并保证该转化后的网络满足动力学一致性，即保证粗粒化完以后的网络具有与原始网络相似的随机游走动力学；
4. 对比微观网络和粗粒化后的宏观网络的有效信息，判断因果涌现是否发生，并计算因果涌现强度数值。
2. 基本理论
2.1 基本思想
如何将Erik Hoel的因果涌现理论应用到复杂网络上？首先，Erik Hoel的理论是针对离散状态马尔科夫链进行展开的。因此，Klein等人需要将复杂网络转变为马尔科夫链。基本思想是，给网络赋予一套随机游走动力学，从而得到马尔科夫链和转移矩阵。其次，Hoel理论中的核心是有效信息指标，那么对该理论做延展的时候，也需要讨论一个网络的有效信息应该如何计算。再次，因果涌现现象是必须借助粗粒化策略来展现的，因此，Klein等人还要考虑如何粗粒化一个复杂网络。下面，本词条分别进行介绍。
2.2 随机游走动力学
由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是转移概率矩阵（Transitional Probability Matrix，简称TPM）。然而对于复杂网络来说，给定一个已知网络，并不具有动力学，所以需要人为定义一套网络上的动力学。Klein等人借助随机游走子的概念，在网络上定义了一个随机游走动力学，该动力学可以被自然地用马尔科夫链来进行表示，并且该马尔科夫链的状态就对应了网络上的节点，而状态转移概率矩阵也可以自然地用网络的邻接矩阵的某种变换而得到。
具体的，假设我们考虑一个连通图G，邻接矩阵为A。假设图上有N个节点，分别表示为1,2,...,N。我们首先可以定义节点i∈{1,2,⋯,N}到节点j∈{1,2,⋯,N}的转移概率为wij，它满足：
这里，aij≥0为G的邻接矩阵A的第i行，第j列元素，它对应连边i→j的权重。由于G是连通图，因此 。根据该定义，wij自然满足归一化条件：
因此，我们可以直接定义一个马尔科夫链，其状态空间为{1,2,⋯,N}，从i状态到j状态的转移概率就是wij，且对应的转移概率矩阵为：
W={wij}N×N
2.3 定义有效信息
对于一般的N个状态的马尔科夫链，其概率转移矩阵为：P，则其有效信息可以由下式计算 (参见有效信息)：
这里，Pi为P的第i个行向量， 为P的所有行向量求平均得到的平均向量。根据上式，EI可以分为两项，刚好对应两种计算下的Shannon信息熵，即−⟨H(Pi)⟩，它描述了P的确定性；还有H()，它刻画了P的非简并性。
下面，我们把这个公式套用到复杂网络上的随机游走子定义的马尔科夫链上
（1）
其中Wi为W的第i行构成的行向量，也对应了i节点跳转到其它节点的概率， 为W的所有行向量求平均得到的平均向量，
，表示从任意节点跳转到节点j的所有概率的平均值。同样，有效信息可以分解为确定性和简并性（参考有效信息）。
这两项分别是：
1. 确定性为−⟨H(Wi)⟩，其中，随机游走子从节点i跳出的不确定性可通过节点跳出概率向量Wi的香农熵定义，即H(Wi)，因此整个网络的确定性可通过所有节点香农熵的平均值取负数−⟨H(Wi)⟩得到；
2. 网络的非简并性为：H()，它是所有节点跳出概率的平均值的熵。
除此之外，1式还可以用有效信息的原始定义，即do干预形式的互信息来理解。在初始时刻，我们假设随机游走子的初始状态分布为：
S0=(1/N,1/N,⋯,1/N),
这相当于游走子会等概率地分布在所有网络节点上，这种初始分布相当于我们对随机游走子的初始分布进行了do干预，把该分布干预为了均匀分布。计算在这个do干预下的t=1时刻和初始时刻两状态分布的互信息，我们同样可以得到1式。
1式就是任意复杂网络G的有效信息的定义式。
2.3.1 网络实例
首先，为了直观地看到网络的拓扑结构和有效信息、确定性、简并性等各个网络指标值之间的关系，下图展示了6种特殊的人工网络，并列出了：确定性、简并性以及有效信息EI值。下图展示的6个图中，有向环形网络（第一个图）的确定性最高，简并性最低，因此有效信息最大，而有向全连通图（第三个图）的确定性和简并性都最小，因此有效信息也最小，其余四个图的有效信息介于这两个图之间。
此外，下面展示了五种经典的人工网络（完全图、星型图、环形图、BA (无标度网络)、ER (随机网络)）的确定性和简并性的大小分布，如下图所示，星型网络的确定性最高但是简并性也最高，因此有效信息也最低。同样完全图的确定性和简并性都最小，因此有效信息也最低。其余三个图的确定性较高，简并性较低，因此有效信息也较大。
2.4 粗粒化复杂网络
为了识别复杂网络中的因果涌现，需要对原始网络做粗粒化，而粗粒化操作通常需要有两个步骤：
1. 对原始网络的节点进行分组；
2. 根据节点分组，对网络的节点和相应的连边进行归并，从而得到一个宏观网络。
最后，通过比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。
其中，节点分组的目的是确定哪些原始网络的节点应该被归并为一个宏观节点；而网络的归并的目的是根据分组和原网络的结构而得到一个更小的粗粒化的网络，但却并不丢失原始网络主要特征。
在Klein等人的论文[2]，以及Griebenow 等人[3]的文献中，作者们主要提出了三种粗粒化网络的方法，包括：贪婪算法、谱分解方法以及梯度下降方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则除了梯度下降方法以外，另外两个都采用了相同的处理手段，即高阶依赖项建模（HOMs）[4]，其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性。
Klein等人[2]相当于使用贪婪算法对节点进行分组，但实质上该方法将分组和归并合并在一起执行了。这种方法对于大规模网络来说效率很低。所以，后来Griebenow[3]又提出了一种基于谱分解的方法来对原始网络节点进行分组，并将这种方法应用于偏好依附网络。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。
下面我们分别详细介绍这些粗粒化方法：
2.4.1 粗粒化算法
2.4.1.1 贪婪算法
该方法并不明显区分分组和归并，而是把两个步骤合并到了一起。
输入：具有N个节点的网络G，其邻接矩阵为：A；输出：经过粗粒化后的宏观网络G′，其邻接矩阵为：B，以及从A到B的粗粒化方式
1. 初始化一个节点的集合V，将V中的每个节点所属的马尔可夫毯（这是一个节点的集合，既包括该节点的父节点、子节点以及子节点的其他父节点）也加入集合中；
2. 遍历G中的节点（如果节点已经被合并成宏观节点则跳过），直到所有的节点遍历一遍停止；
3. 初始化一个队列Q, 取出集合V中vi对应的马尔可夫毯中的所有节点，将其加入队列中；
4. 初始时vμ=vi，
5. 分别尝试将 vμ 与 vj∈Q合并，形成一个新的宏观节点：vμ
1）执行网络归并算法，尝试归并网络（具体方法参考网络归并），并计算新网络的EI；
2）如果归并后的网络的EI增加了且满足粗粒化后的宏观网络与原始网络保持动力学一致性（具体方法参考动力学的一致性检验），就将这两个节点归并到一起组成新的宏观节点vμ，根据网络归并方法（具体方法参考网络归并）得到宏观网络B；
3）将vj所属的马尔可夫毯中的不在队列中的节点加入队列中，更新集合中节点的马尔可夫毯，如果节点的马尔可夫毯中包括vj节点，则将vj节点去除；
4）EI没增加则继续尝试与队列中的其他节点进行归并，直至队列中的节点都归并过，返回步骤2。
时间复杂度：O(N4)
缺点：
1. 时间复杂度比较高，不适合对规模大的网络进行粗粒化
2.4.1.2 谱分解方法
该方法是将原始网络对应的转移矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。
输入：原始包含N个节点的网络G，及对应的邻接矩阵A和距离超参ϵ；输出：粗粒化后的宏观网络G′，及对应的邻接矩阵B，以及从A到B的粗粒化方式
1. 针对邻接矩阵A，得到其转移矩阵W，然后进行矩阵的特征值分解，得到特征值集合与特征向量集合。
2. 构建新的有偏的特征向量集合（新的网络节点数量为N′=rank(A)），该集合中的每个向量被其对应的特征值所加权，同时去除了0特征值和特征向量。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应网络中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息。
3. 依据E′计算节点间的相似矩阵DN′×N′：
1）如果节点vi和vj分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cos相似性作为两者间的相似度dij和dji
2）否则将两个节点间的相似度设为无穷大∞（可以设个比较大的值，如10000）
4. 基于相似度矩阵DN′×N′和一个超参ϵ（需要线性搜索，可以选择EI最大的参数），使用OPTICS算法（是一种基于密度的聚类算法，旨在识别数据集中不同密度的聚类结构）进行聚类，输出对应超参ϵ下的聚类方式。
5. 根据聚类方案，归并根据网络归并方法（参见网络归并）得到宏观网络B。
时间复杂度：O(N3)
1. 对规模大的网络进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高；
2. 聚类算法所需的距离超参ϵ需要线性搜索，需要加入人为的先验知识。
2.4.1.3 梯度下降方法
该方法的核心是将粗粒化方案写成一个分组矩阵，同时将这个分组矩阵参数化，这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算EI。之后，使用自动微分方法执行梯度下降算法从而优化分组矩阵，以使得EI最大化。
输入：包含N个节点的原始网络G，其对应邻接矩阵为：A，粗粒化后的网络所包含的节点数：K；输出：宏观网络G′，对应的邻接矩阵为：B，以及对应的从A到B的粗粒化矩阵：M
1. 针对一个含有N个节点的网络A，随机初始化一个分组矩阵，K表示分组的大小，其中矩阵里面的每个元素miμ=Pr(vi∈vμ)，表示微观节点vi属于宏观节点vμ的概率；
2. 根据微观网络和分组矩阵构建宏观网络B，具体计算方法分为两个步骤：1）MTAM；2）归一化前一步骤得到的矩阵；
3. 使用带动量的梯度下降方法优化M，优化目标是最大化宏观网络的有效信息EI。
时间复杂度：O(N3)
缺点：
1. 初始化分组矩阵的选择，多次重复实验会得到不一样的结果；
2. 依赖神经网络的超参，如学习率、迭代次数等。
2.5 定义复杂网络中的因果涌现
有了每个网络的EI度量值，以及如何对任意的复杂网络进行粗粒化的方案，我们便可以给出复杂网络上因果涌现的具体量化了。
给定一个微观网络A以及通过上面的粗粒化方法得到对应的宏观网络B，我们可以定义复杂网络中的因果涌现的程度如下所示：
CE=EI(B)−EI(A)
3. 数值结果
2020年Klein等人在论文[2]中分析了随机（ER）、偏好依赖（PA）等人工网络，以及生物、社会、信息和技术4类真实网络的有效信息（EI）以及因果涌现（CE）。
3.1 人工网络
为了进一步探究人工网络随着模型参数和网络规模的变化，EI和CE如何变化，作者选取了两种经典网络ER（随机网络）和PA（偏好依赖网络）进行实验：
1）对于ER网络：有效信息的大小只依赖连接概率 p，并且随着网络规模的增大有效信息会收敛到−log2p。在某点之后，ER网络结构不会随着其规模的增加而包含更多的信息，这个相变点近似在网络的平均度 <k>=log2N 的位置，实验结果如图a所示。ER网络的相变点对应于随着连接概率增加出现巨连通集团时的对应概率。图b展示了不同节点规模下随着连接概率 p的增加，网络CE的变化，不同节点规模的网络的CE的变化趋势相同，先增加后降低到零，图中四条竖线对应于不同节点规模网络的相变点位置（<k>=1），同时这些相变点在CE达到峰值之后，这意味着能产生因果涌现最显著的ER网络是尚未形成巨连通集团的网络，这些网络往往是不连通的或者只是存在一些小的连通组或者存在小的树状的子图分组的网络。
2）对于PA网络：当偏好参数α<1.0时，有效信息的大小随着网络规模的增加而增大；α>1.0时，结论相反； α=1.0对应的无标度网络则是增长的临界边界，结果如图c所示。图d展示了PA网络随着偏好参数α的增加CE的变化趋势，CE先增加后减少，CE最终会收敛，当1<α<3时的网络的CE能达到峰值。随着α的增加，基于贪婪算法识别出来的EI最大的宏观网络的节点规模也会越来越小，可以分为微观尺度（−1<α<1），介观尺度（1<α<3）和宏观尺度（3<α<5），其中α=1对应无标度网络。
3.2 真实网络
对于真实网络来说，生物网络因为具有很大的噪声，所以有效性（
）最低，而技术类型网络是更稀疏、非简并的网络，因此，平均效率更高，节点关系更加具体，所以其有效性也最大，如图a所示。通过有效的粗粒化能去除系统的噪声，相较于技术类型网络，生物网络因果涌现最显著，如图b所示。
4. 应用
4.1 在元胞自动机上的应用
Varley等人[5]尝试将上述方法应用到元胞自动机系统中，将每个状态看成一个节点，每个状态会确定的得到下一个状态，从而构成一条有向边，最终可以构建一个有向的确定性网络。文中选择256种中的88个独特的离散元胞自动机，分为四类：静态的、周期性的、混沌的和复杂的，数据也横跨8个尺度，从5个元胞(25=32个状态)到12个元胞(212=4096个状态) 。实验发现因果涌现最强的元胞自动机规则对应的网络中会存在大量星型或者轮辐型的motif结构。此外，还得出下面四个结论：
1. 8%规则的状态图会坍塌成一个点 (属于三种规则的元胞自动机：混沌的、静态的或者振荡的模式)；
2. 43%规则的状态图存在因果涌现， 49%规则的状态图存在因果退化；
3. 存在17个规则对应第三、第四类元胞自动机，其中30%存在因果涌现， 70%出现因果退化；
4. 相同规则的元胞自动机在不同的尺寸下得到的CE结果大致相同；
4.2 在生物网络上的应用
进一步，Klein 等人将复杂网络中的因果涌现方法扩展到了更多的生物网络中。前文已经指出，生物网络具有更大的噪音，这使得我们很难理解其内部的运作原理，这种噪音一方面来自系统的固有噪音，另一方面是由于测量或观察引入的。Klein 等[6]进一步探索了生物网络中的噪声、简并性和确定性三者之间的关系以及具体含义，得出了一些有趣的结论。
例如，基因表达网络中的高确定性可以理解为一个基因几乎肯定会导致另一个基因的表达。同时生物系统在进化过程中也普遍存在高简并性现象。这两个因素共同导致，目前人们尚不清楚应该在何种尺度上分析生物系统才能更好理解它们的功能。Klein 等[7]分析了超过 1800 个物种的蛋白质相互作用网络，发现宏观尺度的网络具有更小的噪音和简并性，同时与不参与宏观尺度的节点相比，组成宏观尺度网络中的节点更具有弹性。因此，生物网络为了适应进化的要求，需要演化出宏观尺度以提高确定性来增强网络弹性以及提高信息传输的有效性。
Hoel 等在文章[8]中借助有效信息理论进一步研究了生物系统中的因果涌现。作者将有效信息应用到基因调控网络上，以识别最能提供信息的心脏发育模型从而控制哺乳动物的心脏发育。通过量化酿酒酵母基因网络的最大连通集团中的因果涌现，文章揭示了富有信息的宏观尺度在生物学中是普遍存在的，以及生命机制本身也经常运行在宏观尺度上。该文章也为生物学家提供了一种可计算的工具来识别最具有信息的宏观尺度，并且可以在此基础上建模、预测、控制和理解复杂的生物系统。
Swain 等在文章[9]中探索了蚁群的交互历史对任务分配和任务切换的影响，将蚁群用网络进行建模，使用有效信息研究噪声如何在蚂蚁之间传播。结果发现，蚁群之间历史交互程度影响任务的分配，并且具体交互中蚂蚁群体的类型决定了交互中的噪音。此外，即使当蚂蚁切换功能群时，蚁群涌现出来的凝聚力也能保证群体的稳定，同时不同功能蚁群在维持蚁群凝聚力方面也发挥着不同的作用。
代码：
参考：https://github.com/jkbren/einet
参考文献：
1. Hoel E P, Albantakis L, Tononi G. Quantifying causal emergence shows that macro can beat micro[J]. Proceedings of the National Academy of Sciences, 2013, 110(49): 19790-19795.
2. Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.
3. Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.
4. Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.
5. Varley, Thomas F. "Causal emergence in discrete and continuous dynamical systems." arXiv preprint arXiv:2003.13075 (2020).
6. Klein B, Swain A, Byrum T, et al. Exploring noise, degeneracy and determinism in biological networks with the einet package[J]. Methods in Ecology and Evolution, 2022, 13(4): 799-804.
7. Klein B, Hoel E, Swain A, et al. Evolution and emergence: higher order information structure in protein interactomes across the tree of life[J]. Integrative Biology, 2021, 13(12): 283-294.
8. Hoel E, Levin M. Emergence of informative higher scales in biological systems: a computational toolkit for optimal prediction and control[J]. Communicative & Integrative Biology, 2020, 13(1): 108-118.
9. Swain A, Williams S D, Di Felice L J, et al. Interactions and information: exploring task allocation in ant colonies using network analysis[J]. Animal Behaviour, 2022, 18969-81.
因果涌现读书会第五季
跨尺度、跨层次的涌现是复杂系统研究的关键问题，生命起源和意识起源这两座仰之弥高的大山是其代表。从2021年夏天至今，集智俱乐部已经陆续举办了四季「因果涌现」读书会，系统梳理了因果涌现理论的发展脉络，深入探讨了信息整合与信息分解的本质，并探索了在生物网络、脑网络、机器学习等跨学科领域的应用。此次因果涌现读书会第五季将追踪因果涌现领域的前沿进展，展示集智社区成员的原创性工作，希望探讨因果涌现理论、复杂系统的低秩表示理论、本征微观态理论之间的相通之处，对复杂系统的涌现现象有更深刻的理解。读书会已完结，现在报名可加入社群并解锁回放视频权限。
详情请见：
荟萃复杂系统前沿进展，集结因果涌现学术社区：因果涌现读书会第五季启动
"复杂 AI 次方"开放实验室招募
作为北师大系统科学学院教授、集智俱乐部与集智学园创始人、集智科学研究中心院长，张江从2003年开始长期从事有关复杂系统建模的工作。近年来，张江带领着北师大的研究组开始聚焦在基于新兴AI技术进行基于数据驱动的自动建模研究，并立志破解复杂系统的涌现之谜。我们希望可以有对复杂系统自动建模领域有热情，且认可这个领域发展前景的朋友一起来合作，促进这一领域的快速发展。我们希望这个叫做" Complexity AI "，中文叫做"复杂AI次方"的开放实验室，能够真正实现思想共享、资源共享、跨学科交叉，共同为复杂系统自动建模而奋进。
详情请见："复杂 AI 次方"开放实验室招募，挑战"涌现"难题
