3,094
个编辑
更改
→粗粒化复杂网络
在Klein等人的论文<ref name=":0"/>，以及Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，作者们主要提出了三种粗粒化网络的方法，包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则采用了相同的处理手段。
在Klein等人的论文<ref name=":0"/>，以及Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，作者们主要提出了三种粗粒化网络的方法，包括：[[贪婪算法]]、[[谱分解方法]]以及[[梯度下降]]方法。这三种方法最大的不同就在于节点分组方案的不同，至于如何归并节点和网络则采用了相同的处理手段。
Klein等人<ref name=":0" />利用贪婪算法对节点进行分组，这种方法对于大规模网络其效率很低。而Griebenow<ref name=":Griebenow"/>又提出了一种基于谱分解的方法来对原始网络节点进行分组，并将这种方法应用于[[偏好依附网络]]。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。
Klein等人<ref name=":0" />相当于使用贪婪算法对节点进行分组，但实质上该方法将分组和归并合并在一起执行了。这种方法对于大规模网络其效率很低。而Griebenow<ref name=":Griebenow"/>又提出了一种基于谱分解的方法来对原始网络节点进行分组，并将这种方法应用于[[偏好依附网络]]。相较于贪婪算法以及梯度下降算法，谱分解算法的计算时间更少，同时找到的宏观网络也更好（EI更大）。
所有这些粗粒化方法都使用了同样的节点与连边的归并方法。这就是高阶依赖项建模（[[HOMs]]），其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性<ref>Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。下面我们分别详细介绍这些粗粒化方法：
所有这些粗粒化方法都使用了同样的节点与连边的归并方法。这就是高阶依赖项建模（[[HOMs]]），其目的是为了保证分组后的宏观网络与原始的微观网络具有相同的随机游走动力学特性<ref>Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。下面我们分别详细介绍这些粗粒化方法：
时间复杂度：<math>O(N^4)</math>
时间复杂度：<math>O(N^4)</math>
'''缺点'''：
# 时间复杂度比较高，不适合对规模大的网络进行粗粒化
# 时间复杂度比较高，不适合对规模大的网络进行粗粒化
=====谱分解方法=====
=====谱分解方法=====
'''输入'''：原始包含[math]N[/math]个节点的网络[math]G[/math]，及对应的邻接矩阵<math>A</math>和距离超参<math>\epsilon</math>；'''输出'''：粗粒化后的宏观网络[math]G'[/math]，及对应的邻接矩阵<math>B</math>，以及从[math]A[/math]到[math]B[/math]的粗粒化方式
# 针对邻接矩阵<math>A</math>，得到其[[转移矩阵]]<math>W</math>，然后进行矩阵的[[特征值分解]]，得到特征值集合<math>Λ=\{λ_i\}^N_{i=1}</math>与特征向量集合<math>E=\{e_i\}^N_{i=1}</math>，通过去除特征值为0的特征向量并且通过特征值对对应的特征向量进行加权，构建新的有偏的特征向量集合<math>E’=\{λ_ie_i|λ_i≠0\}^N_{i=1}</math>（新的网络节点数量为<math>N'=rank(A)</math>）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应网络中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
# 针对邻接矩阵<math>A</math>，得到其[[转移矩阵]]<math>W</math>，然后进行矩阵的[[特征值分解]]，得到特征值集合<math>\Lambda=\{\lambda_i\}^N_{i=1}</math>与特征向量集合<math>E=\{e_i\}^N_{i=1}</math>，通过去除特征值为0的特征向量并且通过特征值对对应的特征向量进行加权，构建新的有偏的特征向量集合<math>E’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1}</math>（新的网络节点数量为<math>N'=rank(A)</math>）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应网络中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
# 依据<math>E'</math>计算节点间的距离矩阵<math>D_{N'×N'}</math>：
# 依据<math>E'</math>计算节点间的距离矩阵<math>D_{N'×N'}</math>：
## 如果节点<math>v_i</math>和<math>v_j</math>分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cos相似性作为两者间的距离<math>d_{ij}</math>和<math>d_{ji}</math>
## 如果节点<math>v_i</math>和<math>v_j</math>分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cos相似性作为两者间的距离<math>d_{ij}</math>和<math>d_{ji}</math>
时间复杂度：<math>O(N^3)</math>
时间复杂度：<math>O(N^3)</math>
'''缺点'''：
# 对规模大的网络进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
# 对规模大的网络进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
时间复杂度：<math>O(N^3)</math>
时间复杂度：<math>O(N^3)</math>
'''缺点'''：
# 初始化分组矩阵的选择，多次重复实验会得到不一样的结果
# 初始化分组矩阵的选择，多次重复实验会得到不一样的结果
# 依赖神经网络的超参，如学习率、迭代次数等
# 依赖神经网络的超参，如学习率、迭代次数等
====宏节点合并方法====
====节点合并方法====
通过上面的网络粗粒化方法可以对节点进行分组，为了构建粗粒化后的宏观网络，需要将微观节点合并成宏观节点，同时需要计算宏观网络之间的转移概率，为了保证分组后的宏观网络和原始网络具有相同的[[随机游走动力学]]，需要通过使用高阶节点显式地对高阶依赖项建模（[[HOMs]]）<ref>Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。
通过上面的网络粗粒化方法可以对节点进行分组，为了构建粗粒化后的宏观网络，需要将微观节点合并成宏观节点，同时需要计算宏观网络之间的转移概率，为了保证分组后的宏观网络和原始网络具有相同的[[随机游走动力学]]，需要通过使用高阶节点显式地对高阶依赖项建模（[[HOMs]]）<ref>Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>。