812
个编辑
更改
无编辑摘要
|}
|}
这两个矩阵的 EI 完全相同，因为它们的平均输出分布相同，各行转移分布的熵也相同。也就是说，从 EI 的角度看，它们具有相同的因果效应强度。但从奇异值谱看，<math>P_{\mathrm{lin}}</math> 只有两条独立的信息通路，而 <math>P_{\mathrm{cmp}}</math> 有三条独立的信息通路。因此，<math>\Gamma_0</math> 和 <math>\Gamma_1</math> 能区分这两种动力学结构，而 EI 无法区分。
这两个矩阵的 EI 完全相同，因为它们的平均输出分布相同，各行转移分布的熵也相同。也就是说，从 EI 的角度看，它们具有相同的因果效应强度。但从奇异值谱看，<math>P_{\mathrm{lin}}</math> 只有两条独立的信息通路，而 <math>P_{\mathrm{cmp}}</math> 有三条独立的信息通路。因此，<math>\Gamma_0</math> 和 <math>\Gamma_1</math> 能区分这两种动力学结构，而 EI 无法区分。这个例子说明，<math>\Gamma_{\alpha}</math> 的优势不在于替代 EI，而在于它能刻画 EI 不敏感的'''线性冗余'''：有些状态转移在概率分布上并不相同，却可能只是已有 information pathway 的线性混合。需要注意的是，<math>\Gamma_2</math> 在这个例子中相同，因为它更接近于衡量矩阵的确定性或能量大小；真正揭示通路冗余的是更偏向秩结构的 <math>\Gamma_0</math>，以及介于二者之间的 <math>\Gamma_1</math>。
=复杂网络中的粗粒化方法=
=复杂网络中的粗粒化方法=
复杂网络中的粗粒化方法非常多，常见思路包括：根据社团结构或模块结构合并节点，根据谱嵌入或扩散距离寻找动力学上相近的节点，根据网络模体或功能单元识别可重复的局部结构，也可以利用统计物理量、图神经网络等方法，在保留全局流量、扩散过程或拓扑功能的前提下压缩网络。不同方法关注的对象并不完全相同：有的主要保留拓扑结构，有的保留随机游走或扩散动力学，有的则保留功能模块和多尺度组织。
这些方法与马尔科夫链粗粒化有两层联系。首先，马尔科夫链本身可以看作一种加权有向复杂网络：状态对应节点，转移概率对应有向边权。因此，我们可以先把马尔科夫链的状态转移图视为一个网络，并使用一些有向图方法来生成候选划分。例如，社团检测会倾向于合并转移联系密集、概率流交换频繁的一组状态；谱聚类会根据大尺度连通结构或扩散结构合并状态；角色相似性方法则会把具有相似入流和出流模式的状态放在一起。如果暂时忽略方向、权重或具体转移概率，则可以把马尔科夫链退化为一个普通的无向拓扑网络。这样做会丢掉一部分动力学信息，但也能使用更广泛的复杂网络粗粒化工具，如无向社团检测、模块识别、网络模体识别和层次聚类等。此时得到的划分可作为候选分组，再根据成块性、稳态流、EI、动力学可逆性等指标进行选择。
其次，许多复杂网络上都可以定义随机游走、扩散或传播动力学。一旦规定游走规则，网络就会诱导出一个转移概率矩阵 <math>P</math>，也就是一条马尔科夫链。于是，复杂网络的粗粒化可以转化为马尔科夫链的状态粗粒化：我们不仅关心哪些节点拓扑上相近，也关心哪些节点在随机游走中具有相似的动力学作用。在这个意义上，成块性可以检验合并后的宏观节点是否仍然形成封闭马尔科夫链；稳态流矩阵可以刻画长期概率流通道；谱方法可以寻找扩散尺度上的相似节点；HOM 则可以在节点合并时保留随机游走的高阶路径依赖。因此，马尔科夫链粗粒化工具可以反过来用于复杂网络上的随机游走动力学压缩。
本节只简要介绍几类与马尔科夫链关系较近的复杂网络粗粒化方法，分别对网络上的随机游走动力学、扩散动力学，和多尺度功能模块进行粗粒化。虽然这些方法并不直接给出马尔科夫链的最优粗粒化，但可以为状态划分、网络归并和动力学保真提供有用的启发。
<br/>
<br/>
==复杂网络的粗粒化方法==
==复杂网络的粗粒化方法==
===谱粗粒化===
===复杂网络上的随机游走和谱粗粒化===
对一个复杂网络而言，网络本身只描述了节点间的静态关系，并不天然具备某种动力学，所以需要人为定义一套动力学。常见做法是借助随机游走子的概念，在网络上定义一套随机游走动力学。
假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。
考虑一个连通图 <math>G</math>，邻接矩阵为 <math>A</math>，假设图上有 <math>N</math> 个节点，分别为 <math>1,2,...,N</math>，我们定义从节点 <math>i\in\left\{1,2,...,N\right\}</math> 到节点 <math>j\in\left\{1,2,...,N\right\}</math> 的转移概率为 <math>w_{ij}=\frac{a_{ij}}{\sum_{j}a_{ij}}</math>（即对边权进行行归一化），其中 <math>a_{ij}</math> 表示邻接矩阵的第 <math>i</math> 行第 <math>j</math> 列元素，对应从节点 <math>i</math> 到节点 <math>j</math> 的边的权重。
由于该网络是连通图，所以分母 <math>\sum_{j}a_{ij}</math> 会大于<math>0</math>，而且满足行归一化，即 <math>\sum_{j=1}^N {w_{ij}}=1</math>。这样我们就定义了一个马尔科夫链，状态空间为 <math>\left\{1,2,...,N\right\}</math>，从状态 <math>i</math> 到状态 <math>j</math> 的转移概率为 <math>w_{ij}</math>，转移矩阵为 <math>W=\left\{w_{ij}\right\}_{N \times N}</math>（详情请见[[复杂网络中的因果涌现]]词条）。
为了对网络的随机游走矩阵 <math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math> 进行降维与简化，研究者提出了一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。这里采用的是'''列归一化写法'''：每一列的和为 1，因此指标 <math>j</math> 表示出发节点，<math>i</math> 表示到达节点。该方法的核心在于选取随机矩阵前 <math>S</math> 个最大非平凡特征值 <math>\lambda^2, \lambda^3, \ldots, \lambda^{S+1}</math> 对应的左特征向量 <math>\langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} |</math>，将网络节点映射到这些特征向量张成的特征空间。在此基础上，将每个特征向量的值域划分为 <math>I</math> 个区间，在所有 <math>S</math> 个特征向量上都落入相同区间的节点会被合并为一个超级节点。
从概率角度看，这一粗粒化过程可以理解为：新超级节点的出边概率由原节点的出边概率加权平均得到，其流入概率则由原节点的流入概率直接相加，其他未合并节点的转移概率保持不变。
<br/>
<br/>