7,129
个编辑
更改
→计算网络的模块化程度Q-Modularity
Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。
Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。
Q的具体计算公式如下：
Q的具体计算公式如下：
[[File:community_figure_2.png|500px]]
:<math>Q=\sum_{ij}{\left [ {\frac{A_{ij}}{2m}-\frac{k_{i}*k_{j}}{(2m)(2m)}}\right ]}\delta (c_{i},c_{j})=\sum_{i=1}^{c}(e_{ii}-a_{i}^{2})</math>
:<math>e_{ii} = \sum_{j}{\frac{A_{ij}}{2m}\delta (c_{i},c{j})}</math>
:<math>a_{i}=\frac{k_{i}}{2m}=\sum_{j}{a_{ij}}</math>
其中<math>A</math>是网络G对应的邻接矩阵，如果从<math>i</math>到<math>j</math>存在边，则<math>A_{ij}=1</math>，否则为0。<math>m</math>是总连接数，<math>2m</math>是总度数，<math>\frac{A_{ij}}{2m}</math>是两节点之间连接的实际概率。<math>k_{i}</math>和<math>k_{j}</math>分别是<math>i</math>和<math>j</math>的度数。如果我们保持一个网络的度分布但对其连边进行随机洗牌，任意一对节点在洗牌后存在连接的概率为<math>\frac{k_{i}*k_{j}}{(2m)(2m)}</math>。上式中中括号表达的就是节点之间的实际连边概率高于期待值的程度。后面跟着一个二元函数，如果节点ij属于同一个社区，则为1，否则为0，这就保证了我们只考虑社区内部的连边。刚才这个定义是以节点为分析单位。实际上，如果以社区为分析单位看Q指标，可以进一步将其化简为<math>e_{ii}</math>和<math>a_{i}</math>之间的差。其中<math>e_{ii}</math>是在第<math>i</math>个社区内部的link占网络总link的比例，<math>a_{i}</math>是第<math>i</math>个社区和所有其他社区的社区间link数。
上式已经清楚定义了<math>Q</math>，但在实际计算里，上式要求对社区及其内部节点进行遍历，这个计算复杂度是很大的。Newman(2006)对上式进行了化简，得到矩阵表达如下：
我们定义<math>S_{ir}</math>为<math>n*r</math>的矩阵，<math>n</math>是节点数，<math>r</math>是社区数。如果节点<math>i</math>属于社区<math>r</math>，则为1，否则为0。则有
:<math>\delta (c_{i},c_{j})=\sum {S_{ir}S_{jr}}</math>
于是有
于是有
[[File:community_figure_4.png|400px]]
:<math>Q=\frac{1}{2m}\sum_{ij}\sum_{r}{\left [ {A_{ij}-\frac{k_{i}*k_{j}}{2m}}\right ]}{S_{ir}S_{jr}}=\frac{1}{2m}T_{r}(S^TBS)</math>
其中<math>B</math>是modularity matrix，其元素为
:<math>B_{ij}={A_{ij}-\frac{k_{i}*k_{j}}{2m}}</math>
该矩阵的行列和都是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>
通过对社区的划分可能空间进行搜索，可以得到最大化Q值的社区划分。在这个过程会涉及数值优化的部分，例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman（2006），它通过不断合并社区来观察Q的增加趋势，得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) )，在最好的情况下接近线性复杂度的算法。
通过对社区的划分可能空间进行搜索，可以得到最大化Q值的社区划分。在这个过程会涉及数值优化的部分，例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman（2006），它通过不断合并社区来观察Q的增加趋势，得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) )，在最好的情况下接近线性复杂度的算法。
<br>
===计算网络的连边紧密度Edge betweenness===
===计算网络的连边紧密度Edge betweenness===