7,129
个编辑
更改
→拓扑分析
==拓扑分析==
==拓扑分析==
===计算网络的模块化程度Q-Modularity ===
===计算网络的模块化程度 Q-Modularity ===
Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。
Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。
该矩阵的行列和都是0，因为实际网络和随机洗牌后的网络度分布是不变的。特别地，在仅仅有两个社区的情况下（<math>r=2</math>），可以<math>S</math>定义为一个<math>n</math>长的向量，节点属于一个社区为1，属于另一个社区为-1，Q可以写成一个更简单的形式：
该矩阵的行列和都是0，因为实际网络和随机洗牌后的网络度分布是不变的。特别地，在仅仅有两个社区的情况下（<math>r=2</math>），可以<math>S</math>定义为一个<math>n</math>长的向量，节点属于一个社区为1，属于另一个社区为-1，Q可以写成一个更简单的形式：
<math>Q = \frac{1}{2m}\sum_{ij}{B_{ij}S_{i}S{j}}=\frac{1}{2m}S^{T}BS</math>
:<math>Q = \frac{1}{2m}\sum_{ij}{B_{ij}S_{i}S{j}}=\frac{1}{2m}S^{T}BS</math>
通过对社区的划分可能空间进行搜索，可以得到最大化<math>Q</math>值的社区划分。在这个过程会涉及数值优化的部分，例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman（2006），它通过不断合并社区来观察Q的增加趋势，得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) )，在最好的情况下接近线性复杂度的算法。
<br>
<br>
===计算网络的连边紧密度Edge betweenness===
===计算网络的连边紧密度 Edge betweenness===
这个思路出现得比较早(Newman, 2001)。Freeman (1975) 提出过一个叫betweenness的指标，它衡量的是网络里一个节点占据其他n-1节点间捷径的程度。具体而言，首先对每一对节点寻找最短路径，得到一个<math>n * (n-1)/2</math>的最短路径集合S，然后看这个集合中有多少最短路径需要通过某个具体的节点。Newman借鉴了这个标准，但不是用来分析节点而是分析连边。一个连边的edge betweenness就是S集合里的最短路径包含该连边的个数。
定义了连边的betweenness后，就可以通过迭代算法来进行社区划分了。具体做法是先计算所有连边的betweenness，然后去除最高值连边，再重新计算，再去除最高值连边，如此反复，直到网络中的所有连边都被移除。在这个过程中网络就逐渐被切成一个个越来越小的component。在这个过程中，我们同样可以用Q-modularity来衡量社区划分的结果。这种算法定义比较清晰，也不涉及矩阵数学等运算，但问题是计算复杂度比较大。
===计算网络拉普拉斯矩阵的特征向量 Leading eigenvector===
一个有n个节点的网络G可以被表达为一个<math>n\times n</math>的[[邻接矩阵]]<math>A</math>。在这个矩阵上，如果节点i和j之间存在连边，则<math>A_{ij}=1</math>，否则为0。当网络是无向的时候，<math>A_{ij}=A_{ji}</math>。另外我们可以构造<math>n\times n</math>的度矩阵（degree matrix）<math>D</math>。<math>D</math>对角线上的元素即节点度数，例如<math>D_{ii}</math>为节点i的度数，所有非对角线的元素都是0。无向网的分析不存在度数的选择问题，有向网则要根据分析目标考虑使用出度还是入度。将度数矩阵减去邻接矩阵即得到拉普拉斯矩阵，即<math>L=D-A</math>。
L的特征根<math>\lambda_0 <= \lambda_1 <= ...<= \lambda_{n-1} </math>存在一些有趣性质。首先，最小的特征根总等于0。因为如果将<math>L</math>乘以一个有n个元素的单位向量，相当于计算每一行的和，刚好是节点的度的自我抵消，结果等于0。其次，特征根中0 的个数即无向网G中分量的个数。这意味着如果除了最小特征根，没有别的特征根为0，则整个网络构成一个整体。
在这些特征根里，第二小的特征根（或者最小的非零特征根）<math>\lambda_1 </math>又叫做代数连通性（algebraic connectivity），其对应的特征向量叫做Fidler vector。当<math>\lambda_1 >0</math>，说明网络是一个整体。<math>\lambda_1 </math>越大，说明网络彼此间的链接越紧密。从这个定义来看，非常像前面讨论的Q-Modularity，实际上在Newman2006的文章里，确实讨论了二者在数学上的对应关系。例如对示例网络所对应的进行分析，可以得到拉普拉斯矩阵如下：
在这些特征根里，第二小的特征根（或者最小的非零特征根）<math>\lambda_1 </math>又叫做代数连通性 algebraic connectivity，其对应的特征向量叫做'''费德勒向量 Fidler vector'''。当<math>\lambda_1 >0</math>，说明网络是一个整体。<math>\lambda_1 </math>越大，说明网络彼此间的链接越紧密。从这个定义来看，非常像前面讨论的Q-Modularity，实际上在Newman2006的文章里，确实讨论了二者在数学上的对应关系。例如对示例网络所对应的进行分析，可以得到拉普拉斯矩阵如下：
[[File:community_figure_7.png|500px]]
[[File:community_figure_7.png|500px]]
这个矩阵的特征根如下：{5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0}。取<math>\lambda_1 =1</math>时， Fidler vector={0.29, 0.00, 0.29, 0.29, 0.29, -0.58, -0.58, 0.00}。因为Fidler vector的值分别对应着图里的节点，于是可以写成{a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00}。仅仅从元素的正负号就可以看出，该分析建议我们把f和g节点与其他节点分开，更细致的，对元素值大小的考察则建议把矩阵分成三个社区，{{a, c, d, e}, {b, h}, {e, f}}。回到图中考察，我们发现这个社区分类基本是合理的。
这个矩阵的特征根如下：{5.5, 4.5, 4.0, 3.4, 2.2, 1.3, 1.0, 0}。取<math>\lambda_1 =1</math>时， Fidler vector={0.29, 0.00, 0.29, 0.29, 0.29, -0.58, -0.58, 0.00}。因为Fidler vector的值分别对应着图里的节点，于是可以写成{a:0.29, b: 0.00, c:0.29, d:0.29, e:0.29, f:-0.58, g:-0.58, h:0.00}。仅仅从元素的正负号就可以看出，该分析建议我们把f和g节点与其他节点分开，更细致的，对元素值大小的考察则建议把矩阵分成三个社区，{{a, c, d, e}, {b, h}, {e, f}}。回到图中考察，我们发现这个社区分类基本是合理的。
===通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值===
===通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值===
因为以上两种方法都是基于Q-modularity的，只不过是搜索策略的不同，所以在此不展开讨论。
因为以上两种方法都是基于Q-modularity的，只不过是搜索策略的不同，所以在此不展开讨论。
<br>
==流分析==
==流分析==