复杂网络中的因果涌现

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
Jake（讨论 | 贡献）2024年12月22日 (日) 17:02的版本 （→‎梯度下降方法）
跳到导航 跳到搜索

复杂网络中的因果涌现是指对于一个复杂网络来说，在合适的粗粒化处理之后能得到一个宏观的网络，该网络能够比原始网络展现出更强的因果特性，即有效信息（Effective Information，简称EI）更高，则称原始网络发生了因果涌现。复杂网络是一种用图的方式建模复杂系统的模型，广泛应用于多种领域。这些网络通常由大量节点和具有一定随机性的连边组成，节点可以代表个体或元素，而边则代表它们之间的相互作用或联系。因果涌现理论最初是由Erik Hoel[1]等人提出，该理论使用有效信息来量化离散马尔科夫动力学系统的因果性强弱。2020 年，Klein 等人[2]尝试将因果涌现的概念扩展到复杂网络上，核心思路是将复杂网络上的随机游走模型视作一个马尔科夫链，从而应用有效信息比较粗粒化后的更宏观尺度的网络和原始网络上的有效信息（EI）有何变化，当粗粒化网络（宏观尺度）比原始网络 （微观尺度）具有更高的EI时，则说明该网络发生了因果涌现。

方法概述

2013年，Erik Hoel等人首次提出了因果涌现理论[1]，并使用有效信息（Effective Information, EI）来量化离散马尔科夫动力学系统的因果性强弱。2020年Klein等人尝试将因果涌现理论拓展到复杂网络[2]上。这一扩展的主要思路为将复杂网络转变为一个马尔科夫链，从而可以直接应用Erik Hoel等人的原始方法来判断因果涌现。具体地，Klein等人的方法包括如下几个步骤：

  1. 定义复杂网络上的动力学：引入随机游走子（Random Walker），该随机游走子可以沿着网络的连边随机跳转，从而构建该随机游走子的马尔科夫链（其中随机游走子的所有可能状态对应为复杂网络上的所有节点，而状态间的转移概率数值可以定义为每条有向连边的权值占比，即该边上的权重占该节点所有出边的权重的比例）；
  2. 定义复杂网络上的有效信息：基于随机游走子的概率转移矩阵计算有效信息，如此便可以将原本刻画马尔科夫链的有效信息指标扩展到复杂网络上；
  3. 粗粒化复杂网络（即将所有网络上的节点进行分组，转化为一系列宏观节点，并将连边也进行归并）得到宏观的复杂网络，并保证该转化后的网络满足动力学一致性，即保证粗粒化完以后的网络具有与原始网络相似的随机游走动力学；
  4. 对比微观网络和粗粒化后的宏观网络的有效信息，判断因果涌现是否发生，并计算因果涌现强度数值。

基本理论

基本思想

如何将Erik Hoel的因果涌现理论应用到复杂网络上？首先，Erik Hoel的理论是针对离散状态马尔科夫链进行展开的。因此，Klein等人需要将复杂网络转变为马尔科夫链。基本思想是，给网络赋予一套随机游走动力学，从而得到马尔科夫链和转移矩阵。其次，Hoel理论中的核心是有效信息指标，那么对该理论做延展的时候，也需要讨论一个网络的有效信息应该如何计算。再次，因果涌现现象是必须借助粗粒化策略来展现的，因此，Klein等人还要考虑如何粗粒化一个复杂网络。下面，本词条分别进行介绍。

随机游走动力学

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是转移概率矩阵（Transitional Probability Matrix，简称TPM）。然而对于复杂网络来说，给定一个已知网络，并不具有动力学，所以需要人为定义一套网络上的动力学。Klein等人借助随机游走子的概念，在网络上定义了一个随机游走动力学，该动力学可以被自然地用马尔科夫链来进行表示，并且该马尔科夫链的状态就对应了网络上的节点，而状态转移概率矩阵也可以自然地用网络的邻接矩阵的某种变换而得到。

具体的，假设我们考虑一个联通的无向图G，邻接矩阵为[math]A[/math]。假设图上有N个节点，分别表示为1,2,...,N。我们首先可以定义节点[math]\displaystyle{ i\in \{1,2,\cdots,N\} }[/math]到节点[math]\displaystyle{ j\in \{1,2,\cdots,N\} }[/math]的转移概率为[math]\displaystyle{ w_{ij} }[/math]，它满足：

[math]\displaystyle{ w_{ij}=\frac{a_{ij}}{\sum_{j=1}^N a_{ij}} }[/math]

这里，[math]a_{ij}\geq 0[/math]为G的邻接矩阵A的第i行，第j列元素，它对应连边[math]i\rightarrow j[/math]的权重。由于G是连通图，因此[math]\sum_{j=1}^N a_{ij}\neq 0[/math]。根据该定义，[math]w_{ij}[/math]自然满足归一化条件：

[math]\displaystyle{ \sum_{j=1}^Nw_{ij}=1 }[/math]

因此，我们可以直接定义一个马尔科夫链，其状态空间为[math]\{1,2,\cdots,N\}[/math]，从i状态到j状态的转移概率就是[math]w_{ij}[/math]，且对应的转移概率矩阵为：

[math]\displaystyle{ W=\{w_{ij}\}_{N\times N} }[/math]

定义有效信息

对于一般的N个状态的马尔科夫链，其概率转移矩阵为：[math]P[/math]，则其有效信息可以由下式计算(参见有效信息)：

[math]\displaystyle{ \begin{aligned} EI &\equiv I(S_{t+1};S_t|do(S_t\sim U))=\sum_{i=1}^ND_{KL}[P_i||\bar{P}]\\ &=\underbrace{-\langle H(P_i)\rangle}_{确定性项}+\underbrace{H(\bar{P})}_{非简并性项} \end{aligned} }[/math]

这里，[math]P_i[/math]为P的第i个行向量，[math]\bar{P}=\sum_{i=1}^N P_i/N[/math]为P的所有行向量求平均得到的平均向量。根据上式，EI可以分为两项，刚好对应两种计算下的Shannon信息熵，即[math]-\langle H(P_i)\rangle[/math]，它描述了P的确定性；还有[math]H(\bar{P})[/math]，它刻画了P的非简并性。

下面，我们把这个公式套用到复杂网络上的随机游走子定义的马尔科夫链上：

[math]\displaystyle{ \begin{aligned} {EI} &=\frac{1}{N}\sum_{i=1}^ND_{KL}[W_i||\bar{W}] \\ &= \frac{1}{N}\sum_{i=1}^N\sum_{j=1}^Nw_{ij}\log_2(w_{ij})-\frac{1}{N}\sum_{i=1}^N\sum_{j=1}^Nw_{ij}\log_2(\bar{w_j}) \\ &=\underbrace{-\langle H(W_i)\rangle}_{确定性项}+\underbrace{H(\bar{W})}_{非简并性项} \end{aligned} }[/math]

 

 

 

 

(1)

其中[math]\displaystyle{ W_i }[/math]为W的第i行构成的行向量，也对应了i节点跳出到其它节点的概率，[math]\bar{W}=\sum_{i=1}^N W_i/N[/math]为W的所有行向量求平均得到的平均向量, [math]\displaystyle{ \bar{w_j}=\frac{1}{N}\sum_{i=1}^N w_{ij} }[/math]，表示从任意节点跳转到节点[math]\displaystyle{ j }[/math]的所有概率的平均值。 同样，有效信息可以分解为确定性和简并性（参考有效信息）。

这两项分别是：

  1. 确定性为[math]\displaystyle{ -\langle H(W_i)\rangle }[/math]，其中，随机游走子从节点i跳出的不确定性可通过节点跳出概率向量[math]\displaystyle{ W_i }[/math]的香农熵定义，即[math]\displaystyle{ H(W_i) }[/math]，因此整个网络的确定性可通过所有节点香农熵的平均值取负数[math]\displaystyle{ -\langle H(W_i)\rangle }[/math]得到；
  2. 网络的非简并性为：[math]\displaystyle{ H(\bar{W}) }[/math]，它是所有节点跳出概率的平均值的熵。


除此之外，1式还可以用有效信息的原始定义，即do干预形式的互信息来理解。在初始时刻，我们假设随机游走子的初始状态分布为：

[math]\displaystyle{ S_0=(1/N,1/N,\cdots,1/N), }[/math]

这相当于游走子会等概率地分布在所有网络节点上，这种初始分布相当于我们对随机游走子的初始分布进行了do干预，把该分布干预为了均匀分布。计算在这个do干预下的t=1时刻和初始时刻两状态分布的互信息，我们同样可以得到1式。

1式就是任意复杂网络G的有效信息的定义式。

网络实例

首先，为了直观地看到网络的拓扑结构和有效信息、确定性、简并性等各个网络指标值之间的关系，下图展示了6种特殊的人工网络，并列出了：确定性、简并性以及有效信息EI值。下图展示的6个图中，有向环形网络（第一个图）的确定性最高，简并性最低，因此有效信息最大，而有向全连通图（第三个图）的确定性和简并性都最小，因此有效信息也最小，其余四个图的有效信息介于这两个图之间。

居左

此外，下面展示了五种经典的人工网络（完全图、星型图、环形图、BA(无标度网络)、ER(随机网络)）的确定性和简并性的大小分布，如下图所示，星型网络的确定性最高但是简并性也最高，因此有效信息也最低。同样完全图的确定性和简并性都最小，因此有效信息也最低。其余三个图的确定性较高，简并性较低，因此有效信息也较大。

居左

粗粒化复杂网络

为了识别复杂网络中的因果涌现，需要对原始网络做粗粒化，而粗粒化操作通常需要有两个步骤：

  1. 对原始网络的节点进行分组；
  2. 根据节点分组，对网络的节点和相应的连边进行归并，从而得到一个宏观网络。

最后，通过比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。

其中，节点分组的目的是确定哪些原始网络的节点应该被归并为一个宏观节点；而网络的归并的目的是根据分组和原网络的结构而得到一个更小的粗粒化的网络，但却并不丢失原始网络主要特征。

在Klein等人的论文[2]，以及Griebenow 等人[3]的文献中，作者们主要提出了三种粗粒化网络的方法，包括：贪婪算法、谱分解方法以及梯度下降方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则除了梯度下降方法以外，另外两个都采用了相同的处理手段，即HOM算法。

Klein等人[2]相当于使用贪婪算法对节点进行分组，但实质上该方法将分组和归并合并在一起执行了。这种方法对于大规模网络来说效率很低。所以，后来Griebenow[3]又提出了一种基于谱分解的方法来对原始网络节点进行分组，并将这种方法应用于偏好依附网络。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。

所有这些粗粒化方法都使用了同样的节点与连边的归并方法。这就是高阶依赖项建模（HOMs），其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性[4]。下面我们分别详细介绍这些粗粒化方法：

粗粒化算法

贪婪算法

该方法并不明显区分分组和归并，而是把两个步骤合并到了一起。

输入：具有N个节点的网络[math]G[/math]，其邻接矩阵为：[math]\displaystyle{ A }[/math]；输出：经过粗粒化后的宏观网络[math]G'[/math]，其邻接矩阵为：[math]\displaystyle{ B }[/math]，以及从[math]A[/math]到[math]B[/math]的粗粒化方式

  1. 初始化一个节点的集合[math]V[/math]，将[math]V[/math]中的每个节点所属的马尔可夫毯（这是一个节点的集合，既包括该节点的父节点、子节点以及子节点的其他父节点）也加入集合中；
  2. 遍历[math]G[/math]中的节点[math]\displaystyle{ \{v_i\}_{i=1}^N }[/math]（如果节点已经被合并成宏观节点则跳过），直到所有的节点遍历一遍停止：
  3. 初始化一个队列[math]\displaystyle{ Q }[/math], 取出集合V中[math]\displaystyle{ v_i }[/math]对应的马尔可夫毯中的所有节点，将其加入队列中；
  4. 初始时[math]\displaystyle{ v_{\mu} }[/math]=[math]\displaystyle{ v_i }[/math]，
  5. 分别尝试将 [math]\displaystyle{ v_{\mu} }[/math] 与 [math]\displaystyle{ v_j }[/math][math]\displaystyle{ \in Q }[/math]合并，形成一个新的宏观节点：[math]\displaystyle{ v_{\mu} }[/math]
    1. 执行网络归并算法，尝试归并网络（具体方法参考网络归并章节），并计算新网络的EI；
    2. 如果归并后的网络的EI增加了且满足粗粒化后的宏观网络与原始网络保持动力学一致性（具体方法参考consistency章节），就将这两个节点归并到一起组成新的宏观节点[math]\displaystyle{ v_{\mu} }[/math]，根据网络归并方法（具体方法参考网络归并章节）得到宏观网络[math]\displaystyle{ B }[/math]。
    3. 将[math]\displaystyle{ v_j }[/math]所属的马尔可夫毯中的不在队列中的节点加入队列中，更新集合中节点的马尔可夫毯，如果节点的马尔可夫毯中包括[math]\displaystyle{ v_j }[/math]节点，则将[math]\displaystyle{ v_j }[/math]节点去除
    4. EI没增加则继续尝试与队列中的其他节点进行归并，直至队列中的节点都归并过，返回步骤2

时间复杂度：[math]\displaystyle{ O(N^4) }[/math]

缺点：

  1. 时间复杂度比较高，不适合对规模大的网络进行粗粒化
谱分解方法

该方法是将原始网络对应的邻接矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。

输入：原始包含[math]N[/math]个节点的网络[math]G[/math]，及对应的邻接矩阵[math]\displaystyle{ A }[/math]和距离超参[math]\displaystyle{ \epsilon }[/math]；输出：粗粒化后的宏观网络[math]G'[/math]，及对应的邻接矩阵[math]\displaystyle{ B }[/math]，以及从[math]A[/math]到[math]B[/math]的粗粒化方式

  1. 针对邻接矩阵[math]\displaystyle{ A }[/math]，得到其转移矩阵[math]\displaystyle{ W }[/math]，然后进行矩阵的特征值分解，得到特征值集合[math]\displaystyle{ \Lambda=\{\lambda_i\}^N_{i=1} }[/math]与特征向量集合[math]\displaystyle{ E=\{e_i\}^N_{i=1} }[/math]。
  2. 构建新的有偏的特征向量集合[math]\displaystyle{ E’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1} }[/math]（新的网络节点数量为[math]\displaystyle{ N'=rank(A) }[/math]），该集合中的每个向量被其对应的特征值所加权，同时去除了0特征值和特征向量。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应网络中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
  3. 依据[math]\displaystyle{ E' }[/math]计算节点间的相似矩阵[math]\displaystyle{ D_{N'×N'} }[/math]：
    1. 如果节点[math]\displaystyle{ v_i }[/math]和[math]\displaystyle{ v_j }[/math]分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cos相似性作为两者间的相似度[math]\displaystyle{ d_{ij} }[/math]和[math]\displaystyle{ d_{ji} }[/math]
    2. 否则将两个节点间的相似度设为无穷大∞（可以设个比较大的值，如10000）
  4. 基于相似度矩阵[math]\displaystyle{ D_{N'×N'} }[/math]和一个超参[math]\displaystyle{ \epsilon }[/math]（需要线性搜索，可以选择EI最大的参数），使用OPTICS算法（是一种基于密度的聚类算法，旨在识别数据集中不同密度的聚类结构）进行聚类，输出对应超参[math]\displaystyle{ \epsilon }[/math]下的聚类方式。
  5. 根据聚类方案，归并根据网络归并方法（参见网络归并章节）得到宏观网络[math]\displaystyle{ B }[/math]

时间复杂度：[math]\displaystyle{ O(N^3) }[/math]

缺点：

  1. 对规模大的网络进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
  2. 聚类算法所需的距离超参[math]\displaystyle{ \epsilon }[/math]需要线性搜索，需要加入人为的先验知识
梯度下降方法

该方法的核心是将粗粒化方案写成一个分组矩阵，同时将这个分组矩阵参数化，这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算EI。之后，使用自动微分方法执行梯度下降算法从而优化分组矩阵，以使得EI最大化。

输入：包含[math]N[/math]个节点的原始网络[math]G[/math]，其对应邻接矩阵为：[math]\displaystyle{ A }[/math]，粗粒化后的网络所包含的节点数：[math]\displaystyle{ K }[/math]；输出：宏观网络[math]G'[/math]，对应的邻接矩阵为：[math]\displaystyle{ B }[/math]，以及对应的从[math]A[/math]到[math]B[/math]的粗粒化矩阵：[math]\displaystyle{ M }[/math]

  1. 针对一个含有[math]\displaystyle{ N }[/math]个节点的网络[math]\displaystyle{ A }[/math]，随机初始化一个分组矩阵[math]\displaystyle{ M\in \mathbb{R}^{N×K} }[/math]，[math]\displaystyle{ K }[/math]表示分组的大小，其中矩阵里面的每个元素[math]\displaystyle{ m_{iμ}=Pr⁡(v_i\in v_{\mu}) }[/math]，表示微节点[math]\displaystyle{ v_i }[/math]属于宏观节点[math]\displaystyle{ v_{\mu} }[/math]的概率
  2. 根据微观网络和分组矩阵构建宏观网络[math]\displaystyle{ B }[/math]，具体计算方法分为两个步骤：1）[math]\displaystyle{ M^TAM }[/math]；2）归一化前一步骤得到的矩阵
  3. 进行优化，优化目标是最大化宏观网络的有效信息EI，使用带动量的梯度下降方法优化[math]\displaystyle{ M }[/math]。

时间复杂度：[math]\displaystyle{ O(N^3) }[/math]

缺点：

  1. 初始化分组矩阵的选择，多次重复实验会得到不一样的结果
  2. 依赖神经网络的超参，如学习率、迭代次数等

节点合并方法

通过上面的网络粗粒化方法可以对节点进行分组，为了构建粗粒化后的宏观网络，需要将微观节点合并成宏观节点，同时需要计算宏观网络之间的连边，以及对应的转移概率。在上述三种方法中，前两种都使用了一种叫做高阶依赖项建模(HOMs)的方法来进行归并[4]，其目的是为了保证分组后的宏观网络和原始网络具有相似的随机游走动力学。

具体来说，不同类型的微观节点合并成宏观节点时边权有不同的处理方式：

1）下面图a展示了微观网络，其中待合并的节点（节点B，C，D）之间没有连边，且待合并节点都指向相同的输出节点（节点E），将节点B，C，D粗粒化成一个宏观节点[math]\displaystyle{ \mu }[/math]，如图b所示，同时需要将指向待合并节点的权重相加，待合并节点的输出权重取平均，具体宏观节点输出权重计算方法为：[math]\displaystyle{ w_{\mu,z}=\sum_{i \in S}w_{i,z}\frac{1}{N_S} }[/math]，其中[math]\displaystyle{ S }[/math]表示待合并节点集合，节点[math]\displaystyle{ i }[/math]表示待合并节点集合中的节点（如下图中的节点B，C，D），节点[math]\displaystyle{ z }[/math]表示待合并节点指向的节点（如下图中的节点E），[math]\displaystyle{ w_{i,z} }[/math]表示微观网络中的节点[math]\displaystyle{ i }[/math]和节点[math]\displaystyle{ z }[/math]之间的转移概率，[math]\displaystyle{ w_{\mu,z} }[/math]表示宏观网络中节点[math]\displaystyle{ \mu }[/math]和节点[math]\displaystyle{ z }[/math]之间的转移概率，[math]\displaystyle{ Ns }[/math]为待合并节点的数量；

居左

2）下面图a展示了待合并的节点（节点B，C）之间没有连边但是待合并节点指向多个输出节点的情况（节点D和E），将节点B，C粗粒化成一个宏观节点[math]\displaystyle{ \mu }[/math]，图b展示了对应的宏观网络，边权处理方式：需要将指向待合并节点的权重相加，待合并节点的输出权重按比例加权求和，具体宏观节点输出权重计算方法为：[math]\displaystyle{ w_{\mu,z}=\sum_{i \in S}w_{i,z}\frac{\sum_{j\rightarrow i}w_{ji}}{\sum_{j\rightarrow k\in S}w_{jk}} }[/math]，其中，[math]\displaystyle{ j\rightarrow i }[/math]表示节点j（如下面图a中的A节点）指向待合并节点集合中的节点i的边，[math]\displaystyle{ w_{\mu,z} }[/math]表示宏观网络中节点[math]\displaystyle{ \mu }[/math]和节点[math]\displaystyle{ z }[/math]之间的转移概率，这里[math]\displaystyle{ z }[/math]表示待合并节点指向的节点（如图a中的节点E）；

居左

3）下面图a展示了待合并的节点（节点B，C）之间存在连边且待合并节点指向多个输出节点的情况（节点D和E），如图a所示，将节点B，C粗粒化成一个宏观节点[math]\displaystyle{ \mu }[/math]，图b展示了对应的宏观网络，具体宏观节点输出权重计算方法为：[math]\displaystyle{ w_{\mu,z}=\sum_{i \in S}w_{i,z}\frac{\pi_i}{\sum_{k\in S}\pi_k} }[/math]，其中 [math]\displaystyle{ \pi_i }[/math]为节点[math]\displaystyle{ i }[/math]在节点平稳分布中的值，[math]\displaystyle{ w_{\mu,z} }[/math]表示宏观网络中节点[math]\displaystyle{ \mu }[/math]和节点[math]\displaystyle{ z }[/math]之间的转移概率；

居左

4）更为复杂的情况，如下图a所示，待合并的节点(B，C，D)三者之间存在循环结构，需要综合考虑方法2和方法3，将待合并的节点粗粒化为两个宏观节点[math]\displaystyle{ \mu_1 }[/math]和[math]\displaystyle{ \mu_2 }[/math]，来捕获延迟效果，其中宏观节点[math]\displaystyle{ \mu_1 }[/math]起到缓冲的效果，最终[math]\displaystyle{ \mu_1 }[/math]和[math]\displaystyle{ \mu_2 }[/math]组成的宏观节点具有记忆功能，如图b所示，宏观节点的出边权重同样结合方法2和方法3进行计算。具体计算时做了简化，[math]\displaystyle{ \mu_1 }[/math]和[math]\displaystyle{ \mu_2 }[/math]之间的转移概率设为1，[math]\displaystyle{ \mu_2 }[/math]的转移概率按照方法3进行计算；

居左

检验动力学的一致性

前面介绍了如何对一个复杂网络进行粗粒化的方式，有了新的粗粒化后的网络，我们便可以在粗粒化的网络上放置随机游走子，从而得到粗粒化后的概率转移矩阵。 然而，好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似的，那么如何保证这种相似性呢？Klein等人在论文[2]提出了一种动力学一致性检验方法，它的基本思想是通过比较粗粒化方案后未曾被分组归并的节点上的概率分布是否和原始的网络一致。此外，需要注意的是该方法主要应用于贪婪算法，作为节点合并的其中一个判别条件。

具体地，动力学的一致性检验可以进一步验证网络粗粒化方法的有效性。它的基本思想是，比较随机游走子在给定相同的初始分布下，宏微观网络的期望分布的KL散度。


计算动力学的一致性检验的具体步骤如下：

输入：微观网络[math]\displaystyle{ A }[/math]，宏观网络[math]\displaystyle{ B }[/math]以及总的转移时间步[math]\displaystyle{ T }[/math]；输出：动力学的不一致性（inconsistency）

  1. 初始化一个微观分布[math]\displaystyle{ S_m(0) }[/math]（分布长度和微观网络的大小一致，记为N），将分布中没有进行粗粒化的节点位置设为1，其余位置设为0；初始化一个宏观分布[math]\displaystyle{ S_M(0) }[/math]（分布长度和宏观网络的大小一致，记为M），同样将分布中还是原始微观网络中的节点位置设为1（分布中值为1的数量为Z），其余位置设为0；基于网络[math]\displaystyle{ A }[/math]和[math]\displaystyle{ B }[/math]分别得到转移概率矩阵[math]\displaystyle{ W_A }[/math]和[math]\displaystyle{ W_B }[/math]
  2. 迭代T步，得到从1到T步的宏微观转移概率矩阵：[math]\displaystyle{ \{W_A^t\}_{t=1}^T }[/math]和[math]\displaystyle{ \{W_B^t\}_{t=1}^T }[/math]
  3. 迭代1到T
    1. [math]\displaystyle{ S_m(t) = (W_A^t)^T S_m(0) }[/math]; 对[math]\displaystyle{ S_m(t) }[/math]进行归一化。初始化一个长度为Z+1的分布[math]\displaystyle{ P_{M|m}(t) }[/math]，表示微观节点分布叠加到相同宏观节点上的概率分布，其中[math]\displaystyle{ P_{M|m}(t) }[/math]的前Z个位置的数值等于[math]\displaystyle{ S_m(t) }[/math]中对应的Z个没有进行粗粒化的节点位置的值，[math]\displaystyle{ P_{M|m}(t) }[/math]中的第Z+1位置的数值等于[math]\displaystyle{ 1-\sum_{i=1}^Z p^i_{M|m}(t) }[/math]
    2. [math]\displaystyle{ S_M(t) = (W_B^t)^T S_M(0) }[/math]; 对[math]\displaystyle{ S_M(t) }[/math]进行归一化。初始化一个长度为Z+1的分布[math]\displaystyle{ P_M(t) }[/math]，表示宏观节点的概率分布, 其中[math]\displaystyle{ P_M(t) }[/math]的前Z个位置的数值等于[math]\displaystyle{ S_M(t) }[/math]中对应的Z个没有进行粗粒化的节点位置的值，[math]\displaystyle{ P_M(t) }[/math]中的第Z+1位置的数值等于[math]\displaystyle{ 1-\sum_{i=1}^Z p^i_M(t) }[/math]
  4. 使用[math]\displaystyle{ P_M(t) }[/math]和[math]\displaystyle{ P_{M|m}(t) }[/math]之间的KL散度来衡量其不一致性，若结果为零则动力学一致， 公式为：[math]\displaystyle{ inconsistency=\sum_{t=1}^T D_{KL}[P_{M|m}(t)||P_M(t)] }[/math]

实验发现，针对偏好依附网络来说，在不同节点规模以及参数下的粗粒化后的宏观网络的不一致性会随着迭代步数的增加都会收敛到0。


为了展示具体动力学一致性的计算流程，下图我们给了一个节点合并方法章节的第一个例子是如何计算动力学一致性的详细步骤，该例子中我们设置[math]\displaystyle{ T=2 }[/math]，图a和图b分别是微观和宏观网络的期望分布的计算过程。


居左

 

 

 

 

(consistency)

定义复杂网络中的因果涌现

有了每个网络的EI度量值，以及如何对任意的复杂网络进行粗粒化的方案，我们便可以给出复杂网络上因果涌现的具体量化了。

给定一个微观网络[math]\displaystyle{ A }[/math]以及通过上面的粗粒化方法得到对应的宏观网络[math]\displaystyle{ B }[/math]，我们可以定义复杂网络中的因果涌现的程度如下所示：

[math]\displaystyle{ CE = EI(B) - EI(A) }[/math]

数值结果

2020年Klein等人在论文[2]中分析了随机（ER）、偏好依赖（PA）等人工网络，以及生物、社会、信息和技术4类真实网络的有效信息（EI）以及因果涌现（CE）。

人工网络

为了进一步探究人工网络随着模型参数和网络规模的变化，EI和CE如何变化，作者选取了两种经典网络ER（随机网络）和PA（偏好依赖网络）进行实验：

1）对于ER网络：有效信息的大小只依赖连接概率 [math]\displaystyle{ p }[/math]，并且随着网络规模的增大有效信息会收敛到[math]\displaystyle{ -\log_2p }[/math]。在某点之后，ER网络结构不会随着其规模的增加而包含更多的信息，这个相变点近似在网络的平均度 [math]\displaystyle{ \lt k\gt }[/math]=[math]\displaystyle{ \log_2N }[/math] 的位置，实验结果如图a所示。ER网络的相变点对应于随着连接概率增加出现巨连通集团时的对应概率。图b展示了不同节点规模下随着连接概率 [math]\displaystyle{ p }[/math]的增加，网络CE的变化，不同节点规模的网络的CE的变化趋势相同，先增加后降低到零，图中四条竖线对应于不同节点规模网络的相变点位置（[math]\displaystyle{ \lt k\gt =1 }[/math]），同时这些相变点在CE达到峰值之后，这意味着能产生因果涌现最显著的ER网络是尚未形成巨连通集团的网络，这些网络往往是不连通的或者只是存在一些小的连通组或者存在小的树状的子图分组的网络。

2）对于PA 网络：当偏好参数[math]\displaystyle{ \alpha\lt 1.0 }[/math]时，有效信息的大小随着网络规模的增加而增大；[math]\displaystyle{ \alpha\gt 1.0 }[/math]时，结论相反； [math]\displaystyle{ \alpha=1.0 }[/math]对应的无标度网络则是增长的临界边界，结果如图c所示。图d展示了PA网络随着偏好参数[math]\displaystyle{ \alpha }[/math]的增加CE的变化趋势，CE先增加后减少，CE最终会收敛，当[math]\displaystyle{ 1\lt \alpha\lt 3 }[/math]时的网络的CE能达到峰值。随着[math]\displaystyle{ \alpha }[/math]的增加，基于贪婪算法识别出来的EI最大的宏观网络的节点规模也会越来越小，可以分为微观尺度（[math]\displaystyle{ -1\lt \alpha\lt 1 }[/math]），介观尺度（[math]\displaystyle{ 1\lt \alpha\lt 3 }[/math]）和宏观尺度（[math]\displaystyle{ 3\lt \alpha\lt 5 }[/math]），其中[math]\displaystyle{ \alpha=1 }[/math]对应无标度网络。

人工网络的有效信息

真实网络

对于真实网络，生物网络因为具有很大的噪声，所以有效性（[math]\displaystyle{ Effectiveness=\frac{EI}{\log N} }[/math]）最低，而技术类型网络是更稀疏、非简并的网络，因此，平均效率更高，节点关系更加具体，所有其有效性也最大，如图a所示。通过有效的粗粒化能去除系统的噪声，相较于技术类型网络，生物网络因果涌现最显著，如图b所示。

居左

应用

在元胞自动机上的应用

Varley等人[5]尝试将上述方法应用到元胞自动机系统中，将每个状态看成一个节点，每个状态会确定的得到下一个状态，从而构成一条有向边，最终可以构建一个有向的确定性网络。文中选择256种中的88个独特的离散元胞自动机，分为四类：静态的、周期性的、混沌的和复杂的，数据也横跨8个尺度，从5个元胞([math]\displaystyle{ 2^5=32 }[/math]个状态)到12个元胞([math]\displaystyle{ 2^{12}=4096 }[/math]个状态) 。实验发现因果涌现最强的元胞自动机规则对应的网络中会存在大量星型或者轮辐型的motif结构。此外，还得出下面四个结论：

  1. [math]\displaystyle{ 8\% }[/math]规则的状态图会坍塌成一个点(属于三种规则的元胞自动机：混沌的、静态的或者振荡的模式)；
  2. [math]\displaystyle{ 43\% }[/math]规则的状态图存在因果涌现， [math]\displaystyle{ 49\% }[/math]规则的状态图存在因果退化；
  3. 存在17个规则对应第三、第四类元胞自动机，其中[math]\displaystyle{ 30\% }[/math]存在因果涌现， [math]\displaystyle{ 70\% }[/math]出现因果退化；
  4. 相同规则的元胞自动机在不同的尺寸下得到的CE结果大致相同；

在生物网络上的应用

进一步，Klein 等人将复杂网络中的因果涌现方法扩展到了更多的生物网络中。前文已经指出，生物网络具有更大的噪音，这使得我们很难理解其内部的运作原理，这种噪音一方面来自系统的固有噪音，另一方面是由于测量或观察引入的。Klein 等[6]进一步探索了生物网络中的噪声、简并性和确定性三者之间的关系以及具体含义，得出了一些有趣的结论。


例如，基因表达网络中的高确定性可以理解为一个基因几乎肯定会导致另一个基因的表达。同时生物系统在进化过程中也普遍存在高简并性现象。这两个因素共同导致，目前人们尚不清楚应该在何种尺度上分析生物系统才能更好理解它们的功能。Klein 等[7]分析了超过 1800 个物种的蛋白质相互作用网络，发现宏观尺度的网络具有更小的噪音和简并性，同时与不参与宏观尺度的节点相比，组成宏观尺度网络中的节点更具有弹性。因此，生物网络为了适应进化的要求，需要演化出宏观尺度以提高确定性来增强网络弹性以及提高信息传输的有效性。


Hoel 等在文章[8]中借助有效信息理论进一步研究了生物系统中的因果涌现。作者将有效信息应用到基因调控网络上，以识别最能提供信息的心脏发育模型从而控制哺乳动物的心脏发育。通过量化酿酒酵母基因网络的最大联通集团中的因果涌现，文章揭示了富有信息的宏观尺度在生物学中是普遍存在的，以及生命机制本身也经常运行在宏观尺度上。该文章也为生物学家提供了一种可计算的工具来识别最具有信息的宏观尺度，并且可以在此基础上建模、预测、控制和理解复杂的生物系统。


Swain 等在文章[9]中探索了蚁群的交互历史对任务分配和任务切换的影响，将蚁群用网络进行建模，使用有效信息研究噪声如何在蚂蚁之间传播。结果发现，蚁群之间历史交互程度影响任务的分配，并且具体交互中蚂蚁群体的类型决定了交互中的噪音。此外，即使当蚂蚁切换功能群时，蚁群涌现出来的凝聚力也能保证群体的稳定，同时不同功能蚁群在维持蚁群凝聚力方面也发挥着不同的作用。

代码

参考：https://github.com/jkbren/einet

参考文献

  1. ↑ 1.0 1.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. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.
  3. ↑ 3.0 3.1 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. ↑ 4.0 4.1 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.

编者推荐

下面是一些链接能够帮助读者更好的了解因果涌现的相关信息：

因果涌现读书会

路径推荐

此词条由王志鹏、刘易明编写，张江、王志鹏、刘易明整理和审校。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=复杂网络中的因果涌现&oldid=40584”