复杂网络中的因果涌现

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

历史渊源

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

1. 定义复杂网络上的动力学：引入随机游走子，该随机游走子可以沿着网络的连边随机跳转，从而构建该随机游走子的马尔科夫链（其中随机游走子的所有可能状态对应为复杂网络上的不同节点，而状态间的转移概率数值可以定义为每个节点的度的倒数）；
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列元素。由于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式还可以用有效信息的原始定义来理解。在初始时刻，我们假设随机游走子的初始状态分布为：

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

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

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

粗粒化复杂网络

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。Klein等人利用贪婪算法构建了宏观尺度的网络，发现对于大规模网络其效率很低。Griebenow 等人提出了一种基于谱分解的方法，并应用于偏好依附网络。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。

贪婪算法

输入：原始网络[math]\displaystyle{ A }[/math]；输出：宏观网络[math]\displaystyle{ B }[/math]以及对应的粗粒化方式

1. 初始化一个字典，将每个节点所属的邻域(马尔可夫毯）加入字典中
2. 遍历节点[math]\displaystyle{ \{v_i\}_{i=1}^N }[/math]（如果节点已经被合并成宏观节点则跳过），直到所有的节点遍历一遍停止：
3. 初始化一个队列, 取出字典中[math]\displaystyle{ v_i }[/math]对应的邻域，将其加入队列[math]\displaystyle{ Q }[/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]合并：
   1. 如果合并后的网络的EI增加了，就将这两个节点合并组成新的宏观节点[math]\displaystyle{ v_{\mu} }[/math]，得到宏观网络[math]\displaystyle{ B }[/math]，将[math]\displaystyle{ v_j }[/math]所属的邻域中的不在队列中的节点加入队列中，更新字典中节点的邻域，如果节点邻域中包括[math]\displaystyle{ v_j }[/math]节点，则将[math]\displaystyle{ v_j }[/math]节点去除
   2. EI没增加则继续尝试与队列中的其他节点进行合并，直至队列中的节点都合并过，返回步骤2

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

谱分解方法

输入：原始网络[math]\displaystyle{ A }[/math]和距离超参[math]\displaystyle{ \epsilon }[/math]；输出：宏观网络[math]\displaystyle{ B }[/math]以及对应的粗粒化方式

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

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

梯度下降方法

输入：原始网络[math]\displaystyle{ A }[/math]和分组大小[math]\displaystyle{ K }[/math]；输出：宏观网络[math]\displaystyle{ 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]
3. 进行优化，优化目标是最大化宏观网络的有效信息EI，使用带动量的梯度下降方法优化[math]\displaystyle{ M }[/math]。

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

困难：

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

宏节点合并方法

通过上面的网络粗粒化方法可以对节点进行分组，从而可以构建宏观网络。将微观节点合并成宏观节点时，对应宏观网络的转移概率矩阵也要进行相应的处理。通过使用高阶节点显式地对高阶依赖项建模（HOMs），保证分组后的宏观网络和原始网络具有相同的随机游走动力学。

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

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

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

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

4）更为复杂的情况，如下图a所示，待合并的节点(B，C，D)三者之间存在环路，需要综合考虑方法2和方法3，将待合并的节点粗粒化为两个宏观节点[math]\displaystyle{ \mu|j }[/math]和[math]\displaystyle{ \mu|\pi }[/math]，如图b所示，宏观节点的出边权重同样结合方法2和方法3进行计算

检验动力学的一致性

动力学的一致性检验可以进一步验证HOMs方法的有效性。它的基本思想是，比较随机游走子在给定相同的初始分布下，宏微观网络的期望分布的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], 初始化一个长度为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], 初始化一个长度为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。

数值结果

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

人工网络

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所示。

代码

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

编者推荐

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

因果涌现读书会

• 因果涌现读书会第一季第七期：复杂网络中的因果涌现

路径推荐

• 张江老师根据因果涌现读书会第一季梳理的关于因果涌现的学习路径：https://pattern.swarma.org/article/153
• 张江老师根据因果涌现读书会梳理的关于因果涌现的入门学习路径：https://pattern.swarma.org/article/296

---

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

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