812
个编辑
更改
跳到导航
跳到搜索
第244行：
第244行： + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 第459行：
第564行： − − − ===成块划分和粗粒化的一致性Consistency=== − − 这一小节里我们讨论一下，对一个马尔科夫链的成块的划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。 − − 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>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。 − − 我们这里使用一个简单的成块的划分的例子，来显示成块性的粗粒化跟HON是对应的。 − − [[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]] − − <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转移概率矩阵的计算方法。 − − 在图4中，我们看到3和4为待合并节点<math>A</math>。 − − 1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图4中绿色的连边），我们直接加和即可，即<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>到其他节点的连边，即待合并节点的出流（图4中棕色的连边），我们需要考虑三种情况： − #当待合并节点<math>A</math>间存在连边时； − #当待合并节点<math>A</math>指向同一个输出节点时； − #当待合并节点<math>A</math>指向不同输出节点时； − − 待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。 − − [[文件:网络节点边权合并示意图.png|替代=|411x411像素]] − − '''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于成块的划分来说都能得出相同的结果。 − − 由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。''' − − − − 我们得出这个结论的目标是，借助HOM方法的一致性的性质，说明成块性的聚合方式，也有一致性的性质。 − − 以下关于'''网络动力学的一致性'''的描述节选自[[复杂网络中的因果涌现]]： − − 定义微观网络<math>G </math>与宏观网络<math>G_M </math>，在两个网络上[[随机游走]]，在未来某个时间<math>t </math> ， <math>G </math>上的预期分布为 <math>P_m(t) </math>， <math>G_M </math>上的预期分布为 <math>P_M(t) </math>。 − − 将<math>P_m(t) </math>分布叠加到宏观上<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。用<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为： − − <math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math> − − 也就是说，Inconsistency 等于 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。 − − 实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。 − − 回到上面成块的划分 等于HOM的推断，我们就能得出，'''根据成块性而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。'''
无编辑摘要
==成块性满足的性质==
===宏观最大预测性===
===成块划分和粗粒化的可交换性===
[[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化定义]]
图3展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
#先进过微观动力学达到<math>s^{(t+1)}</math>，再做粗粒化得到<math>A^{(t+1)}</math>
#先做粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math>
可交换性是指，无论从哪个微观状态分布出发，我们走两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，也就是说，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
===一致性Consistency===
这一小节里我们讨论一下，对一个马尔科夫链的成块的划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。
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>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
我们这里使用一个简单的成块的划分的例子，来显示成块性的粗粒化跟HON是对应的。
[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]
<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转移概率矩阵的计算方法。
在图4中，我们看到3和4为待合并节点<math>A</math>。
1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图4中绿色的连边），我们直接加和即可，即<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>到其他节点的连边，即待合并节点的出流（图4中棕色的连边），我们需要考虑三种情况：
#当待合并节点<math>A</math>间存在连边时；
#当待合并节点<math>A</math>指向同一个输出节点时；
#当待合并节点<math>A</math>指向不同输出节点时；
待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。
[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]
'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于成块的划分来说都能得出相同的结果。
由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
我们得出这个结论的目标是，借助HOM方法的一致性的性质，说明成块性的聚合方式，也有一致性的性质。
以下关于'''网络动力学的一致性'''的描述节选自[[复杂网络中的因果涌现]]：
定义微观网络<math>G </math>与宏观网络<math>G_M </math>，在两个网络上[[随机游走]]，在未来某个时间<math>t </math> ， <math>G </math>上的预期分布为 <math>P_m(t) </math>， <math>G_M </math>上的预期分布为 <math>P_M(t) </math>。
将<math>P_m(t) </math>分布叠加到宏观上<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。用<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为：
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
也就是说，Inconsistency 等于 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。
实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。
回到上面成块的划分 等于HOM的推断，我们就能得出，'''根据成块性而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。'''