2,435
个编辑
更改
→粗粒化复杂网络
===粗粒化复杂网络===
===粗粒化复杂网络===
为了识别复杂网络中的因果涌现，需要有两个步骤：1）对网络进行[[粗粒化]]；2）根据分组方式构建宏观网络，然后比较宏观网络与微观网络的有效信息，判断能否发生因果涌现。粗粒化方法包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。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>提出了一种基于谱分解的方法，并应用于[[偏好依附网络]]。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。为了考虑分组后的宏观网络与原始的网络具有相同的动力学，使用高阶节点显式地对高阶依赖项建模（[[HOMs]]）<ref>Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。下面分别介绍这两个步骤：
====贪婪算法====
====粗粒化算法====
贪婪算法
输入：具有N个节点的网络[math]G[/math]，其邻接矩阵为：<math>A</math>；输出：经过粗粒化后的宏观网络[math]G'[/math]，其节点数依赖于算法，其邻接矩阵为：<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式
输入：具有N个节点的网络[math]G[/math]，其邻接矩阵为：<math>A</math>；输出：经过粗粒化后的宏观网络[math]G'[/math]，其节点数依赖于算法，其邻接矩阵为：<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式
# 初始化一个节点的集合[math]V[/math]，将[math]V[/math]中的每个节点所属的邻域（[[马尔可夫毯]]）也加入集合中；
# 初始化一个节点的集合[math]V[/math]，将[math]V[/math]中的每个节点所属的邻域（[[马尔可夫毯]]）也加入集合中；
# 时间复杂度比较高，不适合对规模大的网络进行粗粒化
# 时间复杂度比较高，不适合对规模大的网络进行粗粒化
谱分解方法
输入：原始包含[math]N[/math]个节点的网络[math]G[/math]，及对应的邻接矩阵<math>A</math>和距离超参<math>\epsilon</math>；输出：粗粒化后的宏观网络[math]G'[/math]，其节点数为[math]N'[/math]，及对应的邻接矩阵<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式
输入：原始包含[math]N[/math]个节点的网络[math]G[/math]，及对应的邻接矩阵<math>A</math>和距离超参<math>\epsilon</math>；输出：粗粒化后的宏观网络[math]G'[/math]，其节点数为[math]N'[/math]，及对应的邻接矩阵<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
梯度下降方法
输入：包含[math]N[/math]个节点的原始网络[math]G[/math]，其对应邻接矩阵为：<math>A</math>，粗粒化后的网络所包含的节点数：<math>K</math>；输出：宏观网络[math]G'[/math]，对应的邻接矩阵为：<math>B</math>，以及对应的从[math]A[/math]到[math]B[/math]的粗粒化矩阵：<math>M</math>
输入：包含[math]N[/math]个节点的原始网络[math]G[/math]，其对应邻接矩阵为：<math>A</math>，粗粒化后的网络所包含的节点数：<math>K</math>；输出：宏观网络[math]G'[/math]，对应的邻接矩阵为：<math>B</math>，以及对应的从[math]A[/math]到[math]B[/math]的粗粒化矩阵：<math>M</math>