3,094
个编辑
更改
→应用
=应用=
=应用=
[[马尔科夫链粗粒化]]的应用工作虽然来自不同领域，但结构和思路都非常相似：
# 先有一个微观马尔科夫链；
# 先有一个微观[[马尔科夫链]]；
# 微观状态数量很多，或者观测上太细；
# 微观状态数量很多，或者观测上太细；
# 根据动力学相似性、观测等价性、研究目标或系统结构，把微观状态合并；
# 根据动力学相似性、观测等价性、研究目标或系统结构，把微观状态合并；
=== 分子构象动力学 ===
=== [[分子构象动力学]] ===
代表文献： 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
分子动力学模拟会产生大量构象。为了建立马尔科夫链，研究者通常先把连续的构象空间离散化：把相近的分子形状归成许多小的构象簇，每个构象簇看作一个微观状态。然后，根据模拟轨迹估计转移概率：如果分子现在处在微观构象 i，过一段时间后转到微观构象 j 的概率是多少？这些概率组成转移矩阵 P，于是分子在不同构象簇之间的随机跳转就可以近似看作马尔科夫链。
分子动力学模拟会产生大量构象。为了建立马尔科夫链，研究者通常先把连续的构象空间离散化：把相近的分子形状归成许多小的构象簇，每个构象簇看作一个微观状态。然后，根据模拟轨迹估计转移概率：如果分子现在处在微观构象 i，过一段时间后转到微观构象 j 的概率是多少？这些概率组成转移矩阵 P，于是分子在不同构象簇之间的随机跳转就可以近似看作马尔科夫链。
粗粒化的目的，是把大量细小构象合并成少数几个有物理意义的“大状态”。例如，一个蛋白质可能有展开态、半折叠中间态和完全折叠态。每个大状态内部仍包含许多细微不同的构象。这类粗粒化主要依据转移动力学，而不是单纯依据几何形状。如果一批微观构象之间经常互相转移，但很少跳到外面，那么它们可以合并成一个宏观状态，称为“[[亚稳态构象]]”。“亚稳态”可以理解为：系统会在这个状态附近停留较久，但最终仍可能跳到别的状态。Kube 和 Weber 的工作使用 PCCA+ 方法。该方法通过分析转移矩阵，找出在较长时间内不容易离开的状态集合。粗粒化之后，研究者可以估计这些大状态之间的转移速率，例如蛋白质从展开态变成折叠态大约需要多久。
=== 生化反应网络 ===
=== [[生化反应网络]] ===
====合并复杂的分子组合 ====
====合并复杂的分子组合 ====
代表文献：Ganguly, Petrov & Koeppl, 2014, Markov chain aggregation and its applications to combinatorial reaction networks；Petrov, 2019, Markov chain aggregation and its application to rule-based modelling
代表文献：Ganguly, Petrov & Koeppl, 2014, Markov chain aggregation and its applications to combinatorial reaction networks；Petrov, 2019, Markov chain aggregation and its application to rule-based modelling
细胞内部有大量化学反应。一个蛋白质可以被磷酸化，可以和另一个蛋白质结合，也可以从复合物中解离。由于分子可能有多个结合位点和修饰位点，所有可能的分子组合会非常多，即使反应规则本身不复杂，状态数也可能爆炸式增长。在这类模型中，微观状态是系统在某一时刻的完整化学状态。例如，一个微观状态需要说明：系统里有哪些分子、每种分子有多少个、哪些分子彼此结合、哪些位点被修饰等。每一次反应都会把系统从一个微观状态带到另一个微观状态。如果每个反应都有发生速率，那么整个系统就形成一个[[连续时间马尔科夫链]]。
完整微观链通常太大，难以直接计算。例如，要求未来某个时间系统处于某类状态的概率，或者求长期稳态分布，都可能因为状态数太多而不可行。同时，研究者往往并不关心所有细节，而只关心某些关键变量，例如某个蛋白是否被激活。因此，可以把对目标变量没有影响或近似没有影响的细节合并掉。粗粒化依据可以是研究目标、分子结构、反应网络对称性，或者成块性条件。粗粒化后得到的宏观状态可能是：“关键蛋白未激活”、“关键蛋白已激活但未结合配体”、“关键蛋白已激活且结合配体”等。
完整微观链通常太大，难以直接计算。例如，要求未来某个时间系统处于某类状态的概率，或者求长期稳态分布，都可能因为状态数太多而不可行。同时，研究者往往并不关心所有细节，而只关心某些关键变量，例如某个蛋白是否被激活。因此，可以把对目标变量没有影响或近似没有影响的细节合并掉。粗粒化依据可以是研究目标、分子结构、反应网络对称性，或者成块性条件。粗粒化后得到的宏观状态可能是：“关键蛋白未激活”、“关键蛋白已激活但未结合配体”、“关键蛋白已激活且结合配体”等。
代表文献：Mu et al., 2018, Organisation-Oriented Coarse Graining and Refinement of Stochastic Reaction Networks
代表文献：Mu et al., 2018, Organisation-Oriented Coarse Graining and Refinement of Stochastic Reaction Networks
另外，在一些化学反应系统中，研究者关心的不是每一种分子此刻具体有多少个，而是系统最终会维持哪些物种。这里的“物种”可以理解为反应网络中的化学成分，例如某种分子、离子或复合物。“chemical organisation” 可以翻译为“化学组织”，指一组在反应中保持封闭、并且有可能自我维持的物种集合。通俗地说，如果系统进入某个化学组织，其中的物种可以通过反应互相支持，不会立刻消失，也不会不断产生完全不属于这个集合的外部物种。
另外，在一些化学反应系统中，研究者关心的不是每一种分子此刻具体有多少个，而是系统最终会维持哪些物种。这里的“物种”可以理解为反应网络中的化学成分，例如某种分子、离子或复合物。“chemical organisation” 可以翻译为“[[化学组织]]”，指一组在反应中保持封闭、并且有可能自我维持的物种集合。通俗地说，如果系统进入某个化学组织，其中的物种可以通过反应互相支持，不会立刻消失，也不会不断产生完全不属于这个集合的外部物种。
这类模型的微观状态通常是每种物种的分子数。例如，若系统中有三种物种 A,B,C，一个微观状态可以写成 (n_A,n_B,n_C)。每次反应都会改变这些分子数，例如 A+B\rightarrow C 会减少 A 和 B，增加 C。若反应随机发生且各自有发生速率，这些分子数状态之间的跳转就形成一个连续时间马尔科夫链。粗粒化的依据不是“分子数是否接近”，而是当前状态中哪些物种存在，以及这些物种是否形成某个 chemical organisation。粗粒化后得到的宏观状态是不同的化学组织，例如：
这类模型的微观状态通常是每种物种的分子数。例如，若系统中有三种物种 A,B,C，一个微观状态可以写成 (n_A,n_B,n_C)。每次反应都会改变这些分子数，例如 A+B\rightarrow C 会减少 A 和 B，增加 C。若反应随机发生且各自有发生速率，这些分子数状态之间的跳转就形成一个连续时间马尔科夫链。粗粒化的依据不是“分子数是否接近”，而是当前状态中哪些物种存在，以及这些物种是否形成某个 chemical organisation。粗粒化后得到的宏观状态是不同的化学组织，例如：
=== 网络社团检测 ===
=== [[网络社团检测]] ===
代表文献：Piccardi, 2011, Finding and Testing Network Communities by Lumped Markov Chains
代表文献：Piccardi, 2011, Finding and Testing Network Communities by Lumped Markov Chains
网络社团检测的目标是找出网络中联系紧密的节点集合。例如，在社交网络中，社团可能是一群经常互动的人；在网页网络中，社团可能是一组主题相近的网站；在交通网络中，社团可能是一组流动联系紧密的区域。
网络社团检测的目标是找出网络中联系紧密的节点集合。例如，在社交网络中，社团可能是一群经常互动的人；在网页网络中，社团可能是一组主题相近的网站；在交通网络中，社团可能是一组流动联系紧密的区域。
在这个应用中，微观状态是网络节点。给定一个网络，可以定义一个[[随机游走]]过程：如果当前在节点 i，下一步就按照边的权重随机移动到某个邻居节点 j。这样就得到一个节点层面的马尔科夫链。粗粒化的目标是把节点合并成较少的社团。其依据是随机游走的停留性：如果一个节点集合内部连接很强，随机游走进入后不容易离开，那么这个节点集合就可以看作一个社团。这个例子说明，马尔科夫链粗粒化可以为“什么是社团”提供一个动力学解释：社团就是随机游走不容易离开的地方。
在这个应用中，微观状态是城市中的细空间单元，例如网格、街区、交通小区、出租车上车/下车区域等。根据大量出行记录，可以估计转移概率，从而得到城市移动马尔科夫链。城市空间单元很多，原始转移矩阵很大。城市空间单元很多，原始转移矩阵很大，直接查看每个网格到每个网格的流动通常很难解释。粗粒化可以帮助识别更大的城市功能区域或交通模式，例如商业区、居住区、旅游区、交通枢纽等。
在这个应用中，微观状态是城市中的细空间单元，例如网格、街区、交通小区、出租车上车/下车区域等。根据大量出行记录，可以估计转移概率，从而得到城市移动马尔科夫链。城市空间单元很多，原始转移矩阵很大。城市空间单元很多，原始转移矩阵很大，直接查看每个网格到每个网格的流动通常很难解释。粗粒化可以帮助识别更大的城市功能区域或交通模式，例如商业区、居住区、旅游区、交通枢纽等。
粗粒化依据是区域之间的移动模式是否相似。如果两个空间单元的人流来源和去向相似，它们可能属于同一类区域。Duan 等人的方法进一步允许“软聚合”：一个区域不一定只属于一个宏观类，而是可以以不同概率属于多个 meta-states。这里的 meta-state 可以理解为从数据中学习出来的宏观状态或潜在类型。这很符合城市空间的实际情况。例如，一个区域白天可能像办公区，晚上可能像餐饮娱乐区，因此它未必只属于一种类型。
粗粒化依据是区域之间的移动模式是否相似。如果两个空间单元的人流来源和去向相似，它们可能属于同一类区域。Duan 等人的方法进一步允许“[[软聚合]]”：一个区域不一定只属于一个宏观类，而是可以以不同概率属于多个 meta-states。这里的 meta-state 可以理解为从数据中学习出来的宏观状态或潜在类型。这很符合城市空间的实际情况。例如，一个区域白天可能像办公区，晚上可能像餐饮娱乐区，因此它未必只属于一种类型。
因此，粗粒化后得到的是空间单元的聚合。硬分组时，每个网格或街区属于一个宏观区域。软分组时，每个区域对多个宏观类型都有一定隶属度。例如，在曼哈顿出租车数据中，粗粒化后的状态可能对应时代广场一类的高活动商业娱乐区、博物馆或公园附近的旅游区域、World Trade Center 附近的商务区域、交通换乘密集区域。
因此，粗粒化后得到的是空间单元的聚合。硬分组时，每个网格或街区属于一个宏观区域。软分组时，每个区域对多个宏观类型都有一定隶属度。例如，在曼哈顿出租车数据中，粗粒化后的状态可能对应时代广场一类的高活动商业娱乐区、博物馆或公园附近的旅游区域、World Trade Center 附近的商务区域、交通换乘密集区域。
在这个应用中，微观状态是空间小格子或网络节点。例如，在海洋表层流中，可以把海面划分成许多网格。一个漂浮粒子现在位于网格 i，过一段时间后移动到网格 j 的概率，就是马尔科夫链中的转移概率。细网格数量很多，而研究者通常关心更大尺度的流动结构。例如，哪些区域之间交换频繁？哪些区域在长时间内相对封闭？哪些区域共同形成一个大尺度循环？粗粒化可以把大量空间网格合并成少数动力学模块。
在这个应用中，微观状态是空间小格子或网络节点。例如，在海洋表层流中，可以把海面划分成许多网格。一个漂浮粒子现在位于网格 i，过一段时间后移动到网格 j 的概率，就是马尔科夫链中的转移概率。细网格数量很多，而研究者通常关心更大尺度的流动结构。例如，哪些区域之间交换频繁？哪些区域在长时间内相对封闭？哪些区域共同形成一个大尺度循环？粗粒化可以把大量空间网格合并成少数动力学模块。
Faccin 等人的方法依据的是“保留长期转移信息”。简单说，一个好的分组应该让我们即使只知道粒子所在的宏观区域，也仍然能尽量预测它在较长时间后会到哪里。该方法用信息论中的互信息来衡量这种保留程度。而粗粒化后得到的分组是空间上的动力学模块。在海洋流中，这些模块可能对应一些大尺度相干区域。粒子在同一模块内部更容易一起移动或长期停留，而不同模块之间的交换相对较少。
Faccin 等人的方法依据的是“保留长期转移信息”。简单说，一个好的分组应该让我们即使只知道粒子所在的宏观区域，也仍然能尽量预测它在较长时间后会到哪里。该方法用[[信息论]]中的[[互信息]]来衡量这种保留程度。而粗粒化后得到的分组是空间上的动力学模块。在海洋流中，这些模块可能对应一些大尺度相干区域。粒子在同一模块内部更容易一起移动或长期停留，而不同模块之间的交换相对较少。
=== Agent-based model 与观点动力学 ===
=== [[Agent-based model]] 与[[观点动力学]] ===
代表文献：Banisch, Lima & Araújo, 2012, Agent Based Models and Opinion Dynamics as Markov Chains
代表文献：Banisch, Lima & Araújo, 2012, Agent Based Models and Opinion Dynamics as Markov Chains
=== 排队网络与计算机系统 ===
=== [[排队网络]]与计算机系统 ===
代表文献：Song & Takahashi, 1991, Aggregate Approximation for Tandem Queueing Systems with Production Blocking；Gambin, Krzyżanowski & Pokarowski, 2008, Aggregation algorithms for perturbed Markov chains with applications to networks modeling
代表文献：Song & Takahashi, 1991, Aggregate Approximation for Tandem Queueing Systems with Production Blocking；Gambin, Krzyżanowski & Pokarowski, 2008, Aggregation algorithms for perturbed Markov chains with applications to networks modeling
# 在生化反应网络中，粗粒化用于避免状态空间爆炸；
# 在生化反应网络中，粗粒化用于避免状态空间爆炸；
# 在化学反应网络长期行为分析中，粗粒化得到的是能够自我维持的物种集合；
# 在化学反应网络长期行为分析中，粗粒化得到的是能够自我维持的物种集合；
# 在网络科学中，粗粒化得到社团；
# 在[[网络科学]]中，粗粒化得到社团；
# 在交通和迁徙数据中，粗粒化得到功能区、交通模式或城市类型；
# 在交通和迁徙数据中，粗粒化得到功能区、交通模式或城市类型；
# 在海洋流和空间流动中，粗粒化得到大尺度动力学模块；
# 在海洋流和空间流动中，粗粒化得到大尺度动力学模块；
|-
|-
| 网络社团检测
| 网络社团检测
| 在复杂网络中识别联系紧密的节点集合
| 在[[复杂网络]]中识别联系紧密的节点集合
| 微观状态是网络节点；随机游走定义节点层面的离散时间马尔科夫链
| 微观状态是网络节点；随机游走定义节点层面的离散时间马尔科夫链
| 网络社团；宏观过程可理解为社团之间的随机游走
| 网络社团；宏观过程可理解为社团之间的随机游走