背景

在很久之前写过的一篇博客 社团检测度量指标 中，简单介绍了社区检测结果的各种评价指标及其计算方法。其中常用的评价指标是 模块度 Q 和 重叠模块度 EQ，为了解答部分读者的疑惑，本文附带 Python 代码来更加详细地说明这两种指标计算方式。

理论计算

由于之前的博客中已经说明，因此本文直接摘抄过来。

模块度 Q

非重叠模块度的主要介绍可以参考 Wiki 上 Modularity networks，以下写出主要的理解。

设AA 为网络的邻接矩阵，cv,cwc_v,c_w 分别为点v,wv,w 所在的两个社团，社团内部的边数和网络中总边数的比例为：

∑vwAvwδ(cv,cw)∑vwAvw=12m∑vwδ(cv,cw)\frac{\sum_{vw}A_{vw}\delta(c_v,c_w)}{\sum_{vw}A_{vw}}=\frac{1}{2m}\sum_{vw}\delta(c_v,c_w)

函数δ\delta 为克罗内克函数，mm 为网络中的总边数。

模块度的大小定义如下：社团内部的总边数和网络中的总边数的比例减去一个期望值，该期望值是将网络设定为随机网络时同样的社团分配所形成的社团内部的总边数和网络中总边数的比例的大小，模块度计算公式定义如下：

Q=12m∑vw[Avw−kvkw2m]δ(cv,cw)Q=\frac{1}{2m}\sum_{vw}[A_{vw}-\frac{k_vk_w}{2m}]\delta(c_v,c_w)

其中，kvk_v 表示节点vv 的度。设eije_{ij} 表示社团ii 和社团jj 内部边数目的和与总边数的比例，aia_i 表示社团ii 内部的点所关联的所有边的数目与总边数的比例，可以用一下公式来表示：

eij=12m∑vwAvwδ(cv,i)δ(cw,j)ai=12m∑vkvδ(cv,i)\begin{aligned} &e_{ij}=\frac{1}{2m}\sum_{vw}A_{vw}\delta(c_v,i)\delta(c_w,j)\\ &a_i=\frac{1}{2m}\sum_vk_v\delta(c_v,i) \end{aligned}

可以根据上述定义简化QQ 的计算，假设网络分为nn 个社团，QQ 的计算公式可以进一步推导：

Q=12m∑vw[Avw−kvkw2m]δ(cv,cw)=∑i[12m∑vwAvwδ(cv,i)δ(cw,i)−12m∑vkvδ(cv,i)12m∑wkwδ(cw,i)]=∑i(eii−ai2)\begin{aligned} Q&=\frac{1}{2m}\sum_{vw}[A_{vw}-\frac{k_vk_w}{2m}]\delta(c_v,c_w)\\ &=\sum_i[\frac{1}{2m}\sum_{vw}A_{vw}\delta(c_v,i)\delta(c_w,i)-\frac{1}{2m}\sum_vk_v\delta(c_v,i)\frac{1}{2m}\sum_wk_w\delta(c_w,i)]\\ &=\sum_i(e_{ii}-a_i^2) \end{aligned}

在进行每次划分的时候计算QQ 值，QQ 取值最大的时候则是此网络较理想的划分。QQ 值的范围在 0-1 之间，QQ 值越大说明网络划分的社区结构准确度越高，在实际的网络分析中，QQ 值的最高点一般出现在 0.3-0.7 之间。

重叠模块度 EQ

由模块度改进的指标 EQ 可用于度量重叠社团的划分结果，具体推导过程可以参考论文 Extending the definition of modularity to directed graphs with overlapping communities，以下给出具体的定义公式：

EQ=12m∑i∑u∈ci,v∈ci1QuQv[Auv−kukv2m]=12m(∑i∑u∈ci,v∈ciAuvQuQv−12m∑i∑u∈ci,v∈cikukvQuQv)\begin{aligned} EQ&=\frac{1}{2m}\sum_i\sum_{u\in c_i,v\in c_i}\frac{1}{Q_uQ_v}[A_{uv}-\frac{k_uk_v}{2m}]\\ &=\frac{1}{2m}(\sum_i\sum_{u\in c_i,v\in c_i}\frac{A_{uv}}{Q_uQ_v} - \frac{1}{2m}\sum_i\sum_{u\in c_i,v\in c_i}\frac{k_uk_v}{Q_uQ_v}) \end{aligned}

其中QuQ_u 表示节点uu 所属的社团，AA 为网络的邻接矩阵，kuk_u 为节点uu 的度，mm 表示网络中的总边数。为了直接在代码中理解直接将公式拆解为两项。

Python 实现

模块度 Q

非重叠模块度 Q 计算非常简单，代码参考如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def Modulartiy(A, coms, sums, vertices):
    Q = 0.0
    for eachc in coms:
        li = 0
        for eachp in coms[eachc]:
            for eachq in coms[eachc]:
                li += A[eachp][eachq]
        li /= 2
        di = 0
        for eachp in coms[eachc]:
            for eachq in range(vertices):
                di += A[eachp][eachq]
        Q = Q + (li - (di * di) / (sums * 4))
    Q = Q / float(sums)
    return Q

除此之外，还可以直接调用库接口 https://python-louvain.readthedocs.io 直接计算，本文不再赘述。

重叠模块度 EQ

重叠模块度 EQ 的 Python 实现如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def ExtendQ(A, coms, edge_num, node_k, node_coms_num):
    """ 重叠模块度 EQ

    Args:
        A (np.array): 邻接矩阵
        coms (dict): 社区划分结果
        edge_num (int): 边数量
        node_k (np.array): 每个节点对应的度 dim: (node_num, 2)
        node_coms_num (np.array): 每个节点所属社团数量 dim: (1, node_num)

    Returns:
        float: 重叠模块度值
    """
    factor = 2.0 * edge_num
    node_k = sorted(node_k, key=lambda x: x[0], reverse=False)
    first_item = 0.0
    second_item = 0.0
    EQ = 0.0
    for eachc in coms:
        for eachp in coms[eachc]:
            for eachq in coms[eachc]:
                first_item += A[eachp][eachq] / float(node_coms_num[eachp] * node_coms_num[eachq])
                second_item += node_k[eachp][1] * node_k[eachq][1] / float(node_coms_num[eachp] * node_coms_num[eachq])
    EQ = first_item - second_item / factor
    return EQ / factor

📢 为了便于理解代码中直接将EQEQ 计算公式拆成两项进行计算。

Contact