基于可逆性的因果涌现理论

基于可逆性的因果涌现理论是一种量化因果涌现强度的新框架，该方法基于奇异值分解和动力学可逆性的概念，提出了近似动力学可逆性[math]\displaystyle{ \Gamma_{\alpha} }[/math]，[math]\displaystyle{ \Gamma_{\alpha} }[/math]可用于量化因果涌现的强度。经过理论推导和数值实验证明，在对因果涌现的判断和量化上，该理论与基于有效信息(EI)的因果涌现理论具有相同的效果，且[math]\displaystyle{ \Gamma_{\alpha} }[/math]和EI在多个方面存在相似之处。此外，该理论还提出了基于SVD的粗粒化方法并进行实验，证明了该粗粒化方法的有效性。

简介

基于可逆性的因果涌现理论的核心概念是近似动力学可逆性： [math]\displaystyle{ \begin{align} \Gamma_{\alpha}=\sum_{i=1}^{N}\sigma_{i}^{\alpha}\tag{3}\end{align} }[/math] 其中[math]\displaystyle{ \sigma_{i} }[/math]是矩阵P的第i个奇异值。[math]\displaystyle{ \alpha\in(0,2) }[/math]是参数。 借助[math]\displaystyle{ \Gamma_{\alpha} }[/math]可以定义清晰因果涌现和模糊因果涌现的概念，形成完整的量化因果涌现方法。

基本概念

下面介绍该理论的几个基本概念，分别是动力学可逆性、近似动力学可逆性、清晰因果涌现和模糊因果涌现。

动力学可逆性

对于给定的马尔可夫链[math]\displaystyle{ \chi }[/math]和对应的转移概率矩阵(TPM) P ，如果P同时满足：1. P是可逆矩阵，即存在矩阵[math]\displaystyle{ P^{-1} }[/math]，使得[math]\displaystyle{ PP^{-1}=I }[/math]； 2. [math]\displaystyle{ P^{-1} }[/math]也是另一个马尔可夫链[math]\displaystyle{ \chi^{-1} }[/math]的有效TPM，则[math]\displaystyle{ \chi }[/math]和P 可以称为动力学可逆的。

定理1：对于一个给定的马尔科夫链[math]\displaystyle{ \chi }[/math]和对应的TPM P，当且仅当P是置换矩阵的时候，P是严格动力学可逆的。

证明见参考文献

纯粹的置换矩阵在所有可能的TPM中非常稀少，所以大多数的TPM并不是严格动力学可逆的。因此，需要一个指标来刻画任意一个TPM接近动力学可逆的程度。

考虑P的秩r，当且仅当r<N的时候，P是不可逆的；且P越退化对应着越小的r。然而，非退化（满秩）的矩阵P并不总是动力学可逆的，因为：1. 尽管[math]\displaystyle{ P^{-1} }[/math]存在，但[math]\displaystyle{ P^{-1} }[/math]并不一定是满足归一化条件（P的第i行向量[math]\displaystyle{ P_{i} }[/math]的第一范数应该为1）的合法TPM。2. 如前所述，若P满足动力学可逆性，则P必为置换矩阵。

所有置换矩阵的行向量都是one-hot向量（即只有一个元素是1，其余元素均为零的向量）。这一特性可以被矩阵P的弗罗贝尼乌斯范数（Frobenius norm）刻画。事实上，当且仅当P的行向量是one-hot向量的时候，矩阵P的弗罗贝尼乌斯范数取最大值。因此，我们可以借由矩阵P的秩r和矩阵的弗罗贝尼乌斯范数共同定义P的近似动力学可逆性。

首先，矩阵的秩可以被写作：

[math]\displaystyle{ \begin{align} r=\sum_{i=1}^{N}\sigma_{i}^{0}\tag{1} \end{align} }[/math]

其中[math]\displaystyle{ \sigma_{i} }[/math]是矩阵P的第i个奇异值。

紧接着，矩阵的弗罗贝尼乌斯范数可以被写作：

[math]\displaystyle{ \begin{align} {||P||}_{F}^{2}=\sum_{i=1}^{N}\sigma_{i}^{2}\tag{2} \end{align} }[/math]

这也是所有奇异值的平方和。可以看出矩阵的秩和弗罗贝尼乌斯范数都与奇异值相联系。

近似动力学可逆性

下面定义矩阵P的近似动力学可逆性：

假设马尔科夫链的概率转移矩阵为P，奇异值为[math]\displaystyle{ (\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0) }[/math]，那么矩阵P的[math]\displaystyle{ \alpha }[/math]阶近似动力学可逆性定义为：

[math]\displaystyle{ \begin{align} \Gamma_{\alpha}=\sum_{i=1}^{N}\sigma_{i}^{\alpha}\tag{3}\end{align} }[/math]

其中[math]\displaystyle{ \alpha\in(0,2) }[/math]是参数。

实际上，当[math]\displaystyle{ \alpha\ge1 }[/math]时，[math]\displaystyle{ \Gamma_{\alpha} }[/math]是P的沙滕范数（Schatten norm）；当[math]\displaystyle{ 0\lt \alpha\lt 1 }[/math]时，[math]\displaystyle{ \Gamma_{\alpha} }[/math]是P的准范数（quasinorm）。

使用这个定义来刻画近似动力学可逆性是合理的，因为完全动力学可逆性可以通过最大化[math]\displaystyle{ \Gamma_{\alpha} }[/math]来得到。

定理2：对于任意[math]\displaystyle{ \alpha\in(0,2) }[/math]，[math]\displaystyle{ \Gamma_{\alpha} }[/math]的最大值是N，当且仅当P是置换矩阵的时候能取到该最大值.

更进一步来说，可以证明，[math]\displaystyle{ \Gamma_{\alpha} }[/math]的下界可以由[math]\displaystyle{ {||P||}_{F}^{\alpha} }[/math]确定。

决定性和简并性

通过调整参数[math]\displaystyle{ \alpha\in(0,2) }[/math]，我们可以使更好地反映P的确定性或者简并性。当[math]\displaystyle{ \Gamma_{\alpha}\to0,\Gamma_{\alpha} }[/math]收敛到P的秩，这类似于EI定义中的非简并项，因为随着P越来越退化，r越来越小。然而，定义不允许[math]\displaystyle{ \alpha }[/math]精确为零，因为rank(P)不是P的连续函数，而且最大化秩不会导致置换矩阵。同样，当[math]\displaystyle{ \Gamma_{\alpha}\to2 }[/math]时，[math]\displaystyle{ \Gamma_{\alpha} }[/math]收敛到[math]\displaystyle{ {||P||}_{F}^{2} }[/math]，但是定义不允许[math]\displaystyle{ \alpha }[/math]取2，因为[math]\displaystyle{ \Gamma_{\alpha=2} }[/math]的最大化并不意味着P是可逆的。[math]\displaystyle{ {||P||}_{F} }[/math]与EI定义中的确定性项具有可比性，因为当P具有越来越多的one-hot向量，P的中的最大转移概率也会变得更大，意味着动力学变得更加可逆。

在实践中，我们总是取[math]\displaystyle{ \alpha=1 }[/math]来平衡[math]\displaystyle{ \Gamma }[/math]测量确定性和简并性的倾向，[math]\displaystyle{ \Gamma_{\alpha=1} }[/math]被称为核范数。

考虑到[math]\displaystyle{ \alpha=1 }[/math]的重要性，我们将主要展示[math]\displaystyle{ \alpha=1 }[/math]的结果，在下文中，我们将[math]\displaystyle{ \Gamma_{\alpha=1} }[/math]记作[math]\displaystyle{ \Gamma }[/math]。

归一化

[math]\displaystyle{ \Gamma_{\alpha=1} }[/math]受矩阵的大小影响，所以我们需要进行归一化，从而刻画与大小无关的近似动力学可逆性，这样可以更方便地在不同大小的马尔科夫链之间进行比较。

[math]\displaystyle{ \begin{align} \gamma_{\alpha}=\frac{\Gamma_{\alpha}}{N}\end{align} }[/math]

容易证明，[math]\displaystyle{ \gamma_{\alpha} }[/math]总是小于1。

与有效信息（EI）的联系

一方面，EI 表征了马尔可夫链的因果效应强度；另一方面，[math]\displaystyle{ \Gamma_{\alpha} }[/math]可以定量地捕捉马尔可夫链的近似动态可逆性。基于可逆性的因果涌现理论认为，因果关系和可逆性之间有着深刻的联系。首先，如下定理所述，EI 和[math]\displaystyle{ \log\Gamma_{\alpha} }[/math] 有相同的最小值和最大值。

定理3: 对于任意 TPM P 和 [math]\displaystyle{ \alpha\in(0,2) }[/math]，[math]\displaystyle{ \Gamma_{\alpha} }[/math]的对数和EI都有相同的最小值0和一个共同的最小值[math]\displaystyle{ P=\frac{1}{N}I_{N\times{N}} }[/math]。它们还有相同的最大值[math]\displaystyle{ \log{N} }[/math]，最大值点对应于P是一个置换矩阵。

证明见参考文献附录A.3

因此当P是可逆的（置换矩阵）时，[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]和EI可以达到最大值[math]\displaystyle{ \log{N} }[/math]。当[math]\displaystyle{ P_{i}=\frac{I}{N},\forall{i}\in[1,N] }[/math]，它们也可以达到最小值0。然而，我们可以证明[math]\displaystyle{ \frac{I}{N} }[/math]并不是EI的唯一最小点,对于任何满足[math]\displaystyle{ P_{i}=P_{j},\forall{i}\in{[1,N]} }[/math]的TPM都能使EI=0.其次EI的上限和下限都是[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]的线性项。这一点由下面的定理证明。

定理4：对于任何TPM P，其有效信息EI的上限为[math]\displaystyle{ \frac{2}{\alpha}\log{\Gamma_{\alpha}} }[/math]，下限为[math]\displaystyle{ \log{\Gamma_{\alpha}}-\log{N} }[/math].

证明见参考文献附录A.3.

因此，我们有如下不等式：

[math]\displaystyle{ \log{\Gamma_{\alpha}}-\log{N}\le{EI}\le\frac{2}{\alpha}\log{\Gamma_{\alpha}} }[/math]

实际上，EI有一个更严格的上限，[math]\displaystyle{ EI\le\log{\Gamma_{\alpha}} }[/math],这个上限是由数值实验的结果确定的。我们发现在许多例子中，EI和[math]\displaystyle{ \log\Gamma_{\alpha} }[/math],因此，基于可逆性的因果涌现理论主张：

[math]\displaystyle{ EI\sim\log\Gamma_{\alpha}. }[/math]

因果涌现的新定义

定义因果涌现强度

对于具有TPM P的给定马尔可夫链[math]\displaystyle{ \chi }[/math]，如果[math]\displaystyle{ r≡rank(P)\lt N }[/math]，则该系统中会出现明显的因果涌现。且因果涌现的程度为：

[math]\displaystyle{ \Delta\Gamma_{\alpha}=\Gamma_{\alpha}\cdot(\frac{1}{r}-\frac{1}{N}) }[/math]

定义模糊因果涌现

对于具有TPM P的给定马尔可夫链[math]\displaystyle{ \chi }[/math]，假设其奇异值为[math]\displaystyle{ (\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0) }[/math]。对于给定实值[math]\displaystyle{ \epsilon\in[0,\epsilon_{1}] }[/math]，如果存在整数[math]\displaystyle{ i\in[1, N) }[/math]，使得[math]\displaystyle{ \sigma_{i}\gt \epsilon }[/math]，则系统中出现了模糊因果涌现，其模糊程度为[math]\displaystyle{ \epsilon }[/math]。而因果涌现的程度为：

[math]\displaystyle{ \Delta\Gamma_{\alpha}(\epsilon)=\frac{\sum_{i=1}^{r_{\epsilon}}\sigma_{i}^{\alpha}}{r_{\epsilon}}-\frac{\sum_{i=1}^{N}\sigma_{i}^{\alpha}}{N}, }[/math]

其中[math]\displaystyle{ r_{\epsilon}=max\{ i| \sigma_{i} \gt \epsilon\} }[/math]

这些定义与任何粗粒化方法无关。因此，它代表了马尔可夫动力学的内在客观属性。因此，清晰和模糊因果涌现的程度都可以客观地量化。

当[math]\displaystyle{ \epsilon=0 }[/math]时，清晰因果涌现是模糊因果涌现的特例，特别是当奇异值可以分析求解时，它具有理论价值。此外，对因果涌现发生的判断与[math]\displaystyle{ \alpha }[/math]无关，因为它只与秩有关。因此，清晰因果涌现的概念仅由P决定，是无参数的。

在实际应用中，必须给出阈值[math]\displaystyle{ \epsilon }[/math]，因为奇异值可能无限趋近于0，但P是全秩的。可以根据奇异值频谱中的明显截止点来选择[math]\displaystyle{ \epsilon }[/math]。若[math]\displaystyle{ \epsilon }[/math]非常小（比如[math]\displaystyle{ \epsilon\lt {10}^{-10} }[/math]），我们也可以说因果涌现大致发生。

对于任意[math]\displaystyle{ \epsilon\ge{0},\Delta\Gamma_{\alpha}(\epsilon)\in[0,N-1]. }[/math]只有当[math]\displaystyle{ \Delta\Gamma_{\alpha}(\epsilon)\gt 0 }[/math]时，才会出现因果涌现。命题和证明见参考文献附录A.3.1。

[math]\displaystyle{ \Gamma }[/math]和EI的比较

相似性

在2.3节中，我们推导出EI的上界和下界分别是[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]的线性项，并推测了两者的近似关系：[math]\displaystyle{ EI\sim\log{\Gamma_{\alpha}} }[/math]。接下来我们将通过数值模拟证明这一点。

我们在由三种不同方法生成的各种归一化TPM 上比较了[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]和 EI：1）软化置换矩阵；2）软化退化矩阵；3）完全随机矩阵。这些生成模型的详情见附录 B。结果如图1 所示。如图1(a)、(b)和(c)所示，在所有这些例子中都观察到了正相关性，并且在N ≫ 1 时，[math]\displaystyle{ EI\sim\log{\Gamma_{\alpha}}. }[/math]的近似关系得到了证实。在图1(a) 和 (b) 中可以明显观察到这种关系，但在图1(b) 中，由于覆盖了有限的[math]\displaystyle{ \Gamma }[/math]值区域，这种关系退化为近似线性关系。关于不同α的更多结果，请参阅附录B.1节。

我们还在图1(a)和(b)中用红色虚线表示了 EI 的上下限。不过，在图1（c）中，由于所有点都集中在一个小区域内，因此看不到理论边界线。根据经验，图1 中灰色断线所示的对数[math]\displaystyle{ \log{\Gamma_{\alpha}} }[/math]的EI上限更为严格。因此，我们推测 [math]\displaystyle{ EI\le\log{\Gamma_{\alpha}} }[/math]这一新关系是成立的，但其严密性有待今后的工作来证明。

我们还在大小为N=2 的最简单参数化TPM中得到了EI和[math]\displaystyle{ \Gamma }[/math]的解析解，并展示了EI和[math]\displaystyle{ \Gamma }[/math]与参数p和q的关系。图1(c)和(d)之间的差异显而易见：1）当[math]\displaystyle{ p\approx 1-q }[/math]时，[math]\displaystyle{ \Gamma }[/math]有一个峰值，但EI没有；2）观察到EI ≈ 0时的区域更宽，而[math]\displaystyle{ \Gamma\approx 1 }[/math]时的区域要小得多；3）观察到[math]\displaystyle{ \Gamma }[/math]有一个从0到最大N=2的渐进过渡，但EI没有。 因此，我们得出结论，EI和[math]\displaystyle{ \Gamma }[/math]在各种TPM上高度相关。

图1

不同

尽管已经发现 EI 和[math]\displaystyle{ \Gamma_{\alpha} }[/math]之间存在深层联系，但这两个指标之间仍然存在差异。 首先，EI 通过KL散度来量化每个行向量与P的平均行向量之间的差异。换句话说，EI衡量行向量之间的相似性。相反，[math]\displaystyle{ \Gamma_{\alpha} }[/math]评估动态可逆性，特别是当[math]\displaystyle{ \alpha \lt nowiki\gt }[/math]接近 0 时，这与行向量之间的线性相互依赖性相关。虽然行向量的线性相互依赖性表明它们的相似性——这意味着两个相同的行向量是线性相关的，但反之则不一定成立。因此，[math]\displaystyle{ \Gamma_{\alpha} }[/math]不仅捕获了行向量之间的相似性，而且还捕获了P与动态可逆矩阵的接近度。相比之下，EI无法完成这个任务。

可以通过以下数值实验来验证这一点：我们可以通过将线性相关行向量与线性独立行向量混合来创建TPM，其中独立向量的数量或等级是受控参数。最初，我们生成r个独立的 one-hot 向量，然后使用与附录B.1中描述的相同方法软化这些行向量，软化程度由[math]\displaystyle{ \sigma }[/math]确定。随后，我们通过将这些软化的 one-hot 向量与随机选择的线性系数线性组合来创建额外的行向量。然后我们量化[math]\displaystyle{ \Gamma }[/math]和 EI 之间的差异，结果如图1(d) 所示。

很明显，对于较小的r值，随着[math]\displaystyle{ \sigma }[/math]的增加，[math]\displaystyle{ \log{\Gamma} }[/math]和 EI 之间的差异会减小，因为 P 的线性依赖性随着向量变得更加明显而增强。这强调了线性相关性并不等于行向量之间的相似性。然而，随着独立行向量数量的增加，如果[math]\displaystyle{ \sigma }[/math]保持很小，P会收敛到置换矩阵。因此，EI 和[math]\displaystyle{ \log{\Gamma} }[/math]都达到相同的最大值。这解释了为什么当r很大时会出现轻微的颠簸。

其次，即使在所有行向量相同的情况下，EI 和[math]\displaystyle{ \Gamma_{\alpha} }[/math]之间也存在显着区别，导致 EI= 0 而[math]\displaystyle{ \Gamma_{\alpha}= ||\overline{P}||^{\alpha}\cdot N^{\alpha /2} }[/math]，而这是一个可以随[math]\displaystyle{ ||\overline{P}|| }[/math]变化的量（参见引理 4，附录 A.2）。这种差异意味着，与 EI 不同，[math]\displaystyle{ \Gamma_{\alpha} }[/math]可以提供有关行向量的更全面的见解，超越其与平均行向量的相似性。

量化因果涌现

下面基于Hoel等人的论文中提出的几种布尔网络马尔可夫动力学来测试清晰和模糊因果涌现的定义。

图2

图2(a-i)分别显示了从具有相同节点机制的相同布尔网络模型生成的用于因果涌现和模糊因果涌现的TPM的两个示例。图2(d)中的TPM直接源自图2(a)和(b)中的布尔网络及其节点机制。它们的奇异值谱分别如图2(e)和(h)所示。(d)中的第一个例子只有4个非零奇异值(图2(e))，因此，出现明显的因果涌现，且因果涌现的程度为[math]\displaystyle{ \Delta\Gamma=0.75 }[/math]。 因果涌现的判断与参考文献相同。

图2(g)中的TPM可以显示出模糊的因果涌现，这是在(d)中的TPM上添加强度为（std = 0.03）的随机高斯噪声后得到的。因此，奇异频谱如图2(h) 所示。我们选择[math]\displaystyle{ \epsilon=0.2 }[/math]作为阈值，这样就只剩下4个大的奇异值。因果涌现程度为[math]\displaystyle{ \Delta\Gamma(0.2)=0.69 }[/math]。[math]\displaystyle{ \epsilon }[/math]值是根据图2(h)中的奇异值频谱选择的，在图2(h)中可以观察到指数为3和[math]\displaystyle{ \epsilon=0.2 }[/math]时有一个明显的分界点。图3（a-f）显示了另一个更复杂的布尔网络模型的明显因果涌现例子，该模型来自参考文献，其中具有相同节点机制的6个节点可归类为3个超级节点，以显示因果涌现。原始布尔网络模型的相应TPM如图3(c)所示。奇异值频谱如图3（d）所示，其中有8个非零值。这个清晰因果涌现的度数为[math]\displaystyle{ \Delta\Gamma=2.23 }[/math]。对因果涌现的判断与相同。参考文献和中有关布尔网络的更多例子可参阅附录第 E.1 节。

图3

对因果涌现的量化可应用于复杂网络（图2(j-l)）和细胞自动机（图3(g-i)）。图2（j-l）显示了由随机块模型（SBM）生成的具有三组参数（内部或内部连接概率）的复杂网络的模糊因果涌现例子。TPM是通过对网络的邻接矩阵按每个节点的度进行归一化得到的。图2(j)显示了一个有 100 个节点和 5 个区块（社区）的示例网络，图2(k)显示了其奇异值频谱，在与区块数相同的横坐标上可以观察到一个明显的分界点[math]\displaystyle{ (\epsilon=0.3,r_{\epsilon}=5) }[/math]。我们可以确定，在这个网络模型中出现了模糊的因果涌现，程度为[math]\displaystyle{ \Delta\Gamma(0.3)=0.56 }[/math]。同图中还显示了两个由SBM生成的网络光谱，它们的大小和块数相同，但参数不同。

如图3（g-i）所示，关于清晰因果涌现的定义可应用于元胞自动机，以发现其局部涌现结构。在这个例子里刻画了元胞自动机（编号40的基本一维元胞自动机）局部TPM的清晰因果涌现。局部TPM 由包括每个单元及其两个相邻单元的局部窗口获得。图3(h) 显示了这些局部 TPM 的奇异值的可能频谱，在这些频谱中可能出现也可能不出现清晰因果涌现。图3(i)用红点标记显示了所有单元和时间步长的清晰因果涌现分布（[math]\displaystyle{ \Delta\Gamma }[/math]）。我们还绘制了该自动机的原始演化作为背景。

基于SVD分解的粗粒化策略

虽然无需粗粒化也能定义和量化清晰或模糊的因果涌现现象，但需要对原始系统进行更简单的粗粒化描述，以便与 EI 得出的结果进行比较。因此，我们还提供了一种基于P的奇异值分解的简明粗粒度方法，以获得宏观层面的简化TPM。其基本思想是将 P 中的行向量 [math]\displaystyle{ P_{i},\forall i \in [1,N] }[/math]投影到[math]\displaystyle{ P\cdot P^{T} }[/math]的特征向量张成的子空间上，从而保留P的主要信息，并保持[math]\displaystyle{ \Gamma }[/math]不变。

粗粒化方法包括五个步骤：1) 对TPM进行SVD分解；2)选择一个[math]\displaystyle{ \epsilon }[/math]作为阈值来切断奇异值谱，并得到[math]\displaystyle{ r_{\epsilon} }[/math]作为保留状态的个数；3)通过计算[math]\displaystyle{ P\cdot V_{N\times r_{\epsilon}} }[/math]对P中的所有Pi进行降维，其中[math]\displaystyle{ V_{N\times r_{\epsilon}} }[/math]由[math]\displaystyle{ P\cdot P^{T} }[/math]的前[math]\displaystyle{ r_{\epsilon} }[/math]特征向量构成；4) 将[math]\displaystyle{ P\cdot V_{N\times r_{\epsilon}} }[/math]中的所有行向量聚类为[math]\displaystyle{ r_{\epsilon} }[/math]组，得到投影矩阵[math]\displaystyle{ \Phi }[/math]；以及 5) 利用[math]\displaystyle{ \Phi }[/math]和P得到新的TPM，使总静态通量保持不变。有关此方法的详细信息及其工作原理，请参阅附录 D。

我们在图2 和图3 所示的所有示例中测试了我们的方法。首先，对于根据图2(d) 和 (g) 所示的相同布尔网络模型生成的两个 TPM，其粗 TPM 分别如图2(f)和(i)所示。从TPM和投影矩阵[math]\displaystyle{ \Phi }[/math]中可以读出宏观布尔网络模型（图2(c)）。值得注意的是，粗TPM中的[math]\displaystyle{ \Gamma }[/math]与原始模型中的[math]\displaystyle{ \Gamma }[/math]几乎完全相同，这说明我们的方法在这种情况下是[math]\displaystyle{ \Gamma }[/math]保守的。我们进一步测试了参考文献和中的因果涌现例子，可以得到几乎相同的粗TPM。其次，如图3(e) 所示，用相同的粗粒度方法可以得到原始TPM（图3(a)）的缩小TPM，投影矩阵[math]\displaystyle{ \Phi }[/math]如 (f) 所示。如图3（b）所示，粗粒度布尔网络可以从简化的TPM和投影矩阵中读出。在本例中，虽然由于粗粒化过程中的信息损失，[math]\displaystyle{ \Gamma }[/math]被大大缩小了（从 [math]\displaystyle{ \Gamma =20.39 }[/math]缩小到[math]\displaystyle{ \Gamma=8.0 }[/math]），但归一化的近似动态可逆性却增加了（从 [math]\displaystyle{ \gamma =0.32 }[/math]增加到[math]\displaystyle{ \gamma =1.0 }[/math]）。同样的粗粒化方法也适用于SBM生成的复杂网络。图2(l)显示了从原始网络（图2(j)）衍生出的 5 节点精简网络。图2(l)显示了从原始网络（图2(j)）得到的具有 5 个节点的缩小网络（图2(l)）。并观察到具有相关性的[math]\displaystyle{ \Gamma }[/math]大幅下降和[math]\displaystyle{ \gamma }[/math]大幅上升。这表明在粗粒化过程中损失了大量信息，同时可以得到一个相对更有效的小型网络模型，具有更强的归一化近似动态可逆性。

附录

引理1：对于一个概率转移矩阵TPM [math]\displaystyle{ P=(P_{1}，P_{2}，...,P_{N})^{T} }[/math]，其中[math]\displaystyle{ P_{i} }[/math]是第i个行向量，那么：

[math]\displaystyle{ P_{i}\cdot P_{j}\le 1, \forall i,j\in [1,N] }[/math]

证明: 由于Pi是概率分布，因此它应满足归一化条件，可表示为：

[math]\displaystyle{ |P_{i}|_{1}=\sum_{j=1}^{N} p_{ij}=1 }[/math]

其中[math]\displaystyle{ |\cdot|_{1} }[/math]是矢量的一阶范数，它被定义为所有元素的绝对值的总和。因此： [math]\displaystyle{ P_{i}\cdot P_{j}=|P_{i}\cdot P_{j}|_{1}\le \cdot |P_{i}|_{1}\cdot |P_{j}|_{1}=1 }[/math]

引理2：对于TPM P，我们可以用如下形式书写：

[math]\displaystyle{ P=(P_{1},P_{2},...,P_{N})^{T} }[/math]

其中Pi是第i个行向量。然后假设P的奇异值为[math]\displaystyle{ (\sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{N}\ge0) }[/math]，那么，若：[math]\displaystyle{ P_{i}\cdot P_{i}=1, \forall i\in [1,N], }[/math]

那么P的所有奇异值满足：

[math]\displaystyle{ \sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{r}\ge 1 }[/math] 以及 [math]\displaystyle{ \sigma_{r+1}=\sigma_{r+2}=...=\sigma_{N}=0 }[/math] 其中r是矩阵P的秩。

证明:如果[math]\displaystyle{ P_{i}\cdot P_{i}=1 }[/math]，则[math]\displaystyle{ \sum_{j} p^{2}_{ij}=1 }[/math]，这意味着Pi是模为1的单位向量。而对于所有i[math]\displaystyle{ |P_{i}|_{1}=\sum_{j=1}^{N} p_{ij}=1 }[/math]，因此Pi必须为独热向量。因此，P存在两种情况：1.存在[math]\displaystyle{ 1≤i,j≤ N }[/math]，使得[math]\displaystyle{ Pi=Pj }[/math]；2.对于任意[math]\displaystyle{ 1≤ i,j≤ N，Pi\neq Pj }[/math]。

情况一：若[math]\displaystyle{ P_{i}=P_{j} }[/math]且因为它们都为独热向量，所以[math]\displaystyle{ P_{i}\cdot P_{j}=1 }[/math]以及[math]\displaystyle{ P_{j}\cdot P_{i}=1 }[/math]（出于内积的对称性）。因此，第i行第j列的元素和第j行第i列的元素均为1，其他均为0。注意到，根据条件，[math]\displaystyle{ P_{i}\cdot P_{i}=1 }[/math]同时成立，因此[math]\displaystyle{ P\cdot P^{T}=1 }[/math]的矩阵具有以下形式：

[math]\displaystyle{ P\cdot P^{T}=\begin{matrix} \\ \\i\\ \\j\\ \end{matrix}\begin{pmatrix} 1 & \cdots &\cdots &\cdots &\cdots &\cdots \\ \cdots & \ddots & \cdots &\cdots &\cdots &\cdots \\ \cdots &\cdots &1 &\cdots &1 &\cdots\\ \cdots &\cdots &\cdots &\ddots &\cdots &\cdots \\ \cdots &\cdots &1 &\cdots &1&\cdots\\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots \end{pmatrix}, }[/math]

其中，除了对角线元素和i、j和j、i处的元素外，所有元素均为0。从公式 A37 中，我们知道第 i 行与第 j 行相同。因此，[math]\displaystyle{ P\cdot P^{T} }[/math]的最小特征值（也是P的最后一个奇异值）必须为0。如果有多个（比如N − r）(i, j)对且[math]\displaystyle{ i\neq j }[/math]满足[math]\displaystyle{ P_{i}\cdot P_{j}=1 }[/math]，那么最后N−r个奇异值全为零。P的秩为r。所以：

[math]\displaystyle{ \sigma_{r+1}=\sigma_{r+2}=...=\sigma_{N}=0 }[/math]

在这种情况下，[math]\displaystyle{ P\cdot P^{T} }[/math]可以被写作：

[math]\displaystyle{ P\cdot P^{T}=\begin{pmatrix} I_{(r-1)\times (r-1)},& \Omicron_{(r-1)\times (N-r+1)}\\ \Omicron_{(N-r+1)\times (r-1)}, & \mathbb{I}_{(N-r+1)\times (N-r+1)} \end{pmatrix}, }[/math]

其中[math]\displaystyle{ I_{(r-1)\times (r-1)} }[/math]是大小为(r − 1) × (r − 1)的单位矩阵，[math]\displaystyle{ \Omicron }[/math]和[math]\displaystyle{ \mathbb{I} }[/math]是所有元素分别均为0和1的矩阵。因此，P的奇异值按降序排列为：

[math]\displaystyle{ \sigma=(\sqrt{N-r+1},1,1,...,1,0,0,...,0) }[/math]

因此：

[math]\displaystyle{ \sigma_{1}\ge\sigma_{2}\ge...\ge\sigma_{r}\ge 1 }[/math]

情况2：如果[math]\displaystyle{ P_{i}\cdot P_{j}=1 }[/math] 仅在 i = j 时成立，则非零元素都位于[math]\displaystyle{ P\cdot P^{T} }[/math]的对角线上，因此[math]\displaystyle{ P\cdot P^{T}=I }[/math]。此时[math]\displaystyle{ P^{T}=P^{-1} }[/math]，且 P 必须是置换矩阵，并且所有奇异值都是1。这也符合引理2的陈述。 引理3：对于给定的TPM P ，任何[math]\displaystyle{ \alpha\in (0, 2) }[/math]的动态可逆性[math]\displaystyle{ \Gamma_{\alpha} }[/math]的度量小于或等于系统的大小 N 。

证明：因为[math]\displaystyle{ 0\le\alpha\le 2 }[/math]，所以[math]\displaystyle{ f(x)=x^{\alpha /2} }[/math]是凹函数，根据命题 4，我们有：

[math]\displaystyle{ \begin{align} \Gamma_{\alpha}=\sum_{i=1}^{N} \sigma_{i}^{\alpha}=N\cdot (\frac{\sum_{i=1}^{N} \sigma_{i}^{2}}{N})^{\alpha/2}=\nonumber\\ N^{1-\alpha/2} (\sum_{i=1}^{N} P_{i}^{2})^{\alpha/2}\le N^{1-\frac{\alpha}{2}+\frac{\alpha}{2}}=N \end{align} }[/math]

引理4：当且仅当任何i的Pi行向量相同时，非零TPM P的秩才能达到最小值1。在这种情况下：

[math]\displaystyle{ \Gamma_{\alpha}=|P_{1}|^{\alpha}\cdot N_{\alpha/2} }[/math]

证明：如果P的秩为1，则Pi的所有N-1个行向量，∀i∈[1, N]都可以用第一个行向量P1的线性函数来表示，因此

[math]\displaystyle{ Pi = k·P1 }[/math]

其中 k > 0。

但是，因为[math]\displaystyle{ |Pi|_{1} = 1 }[/math]，因此 k 必须为 1。因此：

[math]\displaystyle{ Pi = Pj,\forall i, j\in [1,N] }[/math]

另一方面，如果等式A51成立，则P的秩应该为1。在这种情况下，[math]\displaystyle{ P\cdot P^{T}=|P_{1}|^{2}\cdot \mathbb{I}_{N\times N}, }[/math]， (A52) 因此，[math]\displaystyle{ P\cdot P^{T} }[/math]的特征值为[math]\displaystyle{ (|P_{1}|\cdot \sqrt{N},0,...,0) }[/math]。这直接导致了公式A49。

引理5：对于任何[math]\displaystyle{ x_{i}\ge 0,\forall i \in [1,N] }[/math]且[math]\displaystyle{ \alpha\gt 0 }[/math],[math]\displaystyle{ f(\alpha)=(\sum_{i=1}^{N} x_{i}^{\alpha})^{1/\alpha} }[/math]是关于[math]\displaystyle{ \alpha }[/math]的单调递减函数。

证明：因为：

[math]\displaystyle{ \sum_{i=1}^{N}(x_{i}^{\alpha})^{2}\le (\sum_{i=1}^{N} x_{i}^{\alpha})^{2}, }[/math]

因此：

[math]\displaystyle{ log\frac{\sum_{i=1}^{N} x_{i}^{2\alpha}}{\sum_{i=1}^{N} x_{i}^{\alpha}}\le log\sum_{i=1}^{N} x_{i}^{\alpha}. }[/math]

更进一步，由于log是凹函数，因此：

[math]\displaystyle{ \sum_{i=1}^{N}(\frac{x_{i}^{\alpha}}{\sum_{j=1}^{N} x_{j}^{\alpha}})\cdot log x_{i}^{\alpha}\le log\sum_{i=1}^{N}(\frac{x_{i}^{\alpha}}{\sum_{j=1}^{N} x_{j}^{\alpha}}\cdot x_{i}^{\alpha}), }[/math] 因此，结合等式A56 和 A57，我们有： [math]\displaystyle{ \frac{\sum_{i=1}^{N} x_{i}^{\alpha}\cdot log x_{i}^{\alpha}}{\sum_{i=1}^{N} x_{i}^{\alpha}}\le log\sum_{i=1}^{N} x_{i}^{\alpha}. }[/math]