97
个编辑
更改
无编辑摘要
我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。
我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。
[[文件:Lumpability例子示意图.png|缩略图|图2：例子示意图]]
<math>
<math>
P = P_{s_i s_j} = \left [
P = P_{s_i s_j} = \left [
\begin{array}{c:c:cc:c:c}
\begin{array}{c:c:cc:c:c}
0 & 0 & 0.3 & 0.1 & 0.1 & 0.5\\
0 & 0 & 0.3 & 0.1 & 0.6 & 0\\
0 & 0 & 0.2 & 0.3 & 0.1 & 0.4\\
\hdashline
0 & 0 & 0.2 & 0.3 & 0 & 0.5\\
\hdashline
0 & 0 & 0 & 0.7 & 0.2 & 0.1\\
0 & 0 & 0.7 & 0 & 0.2 & 0.1\\
\hdashline
1.0 & 0 & 0 & 0 & 0 & 0\\
\hdashline
0 & 1.0 & 0 & 0 & 0 & 0\\
\end{array}
\right ]
\end{aligned}
</math>
对于这个转移概率矩阵，<math>{1, 2, {34}, 5, 6}</math>这个partition是lumpable的。
首先，我们先按照lumpability的定义，算对应的宏观转移概率：
<math>
\begin{aligned}
\left [
\begin{array}{c:c:c:c:c}
0 & 0 & 0.4 & 0.6 & 0\\
\hdashline
\hdashline
0.2 & 0.1 & 0.1 & 0.3 & 0.2 & 0.1\\
0 & 0 & 0.5 & 0 & 0.5\\
\hdashline
\hdashline
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0.7 & 0.2 & 0.1\\
0 & 0 & 0 & 0 & 0 & 1\\
\hdashline
1.0 & 0 & 0 & 0 & 0\\
\hdashline
0 & 1.0 & 0 & 0 & 0\\
\end{array}
\end{array}
\right ]
\right ]
</math>
</math>
[[文件:网络节点边权合并示意图.png|缩略图|图3：HON计算规则]]
然后，我们来简单的介绍一下的构建宏观HON转移概率矩阵的计算方法。
在图2中，我们看到3和4为待合并节点<math>S</math>。
1. 对于其他节点到待合并节点<math>S</math>的连边，即待合并节点的入流（图2中绿色的连边），我们直接加和即可，即<math>p_{1->S} = 0.3+0.1=0.4</math>，<math>p_{2->S} = 0.2+0.3=0.5</math>
2. 对于待合并节点<math>S</math>到其他节点的连边，即待合并节点的出流（图2中棕色的连边），我们需要考虑三种情况：
#当待合并节点<math>S</math>间存在连边时；
#指向同一个输出节点时；
#当待合并节点<math>S</math>指向不同输出节点时；
待合并节点<math>S</math>的出流的计算方式都不一样，如图3所示。
'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>S</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，lumpability的特性决定了，群组里的各节点的出流<math>W_i^{out}</math>都是一样的。也就是说，任意的加权方法对于lumpable partition来说都能得出相同的结果。
由此，我们总结，lumpable partition的聚合方式和HON，无论入流还是出流都完全一致。
==基于Lumpability的粗粒化方法==
==基于Lumpability的粗粒化方法 ==
[[文件:Lump fig1.png|缩略图|398x398像素|图2：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
[[文件:Lump fig1.png|缩略图|398x398像素|图4：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图2中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。
由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图4中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图2中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
但是，有时候有些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>）。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。