复杂网络中的因果涌现 - 版本历史

相信未来：/* 谱分解方法 */

2024-12-23T07:48:50Z

谱分解方法

相信未来：/* 真实网络 */

2024-12-23T07:25:54Z

真实网络

相信未来：/* 在生物网络上的应用 */

2024-12-23T07:21:16Z

在生物网络上的应用

相信未来：/* 粗粒化复杂网络 */

2024-12-23T07:13:00Z

粗粒化复杂网络

相信未来：/* 定义有效信息 */

2024-12-23T06:31:45Z

定义有效信息

相信未来：/* 随机游走动力学 */

2024-12-23T06:20:03Z

随机游走动力学

相信未来：/* 随机游走动力学 */

2024-12-23T06:17:34Z

随机游走动力学

相信未来：/* 随机游走动力学 */

2024-12-23T06:17:15Z

随机游走动力学

相信未来：/* 谱分解方法 */

2024-12-23T03:42:33Z

谱分解方法

相信未来：/* 贪婪算法 */

2024-12-23T03:42:14Z

贪婪算法

@@ 第129行： / 第129行： @@
 =====谱分解方法=====
-该方法是将原始网络对应的邻接矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。
+该方法是将原始网络对应的转移矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。
 '''输入'''：原始包含[math]N[/math]个节点的网络[math]G[/math]，及对应的邻接矩阵<math>A</math>和距离超参<math>\epsilon</math>；'''输出'''：粗粒化后的宏观网络[math]G'[/math]，及对应的邻接矩阵<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式

@@ 第182行： / 第182行： @@
 === 真实网络 ===
-对于真实网络，生物网络因为具有很大的噪声，所以有效性（<math>Effectiveness=\frac{EI}{\log N}</math>）最低，而技术类型网络是更稀疏、非简并的网络，因此，平均效率更高，节点关系更加具体，所以其有效性也最大，如图a所示。通过有效的粗粒化能去除系统的噪声，相较于技术类型网络，生物网络因果涌现最显著，如图b所示。
+对于真实网络来说，生物网络因为具有很大的噪声，所以有效性（<math>Effectiveness=\frac{EI}{\log N}</math>）最低，而技术类型网络是更稀疏、非简并的网络，因此，平均效率更高，节点关系更加具体，所以其有效性也最大，如图a所示。通过有效的粗粒化能去除系统的噪声，相较于技术类型网络，生物网络因果涌现最显著，如图b所示。
 [[文件:真实网络的有效信息1.png|居左|800x800像素]]

←上一版本		2024年12月23日 (一) 07:21的版本
第202行：		第202行：


−	Hoel 等在文章<ref>Hoel E, Levin M. Emergence of informative higher scales in biological systems: a computational toolkit for optimal prediction and control[J]. Communicative & Integrative Biology, 2020, 13(1): 108-118.</ref>中借助[[有效信息]]理论进一步研究了生物系统中的因果涌现。作者将有效信息应用到[[基因调控网络]]上，以识别最能提供信息的心脏发育模型从而控制哺乳动物的心脏发育。通过量化酿酒酵母基因网络的[[~~最大联通集团~~]]中的因果涌现，文章揭示了富有信息的宏观尺度在生物学中是普遍存在的，以及生命机制本身也经常运行在宏观尺度上。该文章也为生物学家提供了一种可计算的工具来识别最具有信息的宏观尺度，并且可以在此基础上建模、预测、控制和理解复杂的生物系统。	+	Hoel 等在文章<ref>Hoel E, Levin M. Emergence of informative higher scales in biological systems: a computational toolkit for optimal prediction and control[J]. Communicative & Integrative Biology, 2020, 13(1): 108-118.</ref>中借助[[有效信息]]理论进一步研究了生物系统中的因果涌现。作者将有效信息应用到[[基因调控网络]]上，以识别最能提供信息的心脏发育模型从而控制哺乳动物的心脏发育。通过量化酿酒酵母基因网络的[[最大连通集团]]中的因果涌现，文章揭示了富有信息的宏观尺度在生物学中是普遍存在的，以及生命机制本身也经常运行在宏观尺度上。该文章也为生物学家提供了一种可计算的工具来识别最具有信息的宏观尺度，并且可以在此基础上建模、预测、控制和理解复杂的生物系统。

@@ 第101行： / 第101行： @@
 其中，节点分组的目的是确定哪些原始网络的节点应该被归并为一个宏观节点；而网络的归并的目的是根据分组和原网络的结构而得到一个更小的粗粒化的网络，但却并不丢失原始网络主要特征。
-在Klein等人的论文<ref name=":0"/>，以及Griebenow 等人<ref name=":Griebenow">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>的文献中，作者们主要提出了三种粗粒化网络的方法，包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则除了梯度下降方法以外，另外两个都采用了相同的处理手段，即[[HOM算法]]。
+在Klein等人的论文<ref name=":0"/>，以及Griebenow 等人<ref name=":Griebenow">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>的文献中，作者们主要提出了三种粗粒化网络的方法，包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则除了梯度下降方法以外，另外两个都采用了相同的处理手段，即高阶依赖项建模（[[HOMs]]）<ref name="HOMs">Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>，其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性。
 Klein等人<ref name=":0" />相当于使用贪婪算法对节点进行分组，但实质上该方法将分组和归并合并在一起执行了。这种方法对于大规模网络来说效率很低。所以，后来Griebenow<ref name=":Griebenow"/>又提出了一种基于谱分解的方法来对原始网络节点进行分组，并将这种方法应用于[[偏好依附网络]]。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。
-所有这些粗粒化方法都使用了同样的节点与连边的归并方法。这就是高阶依赖项建模（[[HOMs]]），其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性<ref name="HOMs">Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。下面我们分别详细介绍这些粗粒化方法：
+下面我们分别详细介绍这些粗粒化方法：
 ====粗粒化算法====

@@ 第64行： / 第64行： @@
 |{{EquationRef|1}}}}
-其中<math>W_i</math>为W的第i行构成的行向量，也对应了i节点跳出到其它节点的概率，[math]\bar{W}=\sum_{i=1}^N W_i/N[/math]为W的所有行向量求平均得到的平均向量, <math>\bar{w_j}=\frac{1}{N}\sum_{i=1}^N w_{ij}</math>，表示从任意节点跳转到节点<math>j</math>的所有概率的平均值。 同样，有效信息可以分解为[[确定性]]和[[简并性]]（参考[[有效信息]]）。
+其中<math>W_i</math>为W的第i行构成的行向量，也对应了i节点跳转到其它节点的概率，[math]\bar{W}=\sum_{i=1}^N W_i/N[/math]为W的所有行向量求平均得到的平均向量, <math>\bar{w_j}=\frac{1}{N}\sum_{i=1}^N w_{ij}</math>，表示从任意节点跳转到节点<math>j</math>的所有概率的平均值。 同样，有效信息可以分解为[[确定性]]和[[简并性]]（参考[[有效信息]]）。
 这两项分别是：

@@ 第20行： / 第20行： @@
 由于因果涌现理论量化的是系统的动力学，对于离散马尔科夫动力学来说就是[[转移概率矩阵]]（Transitional Probability Matrix，简称TPM）。然而对于复杂网络来说，给定一个已知网络，并不具有动力学，所以需要人为定义一套网络上的动力学。Klein等人借助[[随机游走子]]的概念，在网络上定义了一个[[随机游走动力学]]，该动力学可以被自然地用[[马尔科夫链]]来进行表示，并且该马尔科夫链的状态就对应了网络上的节点，而状态转移概率矩阵也可以自然地用网络的[[邻接矩阵]]的某种变换而得到。
-具体的，假设我们考虑一个连通的图G，邻接矩阵为[math]A[/math]。假设图上有N个节点，分别表示为1,2,...,N。我们首先可以定义节点<math>i\in \{1,2,\cdots,N\}</math>到节点<math>j\in \{1,2,\cdots,N\}</math>的转移概率为<math>w_{ij}</math>，它满足：
+具体的，假设我们考虑一个连通图G，邻接矩阵为[math]A[/math]。假设图上有N个节点，分别表示为1,2,...,N。我们首先可以定义节点<math>i\in \{1,2,\cdots,N\}</math>到节点<math>j\in \{1,2,\cdots,N\}</math>的转移概率为<math>w_{ij}</math>，它满足：
 <math>

@@ 第139行： / 第139行： @@
 ## 否则将两个节点间的相似度设为无穷大∞（可以设个比较大的值，如10000）
 # 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的聚类算法，旨在识别数据集中不同密度的聚类结构）进行聚类，输出对应超参<math>\epsilon</math>下的聚类方式。
-# 根据聚类方案，归并根据网络归并方法（参见{{EquationNote|网络归并}}章节）得到宏观网络<math>B</math>
+# 根据聚类方案，归并根据网络归并方法（参见[[网络归并]]）得到宏观网络<math>B</math>
 时间复杂度：<math>O(N^3)</math>

@@ 第118行： / 第118行： @@
 # 初始时<math>v_{\mu}</math>=<math>v_i</math>，
 # 分别尝试将 <math>v_{\mu}</math> 与 <math>v_j</math><math>\in Q</math>合并，形成一个新的宏观节点：<math>v_{\mu}</math>
-## 执行网络归并算法，尝试归并网络（具体方法参考{{EquationNote|网络归并}}章节），并计算新网络的EI；
+## 执行网络归并算法，尝试归并网络（具体方法参考[[网络归并]]），并计算新网络的EI；
-## 如果归并后的网络的EI增加了且满足粗粒化后的宏观网络与原始网络保持动力学一致性（具体方法参考[[动力学的一致性检验]]），就将这两个节点归并到一起组成新的宏观节点<math>v_{\mu}</math>，根据网络归并方法（具体方法参考{{EquationNote|网络归并}}章节）得到宏观网络<math>B</math>。
+## 如果归并后的网络的EI增加了且满足粗粒化后的宏观网络与原始网络保持动力学一致性（具体方法参考[[动力学的一致性检验]]），就将这两个节点归并到一起组成新的宏观节点<math>v_{\mu}</math>，根据网络归并方法（具体方法参考[[网络归并]]）得到宏观网络<math>B</math>。
 ## 将<math>v_j</math>所属的马尔可夫毯中的不在队列中的节点加入队列中，更新集合中节点的马尔可夫毯，如果节点的马尔可夫毯中包括<math>v_j</math>节点，则将<math>v_j</math>节点去除
 ## EI没增加则继续尝试与队列中的其他节点进行归并，直至队列中的节点都归并过，返回步骤2