【笔记】

度相关、不相关网络的理解（不一定正确）

社交网络中，你刚注册，系统给你推荐了小明，你关注小明的概率和小明一点关系都没有，纯粹是你为了完成任务随便选了个人关注。因为你关注小明的概率随机，只是由你自己的关注总数（节点出度）决定，和对方的关注数和被关注数无关。这个网络就是度不相关网络。

你已经玩社交网络很久，系统根据你的兴趣给你推荐小明，你关注小明的概率和小明是不是大V有很大关系（假设大V发文内容有吸引力）。因为你关注大V的概率由你的关注总数，和大V的粉丝数共同决定。这个网络就是度相关网络。

同理，换成无向网络，就没有出度相关性和入度相关性的区分，统一称为度相关性。

同配、异配网络

研究表明，真实世界网络中节点之间的连接选择并不是均等的，而是存在明显的偏好．连接偏好导致网络中节点与节点之间的连接存在某种相关性，Newman根据复杂网络节点之间这种连接相关性，提出同配(assortativity)和异配(disassortativity)概念来区分节点之间的这种连接偏好，并利用匹配系数来量化节点之间的连接。

所以，复杂网络节点的异质性，是对节点分布均匀情况的一种度量。节点倾向于连接有相似度的节点，则构成同配网络；高度节点和低度节点也有一定概率连接，则构成异配网络。网络异配程度测量。

 

度的0阶、1阶、2阶分布特性

 













 学习来源：https://wenku.baidu.com/view/945731ffb7360b4c2f3f6486.html





 

以下为两个文献矛盾之处，二者有一个是错误的：因为k’和<k>在分子还是分母的位置明显反了。

来源1：复杂网络基础理论（正确）



来源2：复杂系统与复杂理论（错误）

 

 

 

文章目录
复杂网络
复杂网络基本概念
平均路径长度
聚类系数
度与度分布
网络拓扑基本模型及其性质
规则网络
全局耦合网络
最近邻耦合网络
星型耦合网络
随机图（ER随机图）
小世界网络模型
WS小世界模型
NW小世界模型
小世界网络的小波分析
无标度网络模型（重点）
基本性质
鲁棒性与脆弱性
适应度模型

复杂网络
复杂网络基本概念
平均路径长度
两个点$i$和$j$之间的距离$d_{ij}$定义为连接这两个节点的最短路径上的边数。
网络的平均路径长度$L$定义为任意两个节点之间的距离的平均值，即：

$L=\frac{1}{\frac{1}{2}N(N+1)}\sum_{i\ge j}{d_{ij}}$

其中，$N$为网络节点数。
一个含有$N$个节点和$M$条边的网络的平均路径长度可以用时间量级为$O(MN)$的广度优先搜索算法来确定。
网络的平均路径长度也称为网络的特征路径长度。
聚类系数
在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性称之为网络的聚类特性。
在网络中的节点$i$有$k_{i}$条边和其他节点连接,即有$k_{i}$个邻居节点。在这$k_{i}$个邻居节点之间最多可能有 $k_{i}(k_{i}-1)/2$条边，而这$k_{i}$个节点之间实际存在的边数$E_{i}$和总的可能的边数 $k_{i}(k_{i}-1)/2$之比就定义为节点$i$的聚类系数$C_{i}$，即：

$C_{i}=\frac{2E_{i}}{k_{i}(k_{i}-1)}$

简单描述即是：

$C_{i}=\frac{与点i相连的三角形的数量}{与点i相连的三元组的数量}$

三元组包含三角形，三元组两种形式为：

整个网络的聚类系数$C$就是所有结点i的聚类系数$C_{i}$的平均值。
度与度分布
度是单独节点的属性中简单而又重要的概念，分为出度和入度。直观上，一个节点的度越大，那么这个节点在某种意义下越重要。网络中的所有节点$i$的度$k_{i}$的平均值成为网络的(节点)平均度，记为$\langle k \rangle$，网络中节点的度的分布情况用分布函数$P(k)$来描述。$P(k)$表示一个随机选定的节点的度是$k$的概率。

规则图为Delta分布
随机网络和小世界网络为近似Poisson分布
指数分布（暂未知是哪种网络！）
无标度分布，即幂律分布

无标度分布即是分布函数$f(x)$满足无标度条件：

$f(ax)=bf(x)$

当满足这个条件是必定有：(这里假设     $f(1)f'(1)\neq 0$  )

$f(x) = f(1)x^{-r},        r = -\frac{f(1)}{f'(1)}$

证明见《复杂网络理论及其应用》中P12。
幂指数一般为$2\le r\le 3$，绝大多数节点的度相对很低，只有少量节点的度相对很高，因此这类网络为非均匀网络，那些度相对很高的节点成为网络的集线器（hubs）。
网络拓扑基本模型及其性质
规则网络
全局耦合网络
构成：任意两个点之间都直接相连接，如下图a所示
平均路径长度：1
最大聚类系数：1
最近邻耦合网络
构成：每个节点只和它周围的邻居节点相连，一般具有周期边界条件的最近邻耦合网络包含N个围成一个环的点，如下图b所示，每个节点与它最近的4个节点相连
K：最近邻的个数，图b中为4
N：节点的数目
聚类系数为：

$C_{nc}=\frac{3(K-2)}{4(K-1)}\approx \frac{3}{4}$

平均路径长度为：

$L_{nc} \approx \frac{N}{2K} \rightarrow \infty  \quad \quad （N  \rightarrow \infty ）$
星型耦合网络
构成：一个点为中心点，其他点与这个中心点直接连接，如下图c所示
聚类系数为：

$C_{star}=\frac{N-1}{N} \rightarrow 1  \quad \quad （N  \rightarrow \infty ）$

平均路径长度为：

$L_{star}=2- \frac{2(N-1)}{N(N-1)} \rightarrow 2  \quad \quad （N  \rightarrow \infty ）$


总体而言，这三种规则网络在很理想的情况下进行建模，很大程度上无法反映真实网络世界情况，是复杂网络研究中最基本的模型，不过有必要对他们的三要素进行理解与学习。
在人工构建的网络中，P2P为完全耦合网络，C/S为星型网络模型，路网在一定程度上可以认为是最近邻耦合模型（这个是自己想的）。
随机图（ER随机图）
构成：假设有大量的纽扣（$N \gg  1$）散落在地上，并以相同的概率$p$给每对纽扣系上一根线，这样便可以得到一个有$N$个点，约$pN(N-1)/2$条边的ER随机图实例。
性质存在的定义：如果当$N  \rightarrow \infty$时产生了一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随即图都具有性质Q。
ER随即图的许多性质都是突然涌现的。比如当概率$p$大于某个临界值$p_{c} \propto (lnN)/N$，那么几乎每一个图都是连通的。
平均度：$\langle k \rangle=p(N-1) \approx pN$
平均路径长度：$L_{ER} \propto lnN/ln\langle k \rangle$。在ER图中随机选择一个点，网络中大概有$\langle k \rangle^{L_{ER}}$个其他的点与该点之间的距离等于或者非常接近于$L_{ER}$，因此$N\propto \langle k \rangle^{L_{ER}}$，变换一下形式即得原式。这种平均路径长度为网络规模的对数增长函数的特性就是典型的小世界特征。
聚类系数：$C=p=\langle k \rangle/N\ll1$，这意味着大规模的稀疏ER随机图没有聚类特征。
ER图又称为“Poission随机图”，固定ER随机图的平均度$\langle k \rangle$不变，则对于充分大的N，由于每条边的出现与否都是独立的，ER随机图的度分布可以用Poission分布来表示，即：

$P(k)=C_{N}^{k}p^{k}(1-p)^{N-k} \approx \frac {{\lang k \rang}^k e^{- \lang k \rang}}{k!}$
小世界网络模型
考虑到规则的最近邻耦合网络具有高聚类特性，但是平均路径很大，不是小世界网络，而ER随机图有较小的平均路径长度，但是不具备高聚类特性。将这两者的性质结合，即可得小世界网络模型。
WS小世界模型
构造算法：从最近邻耦合网络这个规则网络开始，将它的边以概率$p$进行随机化重连，一个节点固定，另一个节点随机选择。并保证任意两个不同节点之间至多一条边，节点不能有边与自身相连。$p=0$到$p=1$的过程即是从完全规则网络到完全随机网络的过程。
聚类系数：

$C(p)=\frac{3(K-2)}{4(K-1)}(1-p)^3$

平均路径长度（目前暂无精确解析表达式，利用重正化群方法可以得到如下公式）：

$L(p)=\frac{2N}{K}f(NKp/2)$

其中$f(u)$为一普适标度函数，满足：

$f(u)= \left \{ \begin{aligned} 
constant，u \ll 1 \\
(lnu)/u，u \gg 1
\end{aligned} \right.$

后来，基于均场方法有如下表达式：

$f(x) \approx \frac{1}{2\sqrt{x^2+2x}}arctanh\sqrt{\frac{x}{x+2}}$

度分布：由于每个节点有$K$个邻居节点，在随机化重连的过程中，对于每个节点而言，有$K/2$条边是不会离开该节点的，因此，当$k<K/2$时，$P(k)=0$，当$k\geq K/2$时，分布如下：

KaTeX parse error: No such environment: equation* at position 8: 
\begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲
P(k)= \sum_{n=…

WS小世界模型构造方式中的随机化过程可能破坏网络的连通性，于是：
NW小世界模型
构造算法：从最近邻耦合网络这个规则网络开始，将它的边以概率$p$进行随机化加边。并保证任意两个不同节点之间至多一条边，节点不能有边与自身相连。$p=0$对应原始最近邻耦合网络，而$p=1$对应全局耦合网络。
聚类系数：

$C(p)=\frac{3(K-2)}{4(K-1)+4Kp(p+2)}$

平均路径长度（同WS小世界模型）：

$L(p)=\frac{2N}{K}f(NKp/2)$

其中$f(u)$为一普适标度函数，满足：

$f(u)= \left \{ \begin{aligned} 
constant，u \ll 1 \\
(lnu)/u，u \gg 1
\end{aligned} \right.$

后来，基于均场方法有如下表达式：

$f(x) \approx \frac{1}{2\sqrt{x^2+2x}}arctanh\sqrt{\frac{x}{x+2}}$

度分布：由于每个节点至少有$K$个邻居节点，因此，当$k<K$时，$P(k)=0$，当$k\geq K$时，分布如下：

KaTeX parse error: No such environment: equation* at position 8: 
\begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲
P(k)= C_{N}^{k…

当$p$足够小且$N$足够大时，NW小世界网络本质上等同于WS小世界网络。
小世界网络的小波分析
见《复杂网络理论及其应用》中P23。
大概就是利用小波变化，在一个粗化的状态下，观察网络的统计特性，进而研究在粗化状态下，$LL_{1}$低频区间所展现出来的网络特性，即网络的平均路径长度以及聚类系数。
无标度网络模型（重点）
基本性质
ER随机图和WS小世界模型的一个共同特征是度分布近似为Poisson分布，这样度基本上存在于平均度$\langle k \rangle$峰值附近，当$k\gg\langle k \rangle$时，度为$k$的节点几乎不存在。而许多现实生活中的网络，如Internet、WWW、新陈代谢网络等的连接度分布函数具有幂律形式，由于这类网络的节点的连接度没有明显的特征长度（比如平均度$\langle k \rangle$），因此，称之为无标度网络。
最初是的无标度网络模型：BA无标度网络，通过考虑现实情况下，网络的增长特性（每天都有新的节点和边加入）和优先连接特性（新的节点更加倾向于与那些高度节点相连接，“富者更富”“马太效应”）。该部分为我目前的研究重点。
**BA无标度网络构造算法：**从一个具有$m_{0}$个节点的网络开始，每次加入一个节点并连接到$m$个已存在的节点上，当然，必须满足$m \leq m_{0}$。在连接时，一个新的节点与一个已经存在的节点$i$之间的连接概率$\Pi_{i}$与节点$i$的度$k_{i}$和所有其他节点的度关系如下：

$\Pi_{i}=\frac{k_{i}}{\sum\limits_{j}{k_{j}}}$

平均路径长度：

$L \propto \frac{logN}{loglogN}$

$L$与$logN$一个量级，表明该网络具有小世界特性
聚类系数：

$C=\frac{m^2(m+1)^2}{4(m-1)}\big[ln\frac{m+1}{m}-\frac{1}{m+1}\big]\frac{[ln(t)]^2}{t}$

$m$：每次一个新的节点与$m$个已经存在的节点连接
$t$：经过$t$步，即总共加入$t$个节点，最后共有$N=t+m_{0}$个节点，大概$mt$条边
与ER随即图类似，当网络规模充分大时，BA无标度网络不具有明显的聚类特征
度分布：
对于无标度网络的度分布研究主要有三种方法：连续场理论，主方程法，速率方程法。
主方程法的结果：
定义$p(k,t_{i},t)$为在$t_{i}$时刻记录的节点$i$在$t$时刻的度恰好是$k$的概率。在BA模型中，当一个新节点加入到系统中来时，节点$i$的度增加$1$的概率为$m\Pi_{i}=\frac{k}{2t}$ （根据前文，可以推导出来），否则该节点的度保持不变。那么有：

$<Empty \space Math \space Block>$
$p(k,t_{i},t+1)=\frac{k-1}{2t}p(k-1,t_{i},t)+(1-\frac{k}{2t})p(k,t_{i},t)$
网络的度分布为：

$P(k)=\lim_{t\to +\infty}\big(\frac{1}{t}\sum\limits_{t_{i}}p(k,t_{i},t)\big)$

它满足如下递推方程式：

$P(k)= \left \{ \begin{aligned} 
\frac{k-1}{k+2}P(k-1)，k \geq m+1 \\
\frac{2}{m+2} \quad  \quad ，k =m \qquad 
\end{aligned} \right.$

从而可得BA网络的度分布函数为：

$P(k)=\frac{2m(m+1)}{k(k+1)(k+2)} \propto 2m^2k^{-3}$

$m$：每次一个新的节点与$m$个已经存在的节点连接
$k$：随机取一个节点，度为$k$的概率$P(k)$
表明：BA无标度网络的度分布函数可以由幂指数为3的幂律函数近似描述
缺陷：BA无标度网络的幂指数固定为3
鲁棒性与脆弱性
见《复杂网络理论及其应用》中P29。
无标度网络对随机故障策略，即随机移除一些点，有很高的鲁棒性；对蓄意攻击策略，即移除网络中部分度最高的节点，表现得非常脆弱。其中表现情况以整个图的连通性为标准。
鲁棒但又脆弱是复杂系统的最重要和最基本的特征之一。
Broder等人研究了更大规模WWW子网络的鲁棒性。他们发现只有删除所有度大于5的节点才能完全破坏WWW的连通性。这其实是因为WWW具有高度倾斜的度分布，度数大于5的节点在整个网络中所占的比例还是很小的。（这个发现以及相关的具体数值的研究，可能对我的研究有帮助）
适应度模型
BA模型只能生成度分布的幂律指数固定为3的无标度网络，而各种实际复杂网络的幂律指数则不甚相同，且大多属于2到3的范围内。
实际网络常常还具有一些非幂律特征，如指数截断，小变量饱和等。
在BA无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系（流式处理中，应该很有用）：

$k_{i}(t)=\big(\frac{t}{t_{i}}\big)^{\frac{1}{2}}$

$k_{i}(t)$：为第$i$个节点在时刻$t$的度
$t_{i}$：为第$i$个节点加入到网络中的时刻
则可以有一个很直观的认识：就是越老的节点具有越高的度，在完全随机的情况下，这一点基本成立。
适应度模型构造算法：在原有的BA模型上，为每个节点增加了一个适应度权值
从一个具有$m_{0}$个节点的网络开始，每次加入一个节点并连接到$m$个已存在的节点上，当然，必须满足$m \leq m_{0}$，每一个节点的适应度按照概率分布$ \rho ( \eta )$选取。在连接时，一个新的节点与一个已经存在的节点$i$之间的连接概率$\Pi_{i}$与节点$i$的度$k_{i}$以及适应度$\eta_{i}$和所有其他节点的度关系如下：

$\Pi_{i}=\frac{\eta_{i}k_{i}}{\sum\limits_{j}{\eta_{j}k_{j}}}$

中心度概念说明：
指标名称
概念
比较
实际应用
点度中心度
在某个点上，有多少条线
强调某点单独的价值
★作为基本点的描述
接近中心度
该点与网络中其他点距离之和的倒数，越大说明越在中心，越能够很快到达其他点
强调点在网络的价值，越大，越在中心
★★基本描述，用户价值
中间中心度
代表最短距离是否都经过该点，如果都经过说明这个点很重要，其中包括线的中心度
强调点在其他点之间调节能力，控制能力指数，中介调节效应
★★推荐算法，用户的控制力
特征向量中心度
根据相邻点的重要性来衡量该点的价值。首先计算邻接矩阵，然后计算邻接矩阵的特征向量。
强调点在网络的价值，并且比接近中心度厉害的是，点价值是根据近邻点来决定的
★★★推荐算法，用户潜在价值


R语言实现与验证：
library(igraph)
init.igraph<-function(data,dir=F,rem.multi=T)
             {
               labels<-union(unique(data[,1]),unique(data[,2]))
               ids<-1:length(labels);names(ids)<-labels
               from<-as.character(data[,1]);to<-as.character(data[,2])
               edges<-matrix(c(ids[from],ids[to]),nc=2)
               g<-graph.empty(directed = dir)
               g<-add.vertices(g,length(labels))
               V(g)$label=labels
               g<-add.edges(g,t(edges))
               if (rem.multi)
                 {
                   E(g)$weight<-count.multiple(g)
                   g<-simplify(g,remove.multiple = TRUE,
                   remove.loops = TRUE,edge.attr.comb = "mean")
                 }
               g
             }
#init.igraph参数说明：
#data,是两列关系数据，只能两列，而且要同等长度；
#dir，逻辑值，T代表有向图，F无向图；
#rem.multi，逻辑，T删除重复变量并更新线权重weight，F不删除并且线权重为1。

dat <- data.frame(node1 = c("A","A","A","B","B","C","E"),node2 = c("B","C","E","D","F","E","F"))
dat
  node1 node2
1     A     B
2     A     C
3     A     E
4     B     D
5     B     F
6     C     E
7     E     F

g <- init.igraph(dat,dir=F,rem.multi=T)
g
IGRAPH U--- 6 7 --
+ attr: label (v/c)
+ edges:
[1] 1--2 1--3 1--4 2--5 2--6 3--4 4--6
#看着跟原数据对不上，其实是函数根据数据出现顺序对其进行了重编码，A-1，B-2，C-3，E-4，D-5，F-6

#点度中心度——点出度、点入度、相对点中心度、点度频率
degree(g,mode="total")     #mode=in点入度；out=点出度；total点度中心度，三者统称绝对点中心度
[1] 3 3 2 3 1 2
#结果对应的是ABCEDF的度数
degree(g,normalized = T)   #相对点中心度=绝对点中心度/最大度数
[1] 0.6 0.6 0.4 0.6 0.2 0.4
#但根据洒家多次试验，实际除以的数是(结点总数-1)，在这里即5
degree.distribution(g)  #点度频率每种点度数的个数/所有点个数（比如（1,2,4,4）点度数分别为1,1,0,2，密度是1/4，1/4,0/4,2/4）
[1] 0.0000000 0.1666667 0.3333333 0.5000000
#分别对应度数为0,1,2,3的点个数/结点总数，在此为(0,1,2,3)/6

#接近中心度
#该点与网络中其他点距离之和的倒数，越大说明越在中心，越能够很快到达其他点。与点度中心度不同的是，点度更强调某点的相对价值；而接近中心度是某点在网络的价值。
closeness(g,mode="in")  #mode="out"是有向图，默认是无向图为in，设置normalized = T为相对接近中心度
[1] 0.14285714 0.14285714 0.11111111 0.12500000 0.09090909 0.12500000
#结果对应的是ABCEDF的接近中心度
closeness(g,vids=which(V(g)$label=="E")) #仅输出指定结点E的接近中心度
[1] 0.125

#中间中心度——点的中心度以及线的中心度
#点的中心度，代表最短距离是否都经过该点，如果都经过说明这个点很重要。也是强调点与网络的价值，而且更能说明转发、中介的情况
betweenness(g,normalized = T)  #点的中心度：normalized = T代表相对数，默认值为F为绝对值，mode有Out和in分别代表有向和无向
[1] 0.30 0.45 0.00 0.15 0.00 0.10
edge.betweenness(g)            #线的中间中心度
[1] 5.5 3.0 2.5 5.0 3.5 2.0 3.5

#点的特征向量中心度——evcent
#如果某人四周都是大牛人，那么这个人也很牛逼，这个方法是根据相邻点的重要性来衡量该点的价值。首先计算邻接矩阵，然后计算邻接矩阵的特征向量
evcent(g,scale = F)$vector     ##scale=F没有归一化，T代表输出数据进行标准化，mode有Out和in分别代表有向和无向
[1] 0.5162516 0.4075861 0.4010975 0.5023290 0.1604996 0.3583071
#page.rank特征向量中心度，这个是谷歌开发的，对于一些搜索的竞价排名做的指标。原理跟特征向量中心度差不多
page.rank(g)$vector
[1] 0.20466978 0.21836231 0.14090543 0.20440819 0.08686932 0.14478497

#简单网络图形展示
plot(g,layout=layout.grid)


参考资源：

#SNA-社会关系网络 R语言实现专题（基础篇）（一） http://blog.csdn.net/sinat_26917383/article/details/51443846

#SNA-社会关系网络—igraph包（中心度、中心势）（二） http://blog.csdn.net/sinat_26917383/article/details/51443846

#SNA-社会关系网络—igraph包（社群划分、画图）（三） http://blog.csdn.net/sinat_26917383/article/details/51444536

　　对复杂网络进行社区划分，需要有一些评价指标，来评判算法对网络划分结果的好坏优劣。如果我们预先知道网络的真实划分结果，那么我们可以用NMI（归一化互信息）去衡量算法划分结果和真实结果的重合程度，这个会在以后的文章中具体介绍。大多数情况下，我们是不知道网络的真实划分的，尤其是对于大型网络来说更是如此，复杂网络的命名明确的说明了这种现实情况。但是我们依然有方法可以量化或评判我们的社区划分水平，也就是今天要介绍的模块度（Modularity）概念，也称Q值。 

　　从网上看到其他同学写的博客，首先对这方面介绍的不多，仅有的一些文章也是有好有坏，所以决定自己梳理一下，也是对其他人的分享。



资料

　　这次，先贴链接： 

　　wiki：https://en.wikipedia.org/wiki/Modularity_(networks) 一定要搜英文的，中文版的并没有什么信息量。 

　　原定义作者论文：Finding and evaluating community structure in networks  (1) 

　　　　　　　　　　Modularity and community structure in networks　(2) 

　　一篇认为介绍的比较好的文章：Community Detection – Modularity的概念 

　　建议是：看一下那篇博客，再看一下wiki，然后看一下原作者论文定义。 

　　当然，也可以只看我的文章~O(∩_∩)O哈哈~。 

　　之所以选择那篇博客是因为该作者从历史演进角度介绍了模块度概念的由来及变化，从方法论上来说，认识历史可以更好的认识现在，这几乎可以套用在对任何事物的认识上面。。。扯远了 

　　



定义

　　我这里大概以通俗的语言翻译一下，严格的定义还是要看论文的， 

　　定义一： 

　　最早由Newman在文章(1)中给出的模块度的概念： 

　　 Consider a particular division of a network into k communities. Let us define a k ×k symmetric matrix e whose element eij is the fraction of all edges in the network that link vertices in community i to vertices in community j. 

　　 假设网络被划分为 $k$ 个社区，那么定义一个 $k \times k$ 的对称矩阵 $e$，它的元素 $e_{ij}$ 表示社区 $i$ 和社区 $j$ 之间的边的数量。 

　　 

　　The trace of this matrix $Tr e = \sum_{i}e_{ii}$ gives the fraction of edges in the network that connect vertices in the same community, and clearly a good division into communities should have a high value of this trace. 

　　矩阵的迹$Tr e = \sum_{i}e_{ii}$，也就表示了在相同社区内节点之间的边集合。显然，社区划分的好，也就是社区内部节点之间联系密集，那么该值就越高，这与我们通常对社区的认识是一致的。 

　　作者也指出，仅通过矩阵的迹这个值不能完全反应社区结构，因为如果把网络仅划分成1个社区的话，那么会导致$Tr e=1$。

　　So we further define the row (or column) sums $a_i = \sum_{j}e_{ij}$ , which represent the fraction of edges that connect to vertices in community $i$。 

　　因此又定义了一个值 $a_i = \sum_{j}e_{ij}$，表示所有连接到社区$i$的边数量。 

　　于是，作者定义了第一版模块度的概念： 

　　
 $$Q = \sum_{i}(e_{ii} - a_{i}^2) = Tr e - ||e^2||$$  

　　$||x||$ 表示矩阵 $x$ 的所有元素的和。 

　　简单展开一下上面的公式会更清晰： 

　　 $$Q = \sum_{i}(e_{ii} - a_{i}^2) = \sum_{i}e_{ii} - \sum_{i}a_{i}^2 = Tr e - ||e^2||   \qquad(1)$$ 


　　例如下面的网络，10个节点，12条边，被分成３个社区： 

　 

　　根据上述定义生成的社区矩阵为： 

　　 

　　模块度$Q = \frac{3+3+4}{12} - (\frac{7}{2 \times 12})^2 - (\frac{7}{2 \times 12})^2 - (\frac{10}{2 \times 12})^2 = 0.49$

　　定义二： 

　　再来看第二版定义： 

　　Newman在论文(2)中更新了模块度Q的定义，增加了矩阵的表达，感觉更不直观了。 

　　个人感觉从wiki里的定义理解更清楚一些，下面是一些定义及推导： 

　　Modularity is the fraction of the edges that fall within the given groups minus the expected such fraction if edges were distributed at random. 

　　模块度 = （落在同一组内的边的比例） 减 （对这些边进行随机分配所得到的概率期望） 

　　为了说明上述公式，对定义如下内容： 

　　假设网络有$n$个节点，有$m$条边，节点$v$的度表示为$k_v$。 

　　将网络的邻接矩阵表示为$A$，$A_{vw}=0$ 表示节点$v$和$w$之间没有边，$A_{vw}=1$ 表示有边。 

　　定义变量$s$，$s_{vw}=1$表示$v$和$w$属于同一社区，$s_{vw}=-1$表示不在同一社区，那么可以用$δ_{vw}=\frac{1}{2}(s_{vw}+1)$量化表示$v$和$w$是否在同一社区，如果是则等于1，不是则等于0. 

　　那么上述模块度定义就可以表示为： 

　　
 $$Q=\frac{1}{2}\frac{\sum_{vw}A_{vw}}{m}δ_{vw} - （对这些边进行随机分配所得到的概率期望）$$  

　　$\sum_{vw}A_{vw}δ_{vw}/m$ 表示在同一社区内的边的数量占所有边数量的比例， 乘以 $1/2$，是因为对每条边计算过两次。 

　　 

　　以上这部分计算很清楚，下面主要看那个期望值如何计算。 

　　这里面用到了Configuration Models，大体意思就是，对网络的边进行随机分配，需要将每条边切断一分为二，切断的点我们称作末梢点(stub)，这样$m$条边就会产生$l_{n}=2m=\sum_{v=1}^nk_{v}$个末梢点，随机的将这$l_n$个末梢点进行连接，包括同一节点拥有的末梢点的自连接。这样可以保持每个节点原有的度不变的条件下，可以得到一个完全随机网络。 

　　在该随机网络下，任意两点$v、w$连接边数的期望值是：$exp_{vw}=\frac{k_{v}k_{w}}{l_{n}}=\frac{k_{v}k_{w}}{2m}$ 

　　因此，节点$v$和$w$的实际边数与随机网络下边数期望之差为：$A_{vw}-\frac{k_vk_w}{2m}$ 

　　模块度最终可表示为： $$Q=\frac{1}{2m}\sum_{vw}(A_{vw} - \frac{k_{v}k_{w}}{2m}) δ_{vw} \qquad (2)$$  

　　定义 $e_{ij}$表示连接社区 $i$ 和 $j$ 的边的总数，$e_{ij}=\sum_{vw}\frac{A_{vw}}{2m}δ_{vi}δ_{wj}$，$a_i$表示连接   社区$i$的边的总数，$a_i=\sum_je_{ij}=\frac{k_i}{2m}$，那么模块度可以表示为： $$Q=\frac{1}{2m}\sum_{vw}A_{vw}δ_{vw}-\frac{1}{2m}\sum_{vw}\frac{k_{v}k_{w}}{2m}δ_{vw}=\sum_{i=1}^c(e_{ii}-a_{i}^2)$$  

　　 

　　可以看到，虽然初始含义不同，但经过推导，模块度的公式(1)和公式(2)具有一致的表现形式，而且最终的结果非常简单。 

　　应当注意，模块度的取值范围为：$[-1/2, 1)$，有可能得到负值。 

　　


代码实现

　　虽然推导过程非常复杂，但是最终形式非常简单，代码自然也清晰易懂。



#python2.7
#type(graph) = networkx.Graph
def Q(graph, cluster):
    e = 0.0
    a_2 = 0.0
    cluster_degree_table = {}
    for vtx, adj in graph.edge.iteritems():
        label = cluster[vtx]
        for neighbor in adj.keys():
            if label == cluster[neighbor]:
                e += 1
        if label not in cluster_degree_table:
            cluster_degree_table[label] =0
        cluster_degree_table[label] += len(adj)
    e /= 2 * graph.number_of_edges()

    for label, cnt in cluster_degree_table.iteritems():
        a = 0.5 * cnt / graph.number_of_edges()
        a_2 += a * a

    Q = e - a_2
    return Q