复杂网络社团检测GN与FN算法MATLAB实现

资 源 简 介

本项目详细实现了复杂网络分析领域中两个里程碑式的社团检测算法：Girvan-Newman (GN) 分裂算法和 Fast-Newman (FN) 凝聚算法。GN算法基于“边介数”（Edge Betweenness）的概念，核心思想是连接不同社团的边往往具有较高的介数，通过迭代计算并移除网络中介数最高的边，逐步剥离社团之间的连接，从而揭示网络的层次化结构，并利用模块度（Modularity, Q值）作为评价指标来确定最佳的划分层级。FN算法（也称为Newman贪婪算法）则采用自底向上的凝聚策略，初始化时将每个节点视为独立社团，在每一步迭代中选择能使整个网络模块度Q值增量最大（或减小最少）的一对社团进行合并，旨在在降低计算复杂度的同时寻找近似最优解，更适合处理中大规模网络。项目包含完整的MATLAB源码，实现了网络邻接矩阵的构建、基于广度优先搜索（BFS）的最短路径与边介数计算、模块度Q值的动态更新与监测、社团结构的划分与存储。此外，项目还集成了可视化功能，能够绘制Q值变化曲线，并将最终划分的社团结果以不同颜色映射到网络拓扑图中，直观展示节点的聚类情况。

详 情 说 明

复杂网络社团结构划分经典算法 (GN与FN) MATLAB实现

项目简介

本项目在MATLAB环境中完整复现了复杂网络分析领域中两个具有里程碑意义的社团检测算法：Girvan-Newman (GN) 分裂算法 和 Fast-Newman (FN) 凝聚算法。项目以经典的 Zachary 空手道俱乐部网络为数据集，深入展示了从网络构建、算法迭代、模块度（Modularity, Q值）计算到最终社团结构可视化的全过程。

该代码旨在通过对比“自顶向下的分裂”与“自底向上的凝聚”两种截然不同的策略，帮助用户理解网络社团结构的层次化特征及最优划分的评判标准。

主要功能特性

• 数据构建：内置 Zachary 空手道俱乐部网络数据生成逻辑，自动构建无向无权图的邻接矩阵。
• GN 分裂算法实现：

* 基于 Brandes 算法计算所有边的“边介数”（Edge Betweenness）。 * 实现迭代式边移除策略，逐步剥离社团间连接。 * 全程记录模块度 Q 值的变化历史，自动识别 Q 值最大的最优划分层级。

• FN 凝聚算法实现：

* 基于模块度增量（$Delta Q$）的贪婪优化策略。 * 采用矩阵坍缩技术（Matrix Collapsing）更新社区间的连接关系，通过合并邻接矩阵的行与列来模拟社团融合，提高计算效率。 * 构建社团归并树，自底向上寻找全局最优解。

• 核心评价指标：实现了标准的 Newman 模块度 Q 值计算函数，作为评估社团划分质量的唯一标准。
• 结果可视化：能够展示算法运行过程中的 Q 值变化曲线，并将最终的社团划分结果以颜色编码映射到网络拓扑图中。

系统要求

• 软件环境：MATLAB (推荐 R2016b 及以上版本，本项目仅使用基础工具箱，无需额外复杂网络工具箱)。

使用方法

1. 将所有源码保存至 MATLAB 当前工作路径。
2. 直接运行主程序（通常命名为 main）。
3. 程序将自动执行以下流程：

* 初始化网络数据。 * 运行 GN 算法并输出最大 Q 值、耗时及检测到的社团数。 * 运行 FN 算法并输出最大 Q 值、耗时及检测到的社团数。 * 弹出图形窗口，展示可视化结果。

核心算法逻辑与实现细节

本项目代码完全依据原始论文逻辑编写，具体实现细节如下：

1. 主控逻辑

主程序负责整体流程控制。它首先通过内部函数构建 Zachary 网络的邻接矩阵，随后分别调用 GN 和 FN 的封装函数。程序利用 tic / toc 记录算法运行时间，并提取算法返回的“最佳社团划分向量”与“Q值历史记录”，最后调用可视化模块进行展示。

2. Girvan-Newman (GN) 算法实现

该部分采用分裂策略，核心逻辑主要在于不断移除网络中“最繁忙”的边。

• 初始化：从原始网络开始，计算初始 Q 值。
• 迭代循环：只要网络中还存在边，就持续进行以下步骤：

1. 计算介数：调用辅助函数计算当前网络快照中每条边的介数。 2. 移除边：找到介数最大的边（若有多条则同时移除），将邻接矩阵对应位置置零。 3. 识别连通分量：利用 BFS/DFS 确定当前的社团划分情况。 4. 评估：计算当前划分的模块度 Q 值。 5. 记录：保存当前的迭代步数、Q 值以及对应的社团划分。

• 结果择优：遍历整个分裂过程的记录，通过比较 Q 值返回全局最优的社团结构。

3. Fast-Newman (FN) 算法实现

该部分采用凝聚（贪婪）策略，核心逻辑在于合并社团以最大化模块度增量。

• 初始化：将网络中每个节点视为一个独立的社团。构建社区级别的邻接矩阵（CommAdj）和度向量（CommK）。
• Delta Q 矩阵计算：利用简化公式计算合并任意两个当前存在的社团 $i$ 和 $j$ 所带来的模块度变化量 $Delta Q$。

* 公式逻辑考虑了社团间是否有直接连接以及随机连边的概率期望。

• 贪婪合并：在每一步迭代中，遍历所有活跃的社团对，找到能使 $Delta Q$ 最大（或下降最少）的一对社团进行合并。
• 矩阵更新（核心优化）：不重新计算整个网络的 Q 值，而是直接更新社区矩阵信息：

* 将被合并社团 $v$ 的行/列加到主社团 $u$ 上。 * 更新社团度数总和。 * 将社团 $v$ 标记为非活跃。

• 路径压缩：算法结束后，整理合并记录，将最终的节点归属映射为连续的社团编号（如 1, 2, 3...）。

4. 辅助计算模块

• 边介数计算 (calculate_edge_betweenness)

* 实现了无权图的 Brandes 算法。 * 对每个节点执行广度优先搜索 (BFS)，计算最短路径条数 ($sigma$) 和距离 ($d$)。 * 在回溯阶段（依赖度累积），根据经过某边的最短路径比例计算该边的介数贡献。 * 最终矩阵需除以 2（因为无向图对每条边计算了两次）。

• 模块度 Q 计算 (calculate_modularity)

* 严格遵循 Newman 的定义公式：$Q = frac{1}{2m} sum_{ij} (A_{ij} - frac{k_i k_j}{2m}) delta(c_i, c_j)$。 * 通过双重循环遍历节点对，仅当两个节点属于同一社团时累加其对 Q 值的贡献（实际边数减去随机期望边数）。

• 连通分量寻找 (find_connected_components)

* 使用基于队列的广度优先搜索 (BFS)。 * 遍历所有未访问节点，通过邻接关系扩散，标记属于同一连通区域的所有节点，赋予相同的社团 ID。

• 数据加载 (load_zachary_karate_club)

* 不依赖外部文件，直接以硬编码形式存储了 Zachary 空手道网络的 34 个节点和 78 条边的连接关系，返回标准的邻接矩阵。