1 min read

社区发现

Sep 1, 2024

基本概念

现实生活中的图往往会长成这样：社区(community) 内部边相对稠密，而向外部的边比较稀疏。

使用 模块度(Modularity Q) 指标衡量不同社区划分的效果：

\begin{aligned} Q(G,S) &= \sum_{s \in S} [\#(\text{edges within group }s) - \#(\textbf{excepted }\text{edges within group }s)]\\ &= \dfrac{1}{2m} \sum_{s\in S} \sum_{i \in S} \sum_{j\in S} \left( A_{ij} - \dfrac{k_{i}k_{j}}{2m} \right) \\ &= \dfrac{1}{2m} \sum_{ij} \left( A_{ij} - \dfrac{k_{i}k_{j}}{2m} \right) \delta(c_{i},c_{j})\\ &\in [-1,1] \end{aligned}

$m$ 表示总边数，即 $m=\frac{1}{2}\sum_{ij}A_{ij}$ 。
$k_{i}$ 表示节点 $i$ 相邻边的权重和，即带权的度数。
$c_{i}$ 表示节点 $i$ 被分配到的社区， $\delta(\cdot,\cdot)$ 函数判断两个数是否相同；即节点 $i$ 和节点 $j$ 被分配到同一社区时 $\delta(c_{i},c_{j})$ 为 $1$ ，否则为 $0$ 。

我们界定模块度大于 0.3-0.7 中的一个阈值的社区为 有效社区结构(significant community structure)。

模块度增益(modularity gain) 的计算方法： $\Delta Q(D\to i\to C)=\Delta Q(D\to i) + \Delta Q(i\to C)$ 。

Louvain 算法的过程如下：

Phase 1: (Modularity is optimized by allowing only local changes to node-communities memberships)
- Step 1. 将每个节点单独划分为一个社区
- Step 2. 对于每个节点，计算将其放到另一社区的模块度增益，如果有 $>0$ 的就选择其中最大的放过去。
- Step 3. 一直循环第二步直到划分不发生变化。
Phase 2: (The identified communities are aggregated into super-nodes to build a new network)
- 将划分到一个社区的点合并成一个 super-node，从而得到一个新的网络。

这样一个完整的过程称为一个 PASS，有必要的话可以执行多个 PASS。