更改

==粗粒化复杂网络==  

==粗粒化复杂网络==  

为了识别复杂网络中的因果涌现，需要对网络进行粗粒化，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。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>提出了一种基于谱分解的方法识别偏好依赖网络中的因果涌现。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间最少，同时找到宏观网络的因果涌现也更加显著。

为了识别复杂网络中的因果涌现，需要对网络进行[[粗粒化]]，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：贪婪算法、谱分解方法以及梯度下降方法。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>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>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>：

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

## 如果节点<math>v_i</math>和<math>v_j</math>分别在对方的邻域中(马尔可夫毯)，则使用[[cosine]]计算两个节点的相似性作为距离

## 如果节点<math>v_i</math>和<math>v_j</math>分别在对方的邻域中(马尔可夫毯)，则使用[[cosine]]计算两个节点的相似性作为距离

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

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

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

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

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

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