812
个编辑
更改
跳到导航
跳到搜索
第1,010行：
第1,010行： − 在应用到马尔科夫链粗粒化的应用工作中，基本思想都是把原来很多、很细的系统状态中，一些“行为相似”或“观测上无法区分”的状态合并成更少的状态，从而得到一个更容易理解或计算的模型。需要注意的是，粗粒化的结果不一定仍然是严格的马尔科夫链。很多应用正是通过粗粒化来研究：哪些状态可以合并？合并以后会不会丢失马尔科夫性？如果丢失，能不能构造一个近似的宏观马尔科夫模型？+ − 下面介绍几个典型应用。这些应用虽然来自不同领域，但结构和思路都非常相似：+ + + + + − 1. 先有一个微观马尔科夫链；+ − 2. 微观状态数量很多，或者观测上太细； − 3. 根据动力学相似性、观测等价性、研究目标或系统结构，把微观状态合并； − 4. 得到更少的宏观状态； − 5. 再分析粗粒化是否保留了原始系统的重要信息。 − + − + − 在分子动力学中，一个蛋白质、小分子或药物分子会不断改变自己的空间形状。例如，蛋白质可能会折叠、展开，或者在几种稳定形状之间来回切换。一个蛋白质或小分子的构象空间通常是连续且高维的。可以把它理解为：同一个分子，原子连接方式没有变，但整体姿态、弯曲方式、折叠方式不同，这些不同空间形状就叫不同构象。分子动力学模拟会产生大量构象。问题是，这些构象数量太多，直接分析很困难。研究者通常希望把它们合并成少数几类有物理意义的“大状态”。+ − 首先，把分子的连续运动离散化，也就是把大量相近的分子形状归成许多小的构象簇，每个构象簇看作一个微观状态。然后，根据模拟轨迹估计从微观构象 (i)过一段时间后转到微观构象 (j) 的转移概率，所有这样的概率组成一个转移矩阵 (P)。于是，分子在不同微观构象之间的随机跳转就可以近似看成一个马尔科夫链。但是，微观构象太多，而且很多微观构象之间差别很小。真正有意义的往往不是单个微观构象，而是一些较大的稳定区域。例如，一个蛋白质可能有三种主要状态：展开状态、半折叠中间状态、完全折叠状态。每一种状态内部又包含许多细微不同的构象。粗粒化的目的就是把这些细小构象合并成少数几个“亚稳态构象”。“亚稳态”可以理解为：系统会在这个状态附近停留比较久，但最终仍然可能跳到别的状态。+ − 粗粒化主要依据分子的转移动力学，而不是单纯依据几何形状是否相似。如果一批微观构象之间经常互相转移，但很少跳到外面，那么它们可以合并成一个宏观状态。这说明这些微观状态在动力学上属于同一个稳定区域。Kube 和 Weber 的工作使用 PCCA+ 方法。这个方法大致可以理解为：通过分析转移矩阵，找出那些在较长时间内不容易离开的状态集合。粗粒化之后，研究者可以进一步估计这些大状态之间的转移速率，例如蛋白质从展开态变成折叠态大约需要多久。这个例子说明，马尔科夫链粗粒化可以把复杂的微观运动变成更容易理解的宏观状态转换图。+ − + + + − 细胞内部有大量化学反应。例如，一个蛋白质可以被磷酸化，可以和另一个蛋白质结合，也可以从复合物中解离。每个分子又可能有多个结合位点和修饰位点。这样一来，可能出现的分子组合数量会非常大。即使反应规则本身不多，所有可能状态的数量也可能爆炸式增长。这叫“组合爆炸”。+ − − 微观状态是系统在某一时刻的完整化学状态，要说明系统里有哪些分子、每种分子有多少个、哪些分子和哪些分子结合等。每一次化学反应都会把系统从一个微观状态带到另一个微观状态。例如一个分子被修饰或者两个分子结合了等等。如果每个反应都有发生速率，那么整个系统就形成一个连续时间马尔科夫链。 − 但是，完整微观链太大，几乎无法直接计算。例如，想要求系统在未来某个时间处于某类状态的概率，或者求长期稳态分布，都可能因为状态数太多而不可行。在很多问题中，研究者并不关心所有细节。例如，他们可能只关心某个关键蛋白是否被激活，而不关心所有无关位点的具体状态。粗粒化可以把不重要的细节合并掉，而其依据是研究目标和反应结构。例如，如果某些微观状态虽然在细节上不同，但对目标变量来说没有区别，就可以合并。也可以根据反应网络的对称性、分子结构规则或成块性条件来合并状态。得到的分组是许多微观化学状态的集合。每个集合代表一个宏观状态，例如“关键蛋白未激活”、“关键蛋白已激活但未结合配体”、“关键蛋白已激活且结合配体”等。+ − + − + − + − − 微观状态是每种物种的分子数。例如，如果系统中有三种物种 (A,B,C)，一个微观状态可以写成：(n_A,n_B,n_C)。每次反应都会改变这些分子数。例如： − * (A+B\rightarrow C) 会减少 (A) 和 (B)，增加 (C)； − * (C\rightarrow A+B) 会减少 (C)，增加 (A) 和 (B)。 − − 如果反应随机发生，并且每个反应有自己的速率，那么这些分子数状态之间的跳转形成一个连续时间马尔科夫链。微观分子数状态很多，而且单个分子数状态未必能反映系统的长期结构。研究者更关心的是：系统最终会落在哪一类“能维持自身的物种集合”附近。因此，可以把大量具体分子数状态合并成更高层次的化学组织状态。 − 粗粒化依据是当前状态中哪些物种存在，以及这些物种是否形成某个 chemical organisation。也就是说，这里不是按“分子数接近”来合并，而是按“涉及哪些物种、这些物种在反应网络中是否能形成稳定组织”来合并。得到的分组是不同的化学组织。每个宏观状态代表一类物种集合。例如，一个系统可能有以下几类宏观状态：+ 第1,067行：
第1,061行： − + − 网络社团检测的目标是找出网络中联系紧密的节点集合。例如，在社交网络中，社团可能是一群经常互动的人；在网页网络中，社团可能是一组主题相近的网站。一个常用直觉是：如果一个随机游走者进入了一个好的社团，它应该会在社团内部停留比较久，而不是马上跳出去。+ − 定义微观状态是网络节点。给定一个网络，可以定义一个随机游走过程：如果当前在节点 (i)，下一步按照边的权重随机移动到某个邻居节点 (j)。这样就得到一个节点层面的马尔科夫链。在现实中，大型网络中的节点太多，直接看节点层面的转移不容易理解。社团检测希望把节点合并成较少的模块，从而得到网络的宏观结构。得到的分组是网络社团。每个社团是一组节点。例如，社交网络中一组关系密切的用户、网页网络中，一组主题相似的网站、城市交通网络中一组流动联系紧密的区域等。+ − 粗粒化依据是随机游走的停留性。如果一个节点集合内部连接很强，随机游走进入后不容易离开，那么这个节点集合就可以看作一个社团。Piccardi 使用 lumped Markov chain 的思想，用社团保持概率来评价一个候选社团是否显著。 + − === 城市交通与出租车流：把细空间单元合并成功能区域 ===+ − 代表文献：Zhang & Wang, 2020, *Spectral State Compression of Markov Processes*；Duan, Ke & Wang, 2019, *State Aggregation Learning from Markov Transition Data*。+ − 像刚才说的，社团可以看作是城市交通网络中一组流动联系紧密的区域。城市中的出租车、共享单车、手机信令、通勤和迁徙数据都可以看成地点之间的移动记录。例如，一次出租车行程从地点 (i) 到地点 (j)，就表示一次从 (i) 到 (j) 的转移。如果把城市划分成很多网格或街区，就可以用马尔科夫链描述人在城市空间中的移动。+ − 定义微观状态是城市中的细空间单元，例如网格、街区、交通小区、出租车上车/下车区域等。根据大量出行记录，可以估计转移概率，并得到一个空间单元之间的马尔科夫链。城市空间单元很多，原始转移矩阵很大。直接看每个网格到每个网格的流动，通常很难解释。粗粒化可以帮助识别更大的城市功能区域或交通模式，例如商业区、居住区、旅游区、交通枢纽、夜生活区域等。+ − 粗粒化依据是区域之间的移动模式是否相似。如果两个空间单元的人流来源和去向相似，它们可能属于同一类区域。Duan 等人的方法进一步允许“软聚合”：一个区域不一定只属于一个宏观类，而是可以以不同概率属于多个 meta-states。这很符合城市空间的实际情况。例如，一个区域白天可能像办公区，晚上可能像餐饮娱乐区，因此它未必只属于一种类型。得到的分组是空间单元的聚合。硬分组时，每个网格或街区属于一个宏观区域。软分组时，每个区域对多个宏观类型都有一定隶属度。例如，在曼哈顿出租车数据中，粗粒化后的状态可能对应时代广场一类的高活动商业娱乐区、博物馆或公园附近的旅游区域、World Trade Center 附近的商务区域、交通换乘密集区域。+ − + 第1,095行：
第1,089行： − 定义微观状态为空间小格子或网络节点。例如，在海洋表层流中，可以把海面划分成许多网格。一个漂浮粒子现在在网格 (i)，过一段时间后移动到网格 (j) 的概率，就是马尔科夫链的转移概率。细网格数量很多，而且研究者通常关心的是更大尺度的流动结构。例如，哪些区域之间交换频繁？哪些区域在长时间内相对封闭？哪些区域共同形成一个大尺度循环？粗粒化可以把大量空间网格合并成少数动力学模块。+ + + − Faccin 等人的方法依据的是“保留长期转移信息”。简单说，一个好的分组应该让我们即使只知道粒子所在的宏观区域，也仍然能尽量预测它在较长时间后会到哪里。该方法用信息论中的互信息来衡量这种保留程度。而得到的分组是空间上的动力学模块。在海洋流中，这些模块可能对应一些大尺度相干区域。粒子在同一模块内部更容易一起移动或长期停留，而不同模块之间的交换相对较少。这个例子说明，粗粒化不一定只看一步转移，也可以看长时间尺度上的动力学关系。 − + 第1,106行：
第1,101行： − 定义微观状态为所有个体状态的完整配置，对一个有 N 个人，每个人都有两种观点 0 或 1 的系统，那么微观状态就是一个长度为 (N) 的 0/1 序列，例如 (1,0,0,1,1,\ldots)。如果每一步随机选择一个人更新观点，系统就会从一个配置随机跳到另一个配置。因此，所有个体配置构成一个马尔科夫链。+ + + − 研究者通常不关心每个人的具体观点排列，而是关心宏观变量，例如支持观点 1 的人数、两种观点是否达成共识、是否出现极化等现象。因此，需要把许多微观配置合并成同一个宏观状态。粗粒化依据是选定的宏观变量。例如，可以把所有“有 (k) 个人支持观点 1”的微观配置合并在一起。如果系统的更新规则只依赖于这个人数，那么粗粒化后的过程可能仍然是马尔科夫链。如果更新规则还依赖于谁和谁相连、支持者分布在哪些位置，那么只知道人数可能不够，宏观过程就可能不再是马尔科夫链。马尔科夫链粗粒化可以帮助我们从个体规则推导宏观社会变量的演化，但当宏观变量选得太粗时，也可能会丢失关键结构信息。 − + 第1,117行：
第1,113行： − 可以定义微观状态为系统的完整配置，例如，在一个有三个队列的系统中，状态(2,5,1)表示三个队列中分别有 2、5、1 个任务。服务完成、任务到达或阻塞解除都会使系统从一个状态跳到另一个状态。因此，排队系统的随机演化可以表示为马尔科夫链或连续时间马尔科夫链。+ − 完整状态空间很大。队列越多、容量越大，可能状态数就越多。直接求稳态分布或平均等待时间会变得很困难。工程上通常更关心一些聚合指标，例如平均队长、平均等待时间、系统吞吐量、阻塞概率、服务器利用率等。因此，可以依据系统结构和耦合强弱等进行粗粒化，降低模型规模。如果一组微观状态之间转移频繁，而与其他组之间联系较弱，就可以把它们看成一个聚合状态。对于近似可分解的马尔科夫链，这种思想尤其自然：系统内部有强耦合模块，模块之间只有弱相互作用。这类粗粒化的主要目的不是发现新的自然类别，而是让大规模马尔科夫模型可以近似计算。+ − * 在分子动力学中，粗粒化得到的是几个稳定的分子形状；+ − * 在离子通道中，粗粒化得到的是 open / closed 观测状态；+ − * 在生化反应网络中，粗粒化是为了避免状态空间爆炸；+ − * 在网络科学中，粗粒化得到社团；+ − * 在交通和迁徙数据中，粗粒化得到功能区、交通模式或城市类型；+ − * 在观点动力学中，粗粒化得到宏观社会变量；+ − * 在排队系统中，粗粒化得到可计算的性能状态。+ + − 因此，马尔科夫链粗粒化并不是简单地“减少状态数”，而是要在减少状态数的同时，尽量保留对研究问题重要的转移动力学。+ +
→应用
=应用=
=应用=
马尔科夫链粗粒化的应用工作虽然来自不同领域，但结构和思路都非常相似：
# 先有一个微观马尔科夫链；
# 微观状态数量很多，或者观测上太细；
# 根据动力学相似性、观测等价性、研究目标或系统结构，把微观状态合并；
# 得到更少的宏观状态；
# 再分析粗粒化是否保留了原始系统的重要信息。
需要注意的是，粗粒化的结果不一定仍然是严格的马尔科夫链。很多应用正是通过粗粒化来研究：哪些状态可以合并？合并以后会不会丢失马尔科夫性？如果丢失，能不能构造一个近似的宏观马尔科夫模型？
=== 分子构象动力学：把大量分子形状合并成少数稳定形状 ===
=== 分子构象动力学 ===
代表文献： 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，于是分子在不同构象簇之间的随机跳转就可以近似看作马尔科夫链。
粗粒化的目的，是把大量细小构象合并成少数几个有物理意义的“大状态”。例如，一个蛋白质可能有展开态、半折叠中间态和完全折叠态。每个大状态内部仍包含许多细微不同的构象。这类粗粒化主要依据转移动力学，而不是单纯依据几何形状。如果一批微观构象之间经常互相转移，但很少跳到外面，那么它们可以合并成一个宏观状态，称为“亚稳态构象”。“亚稳态”可以理解为：系统会在这个状态附近停留较久，但最终仍可能跳到别的状态。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*。
细胞内部有大量化学反应。一个蛋白质可以被磷酸化，可以和另一个蛋白质结合，也可以从复合物中解离。由于分子可能有多个结合位点和修饰位点，所有可能的分子组合会非常多，即使反应规则本身不复杂，状态数也可能爆炸式增长。在这类模型中，微观状态是系统在某一时刻的完整化学状态。例如，一个微观状态需要说明：系统里有哪些分子、每种分子有多少个、哪些分子彼此结合、哪些位点被修饰等。每一次反应都会把系统从一个微观状态带到另一个微观状态。如果每个反应都有发生速率，那么整个系统就形成一个连续时间马尔科夫链。
完整微观链通常太大，难以直接计算。例如，要求未来某个时间系统处于某类状态的概率，或者求长期稳态分布，都可能因为状态数太多而不可行。同时，研究者往往并不关心所有细节，而只关心某些关键变量，例如某个蛋白是否被激活。因此，可以把对目标变量没有影响或近似没有影响的细节合并掉。粗粒化依据可以是研究目标、分子结构、反应网络对称性，或者成块性条件。粗粒化后得到的宏观状态可能是：“关键蛋白未激活”、“关键蛋白已激活但未结合配体”、“关键蛋白已激活且结合配体”等。
Ganguly 等人的工作研究的是：给定一个连续时间马尔科夫链和一个状态分组，在什么条件下可以在分组后的状态上定义一个合理的聚合模型。Petrov 的工作进一步讨论如何在 rule-based biochemical models 中自动找到这样的聚合结构。
Ganguly 等人的工作研究的是：给定一个连续时间马尔科夫链和一个状态分组，在什么条件下可以在分组后的状态上定义合理的聚合模型。Petrov 的工作进一步讨论如何在 rule-based biochemical models 中自动寻找这种聚合结构。这里的 rule-based model 指的是用反应规则描述系统，而不是一开始就枚举所有可能的微观状态，因此特别适合处理状态空间极大的生化系统。
=== 化学反应网络长期行为：把分子数状态合并成“能自我维持的物种集合”===
====合并物种集合====
代表文献：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) 能维持；
* 只有物种 (A) 能维持；
* 物种 (A) 和 (B) 能共同维持；
* 物种 (A) 和 (B) 能共同维持；
=== 网络社团检测：把节点合并成社团 ===
=== 网络社团检测 ===
代表文献：Piccardi, 2011, *Finding and Testing Network Communities by Lumped Markov Chains*。
代表文献：Piccardi, 2011, *Finding and Testing Network Communities by Lumped Markov Chains*。
网络社团检测的目标是找出网络中联系紧密的节点集合。例如，在社交网络中，社团可能是一群经常互动的人；在网页网络中，社团可能是一组主题相近的网站；在交通网络中，社团可能是一组流动联系紧密的区域。
在这个应用中，微观状态是网络节点。给定一个网络，可以定义一个随机游走过程：如果当前在节点 i，下一步就按照边的权重随机移动到某个邻居节点 j。这样就得到一个节点层面的马尔科夫链。粗粒化的目标是把节点合并成较少的社团。其依据是随机游走的停留性：如果一个节点集合内部连接很强，随机游走进入后不容易离开，那么这个节点集合就可以看作一个社团。这个例子说明，马尔科夫链粗粒化可以为“什么是社团”提供一个动力学解释：社团就是随机游走不容易离开的地方。
=== 城市交通与出租车流 ===
代表文献：Zhang & Wang, 2020, *Spectral State Compression of Markov Processes*；Duan, Ke & Wang, 2019, *State Aggregation Learning from Markov Transition Data*。
城市中的出租车、共享单车、手机信令、通勤和迁徙数据都可以看成地点之间的移动记录。例如，一次出租车行程从地点 i 到地点 j，就表示一次从 i 到 j 的转移。如果把城市划分成网格、街区或交通小区，就可以用马尔科夫链描述人在城市空间中的移动。
在这个应用中，微观状态是城市中的细空间单元，例如网格、街区、交通小区、出租车上车/下车区域等。根据大量出行记录，可以估计转移概率，从而得到城市移动马尔科夫链。城市空间单元很多，原始转移矩阵很大。城市空间单元很多，原始转移矩阵很大，直接查看每个网格到每个网格的流动通常很难解释。粗粒化可以帮助识别更大的城市功能区域或交通模式，例如商业区、居住区、旅游区、交通枢纽等。
粗粒化依据是区域之间的移动模式是否相似。如果两个空间单元的人流来源和去向相似，它们可能属于同一类区域。Duan 等人的方法进一步允许“软聚合”：一个区域不一定只属于一个宏观类，而是可以以不同概率属于多个 meta-states。这里的 meta-state 可以理解为从数据中学习出来的宏观状态或潜在类型。这很符合城市空间的实际情况。例如，一个区域白天可能像办公区，晚上可能像餐饮娱乐区，因此它未必只属于一种类型。
因此，粗粒化后得到的是空间单元的聚合。硬分组时，每个网格或街区属于一个宏观区域。软分组时，每个区域对多个宏观类型都有一定隶属度。例如，在曼哈顿出租车数据中，粗粒化后的状态可能对应时代广场一类的高活动商业娱乐区、博物馆或公园附近的旅游区域、World Trade Center 附近的商务区域、交通换乘密集区域。
=== 海洋流与空间流动：把细网格合并成大尺度流动区域 ===
=== 海洋流与空间流动 ===
代表文献：Faccin, Schaub & Delvenne, 2021, *State aggregations in Markov chains and block models of networks*。
代表文献：Faccin, Schaub & Delvenne, 2021, *State aggregations in Markov chains and block models of networks*。
在海洋、空气污染、生态扩散等系统中，研究者常关心物质如何在空间中移动。例如，海水、漂浮物、污染物或生物幼体可能随着流场移动。如果把空间切成许多小格子，就可以描述一个粒子从一个格子移动到另一个格子的概率。
在海洋、空气污染、生态扩散等系统中，研究者常关心物质如何在空间中移动。例如，海水、漂浮物、污染物或生物幼体可能随着流场移动。如果把空间切成许多小格子，就可以描述一个粒子从一个格子移动到另一个格子的概率。
在这个应用中，微观状态是空间小格子或网络节点。例如，在海洋表层流中，可以把海面划分成许多网格。一个漂浮粒子现在位于网格 i，过一段时间后移动到网格 j 的概率，就是马尔科夫链中的转移概率。细网格数量很多，而研究者通常关心更大尺度的流动结构。例如，哪些区域之间交换频繁？哪些区域在长时间内相对封闭？哪些区域共同形成一个大尺度循环？粗粒化可以把大量空间网格合并成少数动力学模块。
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*。
Agent-based model 是一种个体层面的建模方法。模型中有许多个体，每个个体按照简单规则行动或改变状态。例如，在观点动力学中，每个人可能支持观点 0 或观点 1，并受到邻居影响而改变观点。虽然个体规则简单，但所有个体组合起来以后，系统状态会非常多。
Agent-based model 是一种个体层面的建模方法。模型中有许多个体，每个个体按照简单规则行动或改变状态。例如，在观点动力学中，每个人可能支持观点 0 或观点 1，并受到邻居影响而改变观点。虽然个体规则简单，但所有个体组合起来以后，系统状态会非常多。
在这类模型中，微观状态是所有个体状态的完整配置。比如，有 N 个人，每个人都有两种观点 0 或 1，那么整个系统的一个微观状态就是一个长度为 N 的 0/1 序列，例如 (1,0,0,1,1,\ldots)。如果每一步随机选择一个人更新观点，系统就会从一个配置随机跳到另一个配置。因此，所有个体配置构成一个马尔科夫链。
研究者通常不关心每个人的具体观点排列，而是关心宏观变量，例如支持观点 1 的人数、两种观点是否达成共识、是否出现极化等。粗粒化的依据就是这些宏观变量。例如，可以把所有“有 k 个人支持观点 1”的微观配置合并在一起。如果系统的更新规则只依赖于这个人数，那么粗粒化后的过程可能仍然是马尔科夫链。如果更新规则还依赖于谁和谁相连、支持者分布在哪些位置，那么只知道人数可能不够，宏观过程就可能不再是马尔科夫链。这个例子说明，马尔科夫链粗粒化可以帮助我们从个体规则推导宏观社会变量的演化；但当宏观变量选得太粗时，也可能丢失关键结构信息。
=== 排队网络与计算机系统：把复杂系统状态合并成性能状态 ===
=== 排队网络与计算机系统 ===
代表文献：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*。
排队系统和计算机系统经常可以用马尔科夫链建模。例如，一个工厂生产线有多个工位，每个工位前面可能有队列；一个服务器系统有多个任务等待处理。系统的完整状态需要记录每个队列有多少任务、每个服务器是否忙碌、是否发生阻塞等。
排队系统和计算机系统经常可以用马尔科夫链建模。例如，一个工厂生产线有多个工位，每个工位前面可能有队列；一个服务器系统有多个任务等待处理。系统的完整状态需要记录每个队列有多少任务、每个服务器是否忙碌、是否发生阻塞等。
在这类模型中，微观状态是系统的完整配置。例如，在一个有三个队列的系统中，状态 (2,5,1) 表示三个队列中分别有 2、5、1 个任务。服务完成、任务到达或阻塞解除都会使系统从一个状态跳到另一个状态。因此，排队系统的随机演化可以表示为离散时间或连续时间马尔科夫链。
完整状态空间往往很大。队列越多、容量越大，可能状态数就越多。直接求稳态分布、平均等待时间或阻塞概率会变得很困难。工程上通常更关心平均队长、平均等待时间、系统吞吐量、阻塞概率、服务器利用率等聚合指标。因此，可以通过粗粒化降低模型规模。这类粗粒化通常依据系统结构和耦合强弱。如果一组微观状态之间转移频繁，而与其他组之间联系较弱，就可以把它们看成一个聚合状态。粗粒化后的分组可以理解为聚合性能状态，例如“低拥堵状态”“中等拥堵状态”或“高拥堵状态”。这类粗粒化的主要目的通常不是发现新的自然类别，而是让大规模马尔科夫模型可以近似计算。
从上述工作中可见，在不同领域中，粗粒化的含义可以不同：
从上述工作中可见，在不同领域中，粗粒化的含义可以不同：
# 在分子动力学中，粗粒化得到的是几个稳定的分子形状；
# 在生化反应网络中，粗粒化用于避免状态空间爆炸；
# 在化学反应网络长期行为分析中，粗粒化得到的是能够自我维持的物种集合；
# 在网络科学中，粗粒化得到社团；
# 在交通和迁徙数据中，粗粒化得到功能区、交通模式或城市类型；
# 在海洋流和空间流动中，粗粒化得到大尺度动力学模块；
# 在观点动力学中，粗粒化得到宏观社会变量；
# 在排队系统中，粗粒化得到可计算的性能状态。
因此，马尔科夫链粗粒化并不是简单地“减少状态数”，而是在减少状态数的同时，尽量保留对研究问题重要的转移动力学。不同应用中的“重要信息”并不相同：它可以是亚稳态结构、目标变量、社团保持性、长期流动信息、宏观社会变量，也可以是系统性能指标。
<br/>
<references />
<references />