更改

2020年Klein等人在尝试将因果涌现理论应用于[[复杂网络]]<ref name=":0" />，并提出了一系列技术方法，主要步骤为：定义复杂网络节点动力学（引入随机游走子，假定每个节点具有随机游走动力学），定义有效信息（基于节点的概率转移矩阵，类比[[状态转移矩阵]]的有效信息计算方式），粗粒化复杂网络（考虑不同的粗粒化方法，将微观节点粗粒化为宏观节点）、检验动力学的一致性（保证粗粒化完以后的网络具有相同的随机游走动力学）。

−

==~~定义复杂网络节点动力学~~==

+

==基本理论==

−

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是[[状态转移矩阵]]TPM，然而对于复杂网络来说，给定一个网络已知不具有动力学，需要人为定义复杂网络节点的动力学，可以借助[[随机游走子]]定义网络中的[[马尔科夫链]]，从而假定网络中的每个节点具有[[随机游走动力学]]，并且此时的转移矩阵也是节点间的状态转移。

+

===基本思想===

−

==定义有效信息==

+

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

+

===随机游走动力学===

+

由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是[[状态转移矩阵]]TPM，然而对于复杂网络来说，给定一个已知网络不具有动力学，需要人为定义复杂网络节点的动力学，可以借助[[随机游走子]]定义网络中的[[马尔科夫链]]，从而假定网络中的每个节点具有[[随机游走动力学]]，并且此时的转移矩阵也是节点间的状态转移。

+

===定义有效信息===

将随机游走子放在节点上，等价于对节点做[[干预]]<math>do(·) </math>，基于随机游走概率可以定义节点的转移概率矩阵，建立了有效信息与[[网络连通性]]的联系，将网络节点类比系统状态构建网络动力学的有效信息。

第33行：第39行：

其中，对于一个无权图来说转移概率<math>w_{ij}</math>等于节点<math>i</math>的度的倒数，对于一个加权图来说转移概率<math>w_{ij}</math>等于节点<math>i</math>出边权重值的归一化，<math>W_i^{out}</math>由<math>v_i</math>和它的邻居<math>v_j</math>之间的转移概率<math>w_{ij}</math>组成，如果没有从<math>v_i</math>到<math>v_j</math>的边，则<math>w_{ij}=0</math>，对于每个<math>W_i^{out}</math>，<math>∑_jW_i^{out}=1</math>。<math>W_j=\frac{1}{N}\sum_{i=1}^N w_{ij}</math>，表示节点的平均分布。同样进一步，有效信息可以分解为[[确定性]]和[[简并性]]。

−

==粗粒化复杂网络==

+

===粗粒化复杂网络===

为了识别复杂网络中的因果涌现，需要对网络进行[[粗粒化]]，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。Klein等人<ref name=":0" />利用贪婪算法构建了宏观尺度的网络，发现对于大规模网络其效率很低。Griebenow 等人<ref>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.</ref>提出了一种基于谱分解的方法识别偏好依赖网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著。

−

===贪婪算法===

+

====贪婪算法====

# 初始化一个队列，随机选择一个节点<math>v_i</math>(没有访问过的), 将<math>v_i</math>所属的邻域([[马尔可夫毯]] )<math>B_{v_i}</math> 中的节点加入队列中

第45行：第51行：

时间复杂度：<math>O(N^4)</math>

−

===谱分解方法===

+

====谱分解方法====

# 输入一个网络<math>A_m</math>，得到其[[转移矩阵]]<math>T_{Am}</math>，然后进行矩阵的[[特征值分解]]，得到特征值<math>Λ=\{λ_i\}</math>与特征向量<math>E=\{e_i\}</math>，构建新的<math>E’=\{λ_ie_i|λ_i≠0\}</math>(新的网络节点数量为<math>N'</math>)

# 依据<math>E'</math>计算节点间的距离矩阵<math>D_{N'×N'}</math>：

第53行：第59行：

时间复杂度：<math>O(N^3)</math>

−

===梯度下降方法===

+

====梯度下降方法====

由于EI是不可微的，所以梯度下降法不能直接适用。

第64行：第70行：

# 依赖神经网络的超参，如学习率、迭代次数等

−

=== 宏节点合并方法 ===

+

====宏节点合并方法====

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

第79行：第85行：

[[文件:网络节点边权合并示意图.png|替代=网络节点合并方式|居左|600x600像素|网络节点合并方式]]

−

==检验动力学的一致性==

+

====检验动力学的一致性====

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

第86行：第92行：

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

−

==~~复杂网络中的有效信息~~==

+

==数值结果==

2020年Klein等人在一篇论文<ref name=":0" />中分析了随机（ER）、偏好依赖（PA）等人工网络，以及生物、社会、信息和技术4类真实网络的有效信息（EI）。

Jake

668

个编辑

更改

复杂网络中的因果涌现 (查看源代码)

2024年9月1日 (日) 15:16的版本