更改

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化coarse-graining，聚类/聚合partitioning/lumping/clustering/aggregation和降维dimension reduction是重叠等价的。

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化coarse-graining，聚类/聚合partitioning/lumping/clustering/aggregation和降维dimension reduction是重叠等价的。

多数文献中会出现如图一的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：

多数文献中会出现如图1的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：

[[文件:马尔科夫链粗粒化定义.png|替代=|缩略图|图1：粗粒化定义]]

[[文件:马尔科夫链粗粒化定义.png|替代=|缩略图|图1：粗粒化定义]]

对状态空间<math>S</math>和转移函数<math>T(t):S \rightarrow S</math>，我们需要一个投影矩阵<math>R:S \rightarrow S'</math>，和一个新的转移函数<math>T'(t):S' \rightarrow S'</math>，而且<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。

对状态空间<math>S</math>和转移函数<math>T(t):S \rightarrow S</math>，我们需要一个投影矩阵<math>R:S \rightarrow S'</math>，和一个新的转移函数<math>T'(t):S' \rightarrow S'</math>，而且<math>S'</math>和<math>T'</math>要符合马尔科夫链定义。

我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。

我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。

[[文件:Lumpability例子示意图.png|缩略图|图2：例子示意图]]

[[文件:Lumpability例子示意图.png|缩略图|图3：例子示意图|替代=]]

<math>

<math>

然后，我们来简单介绍一下的构建宏观HOM转移概率矩阵的计算方法。

然后，我们来简单介绍一下的构建宏观HOM转移概率矩阵的计算方法。

在图2中，我们看到3和4为待合并节点<math>A</math>。

在图3中，我们看到3和4为待合并节点<math>A</math>。

1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图2中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>

1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图3中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>

2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图2中棕色的连边），我们需要考虑三种情况：

2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图3中棕色的连边），我们需要考虑三种情况：

#当待合并节点<math>A</math>间存在连边时；

#当待合并节点<math>A</math>间存在连边时；

#当待合并节点<math>A</math>指向同一个输出节点时；

#当待合并节点<math>A</math>指向同一个输出节点时；

#当待合并节点<math>A</math>指向不同输出节点时；

#当待合并节点<math>A</math>指向不同输出节点时；

待合并节点<math>A</math>的出流的计算方式都不一样，如图3所示。

待合并节点<math>A</math>的出流的计算方式都不一样，如图4所示。

[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]

[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]

==基于Lumpability的粗粒化方法（未给定lumpable partition的情况）==

==基于Lumpability的粗粒化方法（未给定lumpable partition的情况）==

[[文件:Lump fig1.png|缩略图|398x398像素|图4：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]

[[文件:Lump fig1.png|缩略图|398x398像素|图5：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]

由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图4中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。

由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图5中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。

但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图4中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。

但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图5中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图5中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。

我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。

我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。

====动力学可逆性 v.s. Lumpability====

====动力学可逆性 v.s. Lumpability====

在lumpability的图1中我们提到了lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。

在lumpability的图5中我们提到了lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。

在没有明显block结构的情况下，我们可以使用上述的SVD+kMeans方式找到最优的lumpability partition并决定它的lumpability。我们在一个动力学可逆性比较高（有明显的因果涌现）的国际贸易网的例子上尝试了一下，却发现该网络上的最优lumpability partition宏观结果的动力学可逆性并不高。这现象说明：

在没有明显block结构的情况下，我们可以使用上述的SVD+kMeans方式找到最优的lumpability partition并决定它的lumpability。我们在一个动力学可逆性比较高（有明显的因果涌现）的国际贸易网的例子上尝试了一下，却发现该网络上的最优lumpability partition宏观结果的动力学可逆性并不高。这现象说明：