812
个编辑
更改
跳到导航
跳到搜索
第399行：
第399行： − ===一致性Consistency=== − 这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]）之间的关系，以及它们与一致性的联系。 − Higher-order Macronodes，是由Jian Xu等人<ref name=":3">J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点划分方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。+ − − 我们通过一个简单的成块划分例子来展示：成块性的粗粒化与HOM是如何对应的。该例子的状态转移图如下图所示： − − [[文件:Lumpability例子示意图.png|缩略图|图6：例子示意图|替代=|500像素|无]] − − 与之相应的状态转移概率矩阵为： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{c:c:cc:c:c} − 0 & 0 & 0.3 & 0.1 & 0.6 & 0\\ − \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>是一个成块的划分。 − − − 首先，我们先按照成块性的粗粒化定义，计算对应的宏观转移概率： − <math> − \begin{aligned} − \left [ − \begin{array}{c:c:c:c:c} − 0 & 0 & 0.4 & 0.6 & 0\\ − \hdashline − 0 & 0 & 0.5 & 0 & 0.5\\ − \hdashline − 0 & 0 & 0.7 & 0.2 & 0.1\\ − \hdashline − 1.0 & 0 & 0 & 0 & 0\\ − \hdashline − 0 & 1.0 & 0 & 0 & 0\\ − \end{array} − \right ] − \end{aligned} − </math> − − 然后，我们简单介绍[[网络归并]]中构建宏观HOM转移概率矩阵的计算方法。 − − 在图（6）中，我们将节点3和4视为待合并的节点<math>A</math>。 − − 1. 计算合并节点的入流：对于其他节点到待合并节点<math>A</math>的连边（图（6）中绿色的连边），直接加和即可。例如，<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>到其他节点的连边（图（6）中棕色的连边），需要考虑三种情况： − #当待合并节点<math>A</math>间存在连边时； − #当待合并节点<math>A</math>指向同一个输出节点时； − #当待合并节点<math>A</math>指向不同输出节点时； − − 待合并节点<math>A</math>的出流的计算方式都不一样，如图（7）所示： − − [[文件:HOM示例.png|缩略图|图7：HOM节点边权合并示意图|替代=|800像素|无]] − − '''然而'''，我们注意到，这三种计算方式本质上都是对待合并节点<math>A</math>中各节点的出流<math>W_i^{out}</math>的加权求和。而成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的。所以，对相同的<math>W_i^{out}</math>进行任意加权平均的结果仍然是<math>W_i^{out}</math>。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。 − − 由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。''' 第719行：
第651行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
无编辑摘要
另一方面，<math>\Phi P'</math>的含义是将<math>P'</math>的每一行按照<math>\Phi</math>复制到对应的微观状态的行中。所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。
另一方面，<math>\Phi P'</math>的含义是将<math>P'</math>的每一行按照<math>\Phi</math>复制到对应的微观状态的行中。所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。
===一致性Consistency===
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
==成块性的相关概念==
这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]）之间的关系。Higher-order Macronodes，是由Jian Xu等人<ref name=":3">J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点划分方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
我们通过一个简单的成块划分例子来展示：成块性的粗粒化与HOM是如何对应的。该例子的状态转移图如下图所示：
[[文件:Lumpability例子示意图.png|缩略图|图6：例子示意图|替代=|500像素|无]]
与之相应的状态转移概率矩阵为：
<math>
\begin{aligned}
P = P_{s_i \rightarrow s_j} = \left [
\begin{array}{c:c:cc:c:c}
0 & 0 & 0.3 & 0.1 & 0.6 & 0\\
\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>是一个成块的划分。
首先，我们先按照成块性的粗粒化定义，计算对应的宏观转移概率：
<math>
\begin{aligned}
\left [
\begin{array}{c:c:c:c:c}
0 & 0 & 0.4 & 0.6 & 0\\
\hdashline
0 & 0 & 0.5 & 0 & 0.5\\
\hdashline
0 & 0 & 0.7 & 0.2 & 0.1\\
\hdashline
1.0 & 0 & 0 & 0 & 0\\
\hdashline
0 & 1.0 & 0 & 0 & 0\\
\end{array}
\right ]
\end{aligned}
</math>
然后，我们简单介绍[[网络归并]]中构建宏观HOM转移概率矩阵的计算方法。
在图（6）中，我们将节点3和4视为待合并的节点<math>A</math>。
1. 计算合并节点的入流：对于其他节点到待合并节点<math>A</math>的连边（图（6）中绿色的连边），直接加和即可。例如，<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>到其他节点的连边（图（6）中棕色的连边），需要考虑三种情况：
#当待合并节点<math>A</math>间存在连边时；
#当待合并节点<math>A</math>指向同一个输出节点时；
#当待合并节点<math>A</math>指向不同输出节点时；
待合并节点<math>A</math>的出流的计算方式都不一样，如图（7）所示：
[[文件:HOM示例.png|缩略图|图7：HOM节点边权合并示意图|替代=|800像素|无]]
'''然而'''，我们注意到，这三种计算方式本质上都是对待合并节点<math>A</math>中各节点的出流<math>W_i^{out}</math>的加权求和。而成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的。所以，对相同的<math>W_i^{out}</math>进行任意加权平均的结果仍然是<math>W_i^{out}</math>。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。
由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
==因果态==
详情请参考[[计算力学]]。
=参考文献=
=参考文献=