马尔科夫链的粗粒化 - 版本历史

Liangjh：/* 高阶网络聚类 Higher-Order Macronodes (HOM) */

2026-08-07T07:54:08Z

高阶网络聚类 Higher-Order Macronodes (HOM)

Jake：/* 结合复杂网络配分函数与图机器学习的网络流方法 */

2026-07-14T01:15:54Z

结合复杂网络配分函数与图机器学习的网络流方法

Jake：/* 结合复杂网络配分函数与图机器学习的网络流方法 */

2026-07-14T01:06:31Z

结合复杂网络配分函数与图机器学习的网络流方法

Jake：/* 复杂网络中的粗粒化方法 */

2026-07-14T01:04:08Z

复杂网络中的粗粒化方法

2026年7月13日 (一) 02:30 Liangjh

2026-07-13T02:30:19Z

Liangjh：/* 合并复杂的分子组合 */

2026-07-13T02:28:58Z

合并复杂的分子组合

2026年7月13日 (一) 02:25 Liangjh

2026-07-13T02:25:33Z

2026年7月13日 (一) 02:24 Liangjh

2026-07-13T02:24:29Z

2026年7月13日 (一) 02:16 Liangjh

2026-07-13T02:16:24Z

Jake：/* 排队网络与计算机系统 */

2026-07-12T03:19:52Z

排队网络与计算机系统

@@ 第873行： / 第873行： @@
 按照该方法进行加和平均，得到的宏观和微观马尔科夫动力学就会满足一致条件。虽然这个方法直观明了，但它的问题在于：在系统演变到平稳分布之前，需要计算每个 <math>t</math> 时刻的状态分布概率 <math>s_j(t)</math>。在达到平稳分布前，直接使用<math>\pi</math>来聚合仍不会满足一致性，因此操作起来比较麻烦；而 HOM 的计算方式则可以解决这个问题。
-===高阶网络聚类 Higher-Order Macronodes (HOM)===
+===网络高阶依赖项聚合 Higher-Order Macronodes (HOM)===
 在 Klein 等人的论文<ref name=":19">Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.</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>来对网络节点进行聚合。其目的是保证聚合后的宏观网络与原始微观网络具有相同的随机游走动力学特性。该方法也可以用于合并马尔科夫链的状态。

@@ 第938行： / 第938行： @@
 下面介绍具体的方法。首先，我们用[[扩散方程]] <math>\frac{d\psi}{d\tau}=-L\psi</math> 来描述网络的扩散过程，其中[[拉普拉斯矩阵]] <math>L=D-A</math> 描述网络的拓扑结构，<math>A</math> 是邻接矩阵，<math>D</math> 是[[度矩阵]]。扩散方程的解为 <math>\psi_{\tau}=e^{-\tau L}\psi_0</math>，体现了信息随时间的演化，其中 <math>e^{-\tau L}</math> 为时间演化算子，<math>[e^{-\tau L}]_{ij}</math> 表示经过时间 <math>\tau</math> 后从节点 <math>j</math> 到节点 <math>i</math> 的流量。
-其次，利用[[复杂网络的配分函数]] <math>Z_{\tau}=Tr(e^{-\tau L})</math>，我们能量化矩阵的全局信息量<ref name='coarse-graining'/>。矩阵 <math>e^{-\tau L}</math> 的每个对角元 <math>[e^{-\tau L}]_{ii}</math> 是第 <math>i</math> 个节点的信息保留量，对所有对角元求和则能得到所有节点的信息保留量。
+其次，利用[[复杂网络的配分函数]] <math>Z_{\tau}=Tr(e^{-\tau L})</math>，我们能量化矩阵的全局信息量<ref name='coarse-graining'/>。矩阵 <math>e^{-\tau L}</math> 的每个对角元 <math>[e^{-\tau L}]_{ii}</math> 是第 <math>i</math> 个节点经过[math]\tau[/math]步信息扩散之后，该同一节点上的信息保留量，求矩阵的迹，即对所有对角元求和则能得到所有节点经过[math]\tau[/math]时间后的信息保留量。
-通过[[图神经网络]]（[[GNN]]）的[[消息传递]]机制，得到每个节点的向量表征，对节点向量应用[[Softmax]]函数，得到分组矩阵 <math>S_{N\times M}</math>，其中元素 <math>s_{ij}</math> 表示节点 <math>i</math> 分到第 <math>j</math> 个超级节点的概率。
+通过[[图神经网络]]（[[GNN]]）的[[消息传递]]机制，得到每个节点的向量表征，对节点向量应用[[Softmax函数]]，得到[[分组矩阵]] <math>S_{N\times M}</math>，其中元素 <math>s_{ij}</math> 表示节点 <math>i</math> 分到第 <math>j</math> 个超级节点的概率。这个[[分组矩阵]]就是一个候选的粗粒化策略。
-通过 <math>\hat{A}=\frac{M}{N}S^{T}AS</math> 得到[[宏观邻接矩阵]] <math>\hat{A}_{M\times M}</math>，其中 <math>A_{N\times N}</math> 原始网络的邻接矩阵。归一化[[配分函数]] <math>\frac{Z}{N}</math> 的[[平均绝对误差]]（MAE）作为训练[[图神经网络]]的损失函数，通过[[梯度下降]]优化GNN的参数。
+通过 <math>\hat{A}=\frac{M}{N}S^{T}AS</math> 得到[[宏观邻接矩阵]](即粗粒化后的矩阵） <math>\hat{A}_{M\times M}</math>，其中 <math>A_{N\times N}</math> 原始网络的邻接矩阵。归一化[[配分函数]] <math>\frac{Z}{N}</math> 的[[平均绝对误差]]（MAE）作为训练[[图神经网络]]的损失函数，通过[[梯度下降]]优化[[GNN]]的参数。
-网络规模从 <math>N</math> 压缩到 <math>N^{'}</math> 后，得到新的[[拉普拉斯矩阵]] <math>L^{'}</math> 和配分函数 <math>Z^{'}</math>，原始网络和压缩后的网络的配分函数的关系是 <math>Z=\gamma Z^{'}</math>，并且压缩后的配分函数和原始网络的配分函数要尽可能相似，不随时间变化而且误差最小。当 <math>\tau=0</math> 时，<math>Z=N,Z^{'}=N^{'}</math>，为了使之成立，<math>\gamma=\frac{N}{N^{'}}</math>，所以乘数的有效值为 <math>\frac{N}{N^{'}}</math>。
+网络规模从 <math>N</math> 压缩到 <math>N^{'}</math> 后，得到新的[[拉普拉斯矩阵]] <math>L^{'}</math> 和[[配分函数]] <math>Z^{'}</math>，原始网络和压缩后的网络的配分函数的关系应该是 <math>Z=\gamma Z^{'}</math>，这里[math]\gamma[/math]为一个乘数因子。我们可以通过设 <math>\tau=0</math> 时，得到<math>Z=N,Z^{'}=N^{'}</math>，为了使之成立，<math>\gamma=\frac{N}{N^{'}}</math>，即为乘数的有效值。
 马尔科夫链是描述状态仅依赖当前状态的[[随机过程]]，通过拉普拉斯矩阵与转移概率的关系，将上述方法应用到马尔科夫链中，在[[离散时间马尔科夫链]]中，转移概率矩阵为 <math>P</math>；在[[连续时间马尔科夫链]]中，<math>P(t)=e^{-tL}</math> 是经过时间 <math>t</math> 的转移概率矩阵。配分函数 <math>Z_t=Tr(e^{-tL})</math> 可以理解为马尔科夫链的所有状态的信息保留总和。

@@ 第934行： / 第934行： @@
 ===结合复杂网络配分函数与图机器学习的网络流方法===
-本节介绍的方法主要参考文章<ref name='coarse-graining'>Zhang, Zhang, et al. "Coarse-graining network flow through statistical physics and machine learning." Nature Communications 16.1 (2025): 1605.</ref>，该方法结合了[[复杂网络上的统计物理]]方法与图神经网络方法，从而对[[复杂网络]]进行粗粒化。其核心思想是，粗粒化前后两个网络的[[配分函数]]应该保持不变，将二者的误差作为损失函数，训练一个[[图神经网络]]，从而提炼出如何将大网络转化为粗粒化的小网络的映射方法。之所以将复杂网络的配分函数作为一个重要的评价指标，是因为该函数不仅可以体现网络的拓扑结构特征，也能够反映网络的动力学特征，因而反映整体网络功能。实验证明，这套粗粒化网络的方法可以应用到大量的真实网络中，并得到了良好的效果<ref name='coarse-graining'/>。
+本节介绍的方法主要参考文章<ref name='coarse-graining'>Zhang, Zhang, et al. "Coarse-graining network flow through statistical physics and machine learning." Nature Communications 16.1 (2025): 1605.</ref>，该方法结合了[[复杂网络上的统计物理]]方法与图神经网络方法，从而对[[复杂网络]]进行粗粒化。其核心思想是，粗粒化前后两个网络的[[配分函数]]应该保持不变，将二者的误差作为损失函数，训练一个[[图神经网络]]，从而提炼出如何将大网络转化为粗粒化的小网络的映射方法。之所以将[[复杂网络的配分函数]]作为一个重要的评价指标，是因为该函数不仅可以体现网络的拓扑结构特征，也能够反映网络在多个时间尺度上的动力学特征，因而反映整体网络功能。实验证明，这套粗粒化网络的方法可以应用到大量的真实网络中，并得到了良好的效果<ref name='coarse-graining'/>。
 下面介绍具体的方法。首先，我们用[[扩散方程]] <math>\frac{d\psi}{d\tau}=-L\psi</math> 来描述网络的扩散过程，其中[[拉普拉斯矩阵]] <math>L=D-A</math> 描述网络的拓扑结构，<math>A</math> 是邻接矩阵，<math>D</math> 是[[度矩阵]]。扩散方程的解为 <math>\psi_{\tau}=e^{-\tau L}\psi_0</math>，体现了信息随时间的演化，其中 <math>e^{-\tau L}</math> 为时间演化算子，<math>[e^{-\tau L}]_{ij}</math> 表示经过时间 <math>\tau</math> 后从节点 <math>j</math> 到节点 <math>i</math> 的流量。

@@ 第908行： / 第908行： @@
 [[复杂网络]]中的粗粒化方法非常多，常见思路包括：根据[[社团结构]]或[[模块结构]]合并节点，根据[[谱嵌入]]或[[扩散距离]]寻找动力学上相近的节点，根据[[网络模体]]或[[功能单元]]识别可重复的局部结构，也可以利用[[复杂网络上的统计物理]]方法、[[图神经网络]]等方法，在保留全局流量、扩散过程或拓扑功能的前提下压缩网络。不同方法关注的对象并不完全相同：有的主要保留拓扑结构，有的保留[[随机游走]]或[[扩散动力学]]，有的则保留功能模块和多尺度组织。
-这些方法与[[马尔科夫链]]粗粒化有两层联系。首先，[[马尔科夫链]]本身可以看作一种加权有向复杂网络：状态对应节点，转移概率对应有向边权。因此，我们可以先把马尔科夫链的状态转移图视为一个网络，并使用一些有向图方法来生成候选划分。例如，[[社团检测]]会倾向于合并转移联系密集、概率流交换频繁的一组状态；[[谱聚类]]会根据大尺度连通结构或扩散结构合并状态；[[角色相似性]]方法则会把具有相似入流和出流模式的状态放在一起。如果暂时忽略方向、权重或具体转移概率，则可以把马尔科夫链退化为一个普通的无向拓扑网络。这样做会丢掉一部分动力学信息，但也能使用更广泛的复杂网络粗粒化工具，如无向社团检测、模块识别、[[网络模体]]识别和[[层次聚类]]等。此时得到的划分可作为候选分组，再根据[[成块性]]、[[稳态流]]、[[EI]]、[[动力学可逆性]]等指标进行选择。
+这些方法与[[马尔科夫链]]粗粒化有两层联系。首先，[[马尔科夫链]]本身可以看作一种加权有向复杂网络：状态对应节点，转移概率对应有向边权。因此，我们可以先把马尔科夫链的状态转移图视为一个网络，并使用一些有向图方法来生成候选划分。例如，[[社团检测]]会倾向于合并转移联系密集、概率流交换频繁的一组状态；[[谱聚类]]会根据大尺度连通结构或扩散结构合并状态；[[角色相似性]]方法则会把具有相似入流和出流模式的状态放在一起。如果暂时忽略方向、权重或具体转移概率，则可以把马尔科夫链退化为一个普通的无向拓扑网络。这样做会丢掉一部分动力学信息，但也能使用更广泛的[[复杂网络粗粒化]]工具，如无向社团检测、模块识别、[[网络模体]]识别和[[层次聚类]]等。此时得到的划分可作为候选分组，再根据[[成块性]]、[[稳态流]]、[[EI]]、[[动力学可逆性]]等指标进行选择。
-其次，许多复杂网络上都可以定义[[随机游走]]、扩散或传播动力学。一旦规定游走规则，网络就会诱导出一个[[转移概率矩阵]] <math>P</math>，也就是一条马尔科夫链。于是，复杂网络的粗粒化可以转化为马尔科夫链的状态粗粒化：我们不仅关心哪些节点拓扑上相近，也关心哪些节点在随机游走中具有相似的动力学作用。在这个意义上，[[成块性]]可以检验合并后的宏观节点是否仍然形成封闭马尔科夫链；[[稳态流矩阵]]可以刻画长期概率流通道；[[谱方法]]可以寻找扩散尺度上的相似节点；HOM 则可以在节点合并时保留随机游走的高阶路径依赖。因此，马尔科夫链粗粒化工具可以反过来用于复杂网络上的随机游走动力学压缩。
+其次，许多复杂网络上都可以定义[[随机游走]]、扩散或[[传播动力学]]。一旦规定游走规则，网络就会诱导出一个[[转移概率矩阵]] <math>P</math>，也就是一条[[马尔科夫链]]。于是，复杂网络的粗粒化可以转化为马尔科夫链的状态粗粒化：我们不仅关心哪些节点拓扑上相近，也关心哪些节点在随机游走中具有相似的动力学作用。在这个意义上，[[成块性]]可以检验合并后的宏观节点是否仍然形成封闭马尔科夫链；[[稳态流矩阵]]可以刻画长期概率流通道；[[谱方法]]可以寻找扩散尺度上的相似节点；[[HOM]] 则可以在节点合并时保留随机游走的高阶路径依赖。因此，马尔科夫链粗粒化工具可以反过来用于复杂网络上的随机游走动力学压缩。
-本节只简要介绍几类与马尔科夫链关系较近的复杂网络粗粒化方法，分别对网络上的随机游走动力学、[[扩散动力学]]，和多尺度功能模块进行粗粒化。虽然这些方法并不直接给出马尔科夫链的最优粗粒化，但可以为状态划分、[[网络归并]]和动力学保真提供有用的启发。
+本节只简要介绍几类与马尔科夫链关系较近的[[复杂网络粗粒化]]方法，分别对网络上的[[随机游走动力学]]、[[扩散动力学]]，和多尺度功能模块进行粗粒化。虽然这些方法并不直接给出马尔科夫链的最优粗粒化，但可以为状态划分、[[网络归并]]和动力学保真提供有用的启发。
 ==复杂网络的粗粒化方法==

@@ 第1,002行： / 第1,002行： @@
 ====合并复杂的分子组合 ====
-代表文献：Ganguly, Petrov & Koeppl, 2014, Markov chain aggregation and its applications to combinatorial reaction networks<ref name=":app0">Ganguly, Arnab, Tatjana Petrov, and Heinz Koeppl. "Markov chain aggregation and its applications to combinatorial reaction networks." Journal of mathematical biology 69.3 (2014): 767-797.</ref>；Petrov, 2019, Markov chain aggregation and its application to rule-based modeling.<ref name=":app2">Petrov, Tatjana. "Markov chain aggregation and its application to rule-based modelling." Modeling Biomolecular Site Dynamics: Methods and Protocols. New York, NY: Springer New York, 2019. 297-313.</ref>
+代表文献：Ganguly, Petrov & Koeppl, 2014, Markov chain aggregation and its applications to combinatorial reaction networks<ref name=":app2">Ganguly, Arnab, Tatjana Petrov, and Heinz Koeppl. "Markov chain aggregation and its applications to combinatorial reaction networks." Journal of mathematical biology 69.3 (2014): 767-797.</ref>；Petrov, 2019, Markov chain aggregation and its application to rule-based modeling.<ref name=":app3">Petrov, Tatjana. "Markov chain aggregation and its application to rule-based modelling." Modeling Biomolecular Site Dynamics: Methods and Protocols. New York, NY: Springer New York, 2019. 297-313.</ref>
 细胞内部有大量化学反应。一个蛋白质可以被磷酸化，可以和另一个蛋白质结合，也可以从复合物中解离。由于分子可能有多个结合位点和修饰位点，所有可能的分子组合会非常多，即使反应规则本身不复杂，状态数也可能爆炸式增长。在这类模型中，微观状态是系统在某一时刻的完整化学状态。例如，一个微观状态需要说明：系统里有哪些分子、每种分子有多少个、哪些分子彼此结合、哪些位点被修饰等。每一次反应都会把系统从一个微观状态带到另一个微观状态。如果每个反应都有发生速率，那么整个系统就形成一个[[连续时间马尔科夫链]]。
@@ 第1,012行： / 第1,012行： @@
 ====合并物种集合====
-代表文献：Mu et al., 2018, Organisation-Oriented Coarse Graining and Refinement of Stochastic Reaction Networks.<ref name=":app3">Mu, Chunyan, et al. "Organisation-oriented coarse graining and refinement of stochastic reaction networks." IEEE/ACM Transactions on Computational Biology and Bioinformatics 15.4 (2018): 1152-1166.</ref>
+代表文献：Mu et al., 2018, Organisation-Oriented Coarse Graining and Refinement of Stochastic Reaction Networks.<ref name=":app4">Mu, Chunyan, et al. "Organisation-oriented coarse graining and refinement of stochastic reaction networks." IEEE/ACM Transactions on Computational Biology and Bioinformatics 15.4 (2018): 1152-1166.</ref>
 另外，在一些化学反应系统中，研究者关心的不是每一种分子此刻具体有多少个，而是系统最终会维持哪些物种。这里的“物种”可以理解为反应网络中的化学成分，例如某种分子、离子或复合物。“chemical organisation” 可以翻译为“[[化学组织]]”，指一组在反应中保持封闭、并且有可能自我维持的物种集合。通俗地说，如果系统进入某个化学组织，其中的物种可以通过反应互相支持，不会立刻消失，也不会不断产生完全不属于这个集合的外部物种。
@@ 第1,025行： / 第1,025行： @@
 === [[网络社团检测]] ===
-代表文献：Piccardi, 2011, Finding and Testing Network Communities by Lumped Markov Chains.<ref name=":app4">Piccardi, Carlo. "Finding and testing network communities by lumped Markov chains." PloS one 6.11 (2011): e27028.</ref>
+代表文献：Piccardi, 2011, Finding and Testing Network Communities by Lumped Markov Chains.<ref name=":app5">Piccardi, Carlo. "Finding and testing network communities by lumped Markov chains." PloS one 6.11 (2011): e27028.</ref>
 网络社团检测的目标是找出网络中联系紧密的节点集合。例如，在社交网络中，社团可能是一群经常互动的人；在网页网络中，社团可能是一组主题相近的网站；在交通网络中，社团可能是一组流动联系紧密的区域。
@@ 第1,047行： / 第1,047行： @@
 === 海洋流与空间流动 ===
-代表文献：Faccin, Schaub & Delvenne, 2021, State aggregations in Markov chains and block models of networks. <ref name=":app5">Faccin, Mauro, Michael T. Schaub, and Jean-Charles Delvenne. "State aggregations in Markov chains and block models of networks." Physical Review Letters 127.7 (2021): 078301.</ref>
+代表文献：Faccin, Schaub & Delvenne, 2021, State aggregations in Markov chains and block models of networks. <ref name=":app6">Faccin, Mauro, Michael T. Schaub, and Jean-Charles Delvenne. "State aggregations in Markov chains and block models of networks." Physical Review Letters 127.7 (2021): 078301.</ref>
 在海洋、空气污染、生态扩散等系统中，研究者常关心物质如何在空间中移动。例如，海水、漂浮物、污染物或生物幼体可能随着流场移动。如果把空间切成许多小格子，就可以描述一个粒子从一个格子移动到另一个格子的概率。
@@ 第1,059行： / 第1,059行： @@
 === [[Agent-based model]] 与[[观点动力学]] ===
-代表文献：Banisch, Lima & Araújo, 2012, Agent Based Models and Opinion Dynamics as Markov Chains.<ref name=":app6">Banisch, Sven, Ricardo Lima, and Tanya Araújo. "Agent based models and opinion dynamics as Markov chains." Social Networks 34.4 (2012): 549-561.</ref>
+代表文献：Banisch, Lima & Araújo, 2012, Agent Based Models and Opinion Dynamics as Markov Chains.<ref name=":app7">Banisch, Sven, Ricardo Lima, and Tanya Araújo. "Agent based models and opinion dynamics as Markov chains." Social Networks 34.4 (2012): 549-561.</ref>
 [[Agent-based model]]是一种个体层面的建模方法。模型中有许多个体，每个个体按照简单规则行动或改变状态。例如，在观点动力学中，每个人可能支持观点 0 或观点 1，并受到邻居影响而改变观点。虽然个体规则简单，但所有个体组合起来以后，系统状态会非常多。
@@ 第1,069行： / 第1,069行： @@
 === [[排队网络]]与计算机系统 ===
-代表文献：Song & Takahashi, 1991, Aggregate Approximation for Tandem Queueing Systems with Production Blocking<ref name=":app7">Song, Yu, and Yukio Takahashi. "Aggregate approximation for tandem queueing systems with production blocking." Journal of the Operations Research Society of Japan 34.3 (1991): 329-353.</ref> ；Gambin, Krzyżanowski & Pokarowski, 2008, Aggregation algorithms for perturbed Markov chains with applications to networks modeling<ref name=":app8">Gambin, Anna, Piotr Krzyżanowski, and Piotr Pokarowski. "Aggregation algorithms for perturbed Markov chains with applications to networks modeling." SIAM Journal on Scientific Computing 31.1 (2008): 45-73.</ref>
+代表文献：Song & Takahashi, 1991, Aggregate Approximation for Tandem Queueing Systems with Production Blocking<ref name=":app8">Song, Yu, and Yukio Takahashi. "Aggregate approximation for tandem queueing systems with production blocking." Journal of the Operations Research Society of Japan 34.3 (1991): 329-353.</ref> ；Gambin, Krzyżanowski & Pokarowski, 2008, Aggregation algorithms for perturbed Markov chains with applications to networks modeling<ref name=":app9">Gambin, Anna, Piotr Krzyżanowski, and Piotr Pokarowski. "Aggregation algorithms for perturbed Markov chains with applications to networks modeling." SIAM Journal on Scientific Computing 31.1 (2008): 45-73.</ref>
 排队系统和计算机系统经常可以用马尔科夫链建模。例如，一个工厂生产线有多个工位，每个工位前面可能有队列；一个服务器系统有多个任务等待处理。系统的完整状态需要记录每个队列有多少任务、每个服务器是否忙碌、是否发生阻塞等。

@@ 第990行： / 第990行： @@
 === [[分子构象动力学]] ===
-代表文献： Kube & Weber, 2007, A coarse graining method for the identification of transition rates between molecular conformations
+代表文献： Kube & Weber, 2007, A coarse graining method for the identification of transition rates between molecular conformations. <ref name=":10">Kube, Susanna, and Marcus Weber. "A coarse graining method for the identification of transition rates between molecular conformations." The Journal of chemical physics 126.2 (2007).</ref>
 在分子动力学中，蛋白质、小分子或药物分子会不断改变自己的空间形状。例如，蛋白质可能会折叠、展开，或者在几种相对稳定的形状之间切换。这里的“构象”指的是分子的空间形状：同一个分子中，原子连接关系没有变，但整体姿态、弯曲方式或折叠方式不同，就对应不同构象。

@@ 第1,156行： / 第1,156行： @@
 因此，马尔科夫链粗粒化并不是简单地“减少状态数”，而是在减少状态数的同时，尽量保留对研究问题重要的转移动力学。不同应用中的“重要信息”并不相同：它可以是亚稳态结构、目标变量、社团保持性、长期流动信息、宏观社会变量，也可以是系统性能指标。
 =参考文献=
 <references />