复杂网络中的因果涌现

因果涌现理论最初是由Erick Hoel等人提出，使用有效信息来量化离散马尔可夫动力学的因果性强弱。2020 年，Klein 等人尝试将该方法应用到复杂网络中，然后为了量化复杂网络中的因果涌现，需要解决如下问题：定义网络中的动力学，定义有效信息，网络如何粗粒化等问题。

定义网络中的动力学

由于因果涌现理论量化的是系统的动力学，对于网络来说，需要定义网络节点的动力学，可以借助随机游走子定义网络中的马尔可夫链，从而假定网络中的每个节点具有随机游走动力学。

有效信息定义

将随机游走子放在节点上，等价于对节点做干预[math]\displaystyle{ do(·) }[/math]，基于随机游走概率可以定义节点的转移概率矩阵，将网络节点类比系统状态构建网络动力学的有效信息；建立了有效信息与网络连通性的联系。网络中的连通性可通过节点出边与入边的权重的不确定性表征 2 项衡量：1）节点输出的不确定性可通过节点出权的香农熵定义，即[math]\displaystyle{ H(W_i^{out}) }[/math]，因此整个网络的不确定性可通过[math]\displaystyle{ \lt H(W_i^{out})\gt }[/math]得到；2）基于网络的出边权重分布计算，[math]\displaystyle{ H(\lt W_i^{out}\gt ) }[/math]反映了确定性如何在网络中分布. 通过这2项就可得到复杂网络中的有效信息定义,[math]\displaystyle{ I_E=H(\lt W_i^{out}\gt )-\lt H(W_i^{out})\gt }[/math]。 进一步，有效信息可以分解为确定性和简并性。

网络中的粗粒化

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及机器学习方法。

贪婪算法

1. 初始化一个队列，随机选择一个节点[math]\displaystyle{ v_i }[/math](没有访问过的), 将[math]\displaystyle{ v_i }[/math]所属的邻域(马尔可夫毯 )[math]\displaystyle{ B_{v_i} }[/math] 中的节点加入队列中
2. 初始时[math]\displaystyle{ v_{\mu} }[/math]=[math]\displaystyle{ v_i }[/math]
3. 分别尝试将 [math]\displaystyle{ v_{\mu} }[/math] 与 [math]\displaystyle{ v_j }[/math][math]\displaystyle{ \in }[/math][math]\displaystyle{ B_{v_i} }[/math] 合并：
   1. 如果合并后的网络的EI增加了，就将这两个节点合并组成新的宏观节点[math]\displaystyle{ v_{\mu} }[/math]，将[math]\displaystyle{ v_j }[/math]所属的邻域中的不在队列中的节点加入队列中；
   2. EI没增加则继续尝试与队列中的其他节点进行合并，直至队列中的节点都合并过，返回步骤1

谱分解方法

1. 输入一个网络[math]\displaystyle{ A_m }[/math],得到其转移矩阵[math]\displaystyle{ T_{Am} }[/math], 然后进行矩阵的特征值分解，得到特征值[math]\displaystyle{ Λ={λ_i} }[/math]与特征向量[math]\displaystyle{ E={e_i} }[/math], 构建新的[math]\displaystyle{ E’=\{λ_ie_i|λ_i≠0\} }[/math](新的网络节点数量为[math]\displaystyle{ N' }[/math])
2. 依据[math]\displaystyle{ E' }[/math]计算节点间的距离矩阵[math]\displaystyle{ D_{N'×N'} }[/math]：
   1. 如果节点[math]\displaystyle{ v_i }[/math]和[math]\displaystyle{ v_j }[/math]分别在对方的邻域中(马尔可夫毯)，则使用cosine计算两个节点的相似性作为距离；
   2. 否则将两个节点间的距离设为无穷大∞(1000)
3. 基于距离矩阵[math]\displaystyle{ D_{N'×N'} }[/math]，使用OPTICS算法进行聚类，同一类里的节点进行粗粒化作为一个宏观节点，存在距离超参[math]\displaystyle{ \epsilon }[/math]，需要线性搜索，选择EI最大的参数

机器学习方法

EI是不可微的，所以梯度下降法不能直接适用。 针对一个含有[math]\displaystyle{ 𝑛 }[/math]个节点的网络，定义一个分组矩阵[math]\displaystyle{ M\in R^{n×k} }[/math]，其中[math]\displaystyle{ m_{iμ}=Pr⁡(v_i\in v_{\mu}) }[/math]，表示微节点[math]\displaystyle{ v_i }[/math]属于宏观节点[math]\displaystyle{ v_{\mu} }[/math]的概率，然后根据微观网络和分组矩阵构建宏观网络，优化目标是最大化宏观网络的有效信息EI，使用带动量的梯度下降方法优化M。

困难：

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

通过对节点进行分组，并构建宏观网络。将微观节点合并成宏观节点时，对应宏观网络的转移概率矩阵也要进行相应的处理. 通过使用高阶节点显式地对高阶依赖项建模（HOMs），保证分组后的宏观网络和原始网络具有相同的随机游走动力学。具体来说，不同的类型为微观网络合并成宏观节点时边权有不同的处理方式，包括四种处理方法，1）待合并的节点之间没有连边，且输入节点都指向待合并节点，待合并节点都指向相同节点，如图b，输入权重相加，输出权重取平均；2）待合并的节点之间没有连边时，待合并节点指向多个节点时，如图c，输入边权加和，出边的边权按比例加权求和；3）当节点间存在连边时，如图d，需要计算待合并节点的平稳分布，然后采用方法2的方式计算；4）更为复杂的情况，如图e，综合考虑方法2和方法3。

动力学一致性检验

动力学的一致性检验可以进一步验证了 HOMs 方法的有效性，公式如下所示，比较宏微观网络节点在不同时刻的概率分布的KL散度之和。实验发现在不同节点规模以及参数下的偏好依附网络的宏观网络的不一致性随着时间的增加都会收敛到0.

[math]\displaystyle{ inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)] }[/math]

实验分析

该工作在随机（ER）、偏好依赖（PA）等人工网络，以及 4 类真实网络中做了试验。 对于 ER 网络，有效信息的大小只依赖连接概率 [math]\displaystyle{ p }[/math]，并且随着网络规模的增大收敛到[math]\displaystyle{ -log_2p }[/math]。在某点之后，随机网络结构不会随着其规模的增加而包含更多的信息，这个相变点近似在网络的平均度 [math]\displaystyle{ \lt k\gt }[/math]=[math]\displaystyle{ log_2N }[/math] 的位置。随着 ER 网络连接概率的增大，巨连通集团相变点位置对应出现。对于PA 网络：[math]\displaystyle{ \alpha\lt 1.0 }[/math]时，有效信息的大小随着网络规模的增加而增大；[math]\displaystyle{ \alpha\gt 1.0 }[/math]时，结论相反； [math]\displaystyle{ \alpha=1.0 }[/math]对应的无标度网络则是 增长的临界边界。对于真实网络，他们发现，生物网络因为具有很大的噪声，所以有效信息最低，通过有效的粗粒化能去除这些噪声。相较于其他类型，因果涌现最显著；技术类型网络是更稀疏、非退化的网络，因此，平均效率更高，节点关系更加具体，所有有效信息也最多。此外，还利用贪婪算法构建了宏观尺度的网络，对 于大规模网络其效率很低。Griebenow 等提出了一种基于谱聚类的方法识别偏好依附网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱聚类算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著.

代码

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