38、复杂网络社区结构检测方法解析

复杂网络社区结构检测方法解析

1. 局部合并算法

在网络社区结构检测中，有一种基于局部信息的合并算法。在该算法里，集合 $C_{m’‘’}$ 内部边的比例 $p_{m’‘’m’‘’}$ 等于集合 $C_{m’}$ 和 $C_{m’‘}$ 内部边的比例之和，再加上连接 $C_{m’}$ 与 $C_{m’‘}$ 中节点的边的比例。同时，连接到集合 $C_{m’‘’}$ 中节点的边的比例 $a_{m’‘’}$ 等于 $a_{m’}$ 与 $a_{m’‘}$ 之和，最终可得到公式 (9.20)。

算法的具体操作流程如下：
1. 找出使 $Q$ 值最大的两个集合 $C_{m’}$ 和 $C_{m’‘}$ 并将它们合并。
2. 相应地更新矩阵 ${p_{mm’}}$。具体做法是，将对应 $C_{m’}$ 的行（列）替换为对应 $C_{m’}$ 和 $C_{m’‘}$ 的行（列）之和，然后删除对应 $C_{m’‘}$ 的行（列）。
3. 重复上述步骤，使用新的矩阵 ${p_{mm’}}$ 继续合并，直到所有节点合并为一个集合，从而得到一个树状图。
4. 从生成的分区中选择模块化值最大的分区。

由于图中最多有 $K$ 对由至少一条边连接的集合（$K$ 为图中的边数），每次迭代最多需要计算 $K$ 种不同合并的 $Q$ 值。并且，不相连的两个集合合并不会增加模块化值，因此无需检查此类合并。此外，合并两个集合最多需要 $2N$ 次操作。在最坏情况下，该算法所需的总步骤数与 $(K + N×N)$ 成正比。虽然该算法原理简单，但高效实现需要专门的数据结构和巧妙的程序来更新矩阵 $E$ 并评估 $Q$ 的最大值。

以 Zachary’s 空手道