812
个编辑
更改
→复杂网络中的粗粒化方法
=复杂网络中的粗粒化方法=
=复杂网络中的粗粒化方法=
复杂网络与马尔科夫链之间存在密不可分的联系。许多复杂网络上的分析方法，比如随机游走等，会利用马尔科夫链动力学的理论。而马尔科夫链同样也会使用到复杂网络的理论分析方法，比如统计物理中的配分函数等。这部分简要介绍了复杂网络中的三种粗粒化方法，具有巨大的应用在马尔科夫链粗粒化问题上的研究潜力。
==复杂网络与马尔科夫链的相似性==
==复杂网络与马尔科夫链的相似性==
考虑一个连通图<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>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>。
，假设图上有$$N$$个节点，分别为$$1,2,...,N$$，我们定义从节点<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><ref>复杂网络的因果涌现.https://wiki.swarma.org/index.php/%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C%E4%B8%AD%E7%9A%84%E5%9B%A0%E6%9E%9C%E6%B6%8C%E7%8E%B0</ref>。
，假设图上有$$N$$个节点，分别为$$1,2,...,N$$，我们定义从节点<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><ref>复杂网络的因果涌现.https://wiki.swarma.org/index.php/%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C%E4%B8%AD%E7%9A%84%E5%9B%A0%E6%9E%9C%E6%B6%8C%E7%8E%B0</ref>。
<br/>
==复杂网络的粗粒化方法==
==复杂网络的粗粒化方法==
复杂网络可以被建模为一个马尔科夫过程，它的动力学由邻接矩阵<math>A</math>构建的随机矩阵$$W$$（或称转移概率矩阵）所描述，定义为<math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math>表示从节点<math>j</math>转移到节点<math>i</math>的概率。为实现网络的降维与简化，研究一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。该方法的核心在于选取随机矩阵前<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>个特征向量均落入相同区间的节点合并为一个超级节点。从概率角度可以对此粗粒化过程可以解释为，将新超级节点的出边概率为原节点的出边概率的加权平均，其流入概率为原节点的流入概率相加，其他没有合并节点的转移概率保持不变。
复杂网络可以被建模为一个马尔科夫过程，它的动力学由邻接矩阵<math>A</math>构建的随机矩阵$$W$$（或称转移概率矩阵）所描述，定义为<math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math>表示从节点<math>j</math>转移到节点<math>i</math>的概率。为实现网络的降维与简化，研究一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。该方法的核心在于选取随机矩阵前<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/>
===结合统计物理与机器学习的网络流方法===
===结合统计物理与机器学习的网络流方法===
进行稳态分析的时候，当<math>t\rightarrow \infty</math>时，<math>e^{-tL}</math>的极限与稳态分布有关，配分函数的渐近行为反映链的长期信息保留特性。通过分析<math>e^{-tL}</math>的特征向量来识别马尔科夫链的状态聚类。
进行稳态分析的时候，当<math>t\rightarrow \infty</math>时，<math>e^{-tL}</math>的极限与稳态分布有关，配分函数的渐近行为反映链的长期信息保留特性。通过分析<math>e^{-tL}</math>的特征向量来识别马尔科夫链的状态聚类。
<b/>
===具有自非相似性的复杂网络的粗粒化方法===
===具有自非相似性的复杂网络的粗粒化方法===