更改

Barnett & Seth 的动力学解耦文章中<ref name=":26" /> 把宏观变量定义为确定性粗粒化 <math>Y_t=f(X_t)</math>，实际上用到了平稳分布加权平均。如果我们额外假设微观过程 <math>X_t</math> 是有限状态一阶 Markov 链，且忽略或不显式保留 <math>Y</math> 的历史依赖，那么宏观块 <math>M</math> 的出流应按组内微观状态在平稳分布下的条件概率加权：<math>P'_{MN}=\sum_{i\in M} \frac{\pi_i}{\sum_{k\in M}\pi_k} \sum_{j\in N}P_{ij}</math>。因此，在这些附加假设下，它可以归为平稳分布加权聚合。

Barnett & Seth 的动力学解耦文章中<ref name=":26" /> 把宏观变量定义为确定性粗粒化 <math>Y_t=f(X_t)</math>，实际上用到了平稳分布加权平均。如果我们额外假设微观过程 <math>X_t</math> 是有限状态一阶 Markov 链，且忽略或不显式保留 <math>Y</math> 的历史依赖，那么宏观块 <math>M</math> 的出流应按组内微观状态在平稳分布下的条件概率加权：<math>P'_{MN}=\sum_{i\in M} \frac{\pi_i}{\sum_{k\in M}\pi_k} \sum_{j\in N}P_{ij}</math>。因此，在这些附加假设下，它可以归为平稳分布加权聚合。

=复杂网络中的[[粗粒化]]方法=

=[[复杂网络]]中的[[粗粒化]]方法=

复杂网络中的粗粒化方法非常多，常见思路包括：根据[[社团结构]]或[[模块结构]]合并节点，根据[[谱嵌入]]或[[扩散距离]]寻找动力学上相近的节点，根据[[网络模体]]或[[功能单元]]识别可重复的局部结构，也可以利用统计物理量、[[图神经网络]]等方法，在保留全局流量、扩散过程或拓扑功能的前提下压缩网络。不同方法关注的对象并不完全相同：有的主要保留拓扑结构，有的保留[[随机游走]]或扩散动力学，有的则保留功能模块和多尺度组织。

[[马尔可夫链]]与[[复杂网络]]具有天然的对应关系：一方面，[[马尔可夫链]]本身可以看作是一个有向加权的网络，而另一方面，可以针对任何[[复杂网络]]定义[[随机游走动力学]]，该动力学可以直接对应到一个[[马尔可夫链]]。因此，[[复杂网络]]的[[粗粒化]]方法也可以借鉴作为[[马尔可夫链的粗粒化]]方法。

这些方法与[[马尔科夫链]]粗粒化有两层联系。首先，马尔科夫链本身可以看作一种加权有向复杂网络：状态对应节点，转移概率对应有向边权。因此，我们可以先把马尔科夫链的状态转移图视为一个网络，并使用一些有向图方法来生成候选划分。例如，社团检测会倾向于合并转移联系密集、概率流交换频繁的一组状态；[[谱聚类]]会根据大尺度连通结构或扩散结构合并状态；[[角色相似性]]方法则会把具有相似入流和出流模式的状态放在一起。如果暂时忽略方向、权重或具体转移概率，则可以把马尔科夫链退化为一个普通的无向拓扑网络。这样做会丢掉一部分动力学信息，但也能使用更广泛的复杂网络粗粒化工具，如无向社团检测、模块识别、网络模体识别和[[层次聚类]]等。此时得到的划分可作为候选分组，再根据[[成块性]]、[[稳态流]]、EI、[[动力学可逆性]]等指标进行选择。

[[复杂网络]]中的粗粒化方法非常多，常见思路包括：根据[[社团结构]]或[[模块结构]]合并节点，根据[[谱嵌入]]或[[扩散距离]]寻找动力学上相近的节点，根据[[网络模体]]或[[功能单元]]识别可重复的局部结构，也可以利用[[复杂网络上的统计物理]]方法、[[图神经网络]]等方法，在保留全局流量、扩散过程或拓扑功能的前提下压缩网络。不同方法关注的对象并不完全相同：有的主要保留拓扑结构，有的保留[[随机游走]]或[[扩散动力学]]，有的则保留功能模块和多尺度组织。

其次，许多复杂网络上都可以定义随机游走、扩散或传播动力学。一旦规定游走规则，网络就会诱导出一个[[转移概率矩阵]] <math>P</math>，也就是一条马尔科夫链。于是，复杂网络的粗粒化可以转化为马尔科夫链的状态粗粒化：我们不仅关心哪些节点拓扑上相近，也关心哪些节点在随机游走中具有相似的动力学作用。在这个意义上，成块性可以检验合并后的宏观节点是否仍然形成封闭马尔科夫链；稳态流矩阵可以刻画长期概率流通道；谱方法可以寻找扩散尺度上的相似节点；HOM 则可以在节点合并时保留随机游走的高阶路径依赖。因此，马尔科夫链粗粒化工具可以反过来用于复杂网络上的随机游走动力学压缩。

这些方法与[[马尔科夫链]]粗粒化有两层联系。首先，[[马尔科夫链]]本身可以看作一种加权有向复杂网络：状态对应节点，转移概率对应有向边权。因此，我们可以先把马尔科夫链的状态转移图视为一个网络，并使用一些有向图方法来生成候选划分。例如，[[社团检测]]会倾向于合并转移联系密集、概率流交换频繁的一组状态；[[谱聚类]]会根据大尺度连通结构或扩散结构合并状态；[[角色相似性]]方法则会把具有相似入流和出流模式的状态放在一起。如果暂时忽略方向、权重或具体转移概率，则可以把马尔科夫链退化为一个普通的无向拓扑网络。这样做会丢掉一部分动力学信息，但也能使用更广泛的复杂网络粗粒化工具，如无向社团检测、模块识别、[[网络模体]]识别和[[层次聚类]]等。此时得到的划分可作为候选分组，再根据[[成块性]]、[[稳态流]]、[[EI]]、[[动力学可逆性]]等指标进行选择。

 

 

==复杂网络的粗粒化方法==

==复杂网络的粗粒化方法==

假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。

假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。

考虑一个连通图 <math>G</math>，[[邻接矩阵]]为 <math>A</math>，假设图上有 <math>N</math> 个节点，分别为 <math>1,2,...,N</math>，我们定义从节点 <math>i\in\left\{1,2,...,N\right\}</math> 到节点 <math>j\in\left\{1,2,...,N\right\}</math> 的转移概率为 <math>w_{ij}=\frac{a_{ij}}{\sum_{j}a_{ij}}</math>（即对边权进行行归一化），其中 <math>a_{ij}</math> 表示邻接矩阵的第 <math>i</math> 行第 <math>j</math> 列元素，对应从节点 <math>i</math> 到节点 <math>j</math> 的边的权重。

考虑一个连通图 <math>G</math>，[[邻接矩阵]]为 <math>A</math>，假设图上有 <math>N</math> 个节点，分别为 <math>1,2,...,N</math>，我们定义从节点 <math>i\in\left\{1,2,...,N\right\}</math> 到节点 <math>j\in\left\{1,2,...,N\right\}</math> 的转移概率为 <math>w_{ij}=\frac{a_{ij}}{\sum_{j}a_{ij}}</math>（即对边权进行行[[归一化]]），其中 <math>a_{ij}</math> 表示[[邻接矩阵]]的第 <math>i</math> 行第 <math>j</math> 列元素，对应从节点 <math>i</math> 到节点 <math>j</math> 的边的权重。

由于该网络是连通图，所以分母 <math>\sum_{j}a_{ij}</math> 会大于<math>0</math>，而且满足行归一化，即 <math>\sum_{j=1}^N {w_{ij}}=1</math>。这样我们就定义了一个马尔科夫链，[[状态空间]]为 <math>\left\{1,2,...,N\right\}</math>，从状态 <math>i</math> 到状态 <math>j</math> 的转移概率为 <math>w_{ij}</math>，转移矩阵为 <math>W=\left\{w_{ij}\right\}_{N \times N}</math>（详情请见[[复杂网络中的因果涌现]]词条）。

由于该网络是连通图，所以分母 <math>\sum_{j}a_{ij}</math> 会大于<math>0</math>，而且满足行归一化，即 <math>\sum_{j=1}^N {w_{ij}}=1</math>。这样我们就定义了一个马尔科夫链，[[状态空间]]为 <math>\left\{1,2,...,N\right\}</math>，从状态 <math>i</math> 到状态 <math>j</math> 的转移概率为 <math>w_{ij}</math>，转移矩阵为 <math>W=\left\{w_{ij}\right\}_{N \times N}</math>（详情请见[[复杂网络中的因果涌现]]词条）。

为了对网络的随机游走矩阵 <math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math> 进行降维与简化，研究者提出了一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。这里采用的是'''列归一化写法'''：每一列的和为 1，因此指标 <math>j</math> 表示出发节点，<math>i</math> 表示到达节点。该方法的核心在于选取随机矩阵前 <math>S</math> 个最大非平凡[[特征值]] <math>\lambda^2, \lambda^3, \ldots, \lambda^{S+1}</math> 对应的左[[特征向量]] <math>\langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} |</math>，将网络节点映射到这些特征向量张成的特征空间。在此基础上，将每个特征向量的值域划分为 <math>I</math> 个区间，在所有 <math>S</math> 个特征向量上都落入相同区间的节点会被合并为一个超级节点。

为了对网络的随机游走矩阵 <math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math> 进行降维与简化，研究者提出了一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。这里采用的是'''列归一化写法'''：每一列的和为 1，因此指标 <math>j</math> 表示出发节点，<math>i</math> 表示到达节点。该方法的核心在于选取随机矩阵前 <math>S</math> 个最大非平凡[[特征值]] <math>\lambda^2, \lambda^3, \ldots, \lambda^{S+1}</math> 对应的左[[特征向量]] <math>\langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} |</math>，将网络节点映射到这些[[特征向量]]张成的特征空间。在此基础上，将每个特征向量的值域划分为 <math>I</math> 个区间，在所有 <math>S</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><ref>Zhang, Zhang, et al. "Coarse-graining network flow through statistical physics and machine learning." Nature Communications 16.1 (2025): 1605.</ref>。

网络规模从 <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><ref>Zhang, Zhang, et al. "Coarse-graining network flow through statistical physics and machine learning." Nature Communications 16.1 (2025): 1605.</ref>。

马尔科夫链是描述状态仅依赖当前状态的随机过程，通过拉普拉斯矩阵与转移概率的关系，将上述方法应用到马尔科夫链中，在[[离散时间马尔科夫链]]中，转移概率矩阵为 <math>P</math>；在[[连续时间马尔科夫链]]中，<math>P(t)=e^{-tL}</math> 是经过时间 <math>t</math> 的转移概率矩阵。配分函数 <math>Z_t=Tr(e^{-tL})</math> 可以理解为马尔科夫链的所有状态的信息保留总和。

马尔科夫链是描述状态仅依赖当前状态的[[随机过程]]，通过拉普拉斯矩阵与转移概率的关系，将上述方法应用到马尔科夫链中，在[[离散时间马尔科夫链]]中，转移概率矩阵为 <math>P</math>；在[[连续时间马尔科夫链]]中，<math>P(t)=e^{-tL}</math> 是经过时间 <math>t</math> 的转移概率矩阵。配分函数 <math>Z_t=Tr(e^{-tL})</math> 可以理解为马尔科夫链的所有状态的信息保留总和。

进行稳态分析的时候，当 <math>t\rightarrow \infty</math> 时，<math>e^{-tL}</math> 的极限与[[稳态分布]]有关，配分函数的渐近行为反映链的长期信息保留特性。通过分析 <math>e^{-tL}</math> 的特征向量来识别马尔科夫链的状态聚类。

进行稳态分析的时候，当 <math>t\rightarrow \infty</math> 时，<math>e^{-tL}</math> 的极限与[[稳态分布]]有关，配分函数的渐近行为反映链的长期信息保留特性。通过分析 <math>e^{-tL}</math> 的特征向量来识别马尔科夫链的状态聚类。

#'''简洁性'''：字典中 CGU 的总数尽可能少。

#'''简洁性'''：字典中 CGU 的总数尽可能少。

#'''简单性'''：单个 CGU 的结构尽可能简单，由黑箱数 <math>H</math> 决定，<math>H</math> 越少越简单。 <math>H=I+O+2M</math>， <math>I</math> 为输入节点，<math>O</math> 为输出节点，<math>M</math> 为混合节点。

#'''简单性'''：单个 CGU 的结构尽可能简单，由黑箱数 <math>H</math> 决定，<math>H</math> 越少越简单。 <math>H=I+O+2M</math>， <math>I</math> 为输入节点，<math>O</math> 为输出节点，<math>M</math> 为混合节点。

#'''覆盖度'''：粗粒化后消除的节点和边数尽可能多，被CGU覆盖的节点数 <math>P_{covered}</math> 和边数 <math>E_{covered}</math> 尽可能多。

#'''覆盖度'''：粗粒化后消除的节点和边数尽可能多，被[[CGU]]覆盖的节点数 <math>P_{covered}</math> 和边数 <math>E_{covered}</math> 尽可能多。

针对CGU的评分函数：<math>S=[E_{covered}+\alpha P_{covered}]-[\alpha \sum_{i=1}^{N}n_i H_i+\beta N+\gamma\sum_{i=1}^{N} T_i]</math>

针对CGU的评分函数：<math>S=[E_{covered}+\alpha P_{covered}]-[\alpha \sum_{i=1}^{N}n_i H_i+\beta N+\gamma\sum_{i=1}^{N} T_i]</math>