简介：Fast-Newman社区检测算法的MATLAB实现压缩包，面向复杂网络研究的学生和工程技术人员。该算法由Newman提出，在经典模块度优化基础上提升计算效率，通过反复评估节点移动来提升划分质量，广泛用于社会网络、生物学网络和互联网结构分析。包内共2个文件：一个.m脚本负责读取网络数据、执行迭代社区划分并绘制聚类图；一个txt数据文件使用Zachary's Karate Club标准测试集（34个节点、78条边），由Zachary于1977年收集，是验证社区检测算法的经典案例。压缩包仅约1KB，下载运行都很轻量，已有1508人浏览学习，尤其适合刚接触社区划分的读者快速掌握Fast-Newman的思路与实现细节。运行脚本后可直接看到聚类结果及模块度变化，既能加深对模块度优化过程的理解，也可替换为自己的网络数据，用于更多真实场景的社区发现实验。

1. fast-Newman算法不是又一个聚类包：它解决的是大图上的社区发现

前阵子帮一个做社交关系分析的团队处理千万级边的关系网络，需求是把用户划分成若干兴趣社区。最开始他们用的是传统层次聚类，跑一次要一个通宵，而且内存直接被距离矩阵撑爆。后来换成基于模块度优化的 fast-Newman算法，同样的机器上几十秒出结果，社区质量还更符合业务直觉。你可能会觉得这是算法本身有什么黑魔法，其实它只是把“贪心合并”和“堆结构”这两件老工具组合起来，让社区发现从教科书里的实验室玩具变成了能上生产的东西。这篇文章我按自己落地的经验，把模块度是什么、fast-Newman为什么快、最小可复现代码、调参和翻车现场一次讲完。适合正在做社区发现、用户分群、图结构分析，或者被聚类性能卡住的开发者。

2. 先把模块度这条线捋直：fast-Newman在优化什么

2.1 模块度：社区划分的“心率”

社区发现这个问题，嘴上说“把联系紧密的点分到一起”很容易，难的是怎么量化“紧密”。fast-Newman算法的优化目标叫模块度 Q，它想表达的意思是：社区内部的边密度，比随机连接下的期望密度高多少。如果划分结果和随机图没有区别，Q 接近 0；如果社区结构明显，Q 通常落在 0.3 到 0.7 之间。

定义式为：

Q = (1 / (2m)) * Σ_ij [ A_ij - (k_i * k_j) / (2m) ] * δ(c_i, c_j)

其中 m 是总边数，A_ij 是邻接矩阵元素，k_i 是节点 i 的度，δ(c_i, c_j) 表示 i 和 j 是否在同一社区。这个式子里最关键的是(k_i * k_j) / (2m)，它代表“如果边是完全随机连的，i 和 j 之间应该有多少条边”。实际边数减去随机期望，就是社区划分带来的“超额连接”。

参数说明：

• 对于无权网络，A_ij 取 0 或 1；对于有权网络，A_ij 是边权重，k_i 也要换成加权度。
• m 在有权图里是所有边权和，不是边数。
• δ 函数是硬性条件，它让求和对“社区内节点对”生效，跨社区节点对的贡献为 0。

我一般不会直接去算这个全局 Q，因为计算成本高。实际代码里用的是它的增量形式：不重新算整张图，只算“如果合并两个社区，Q 变化多少”。这就是 fast-Newman 能快起来的第一个基础。

2.2 贪心合并与模块度增量

fast-Newman 的核心策略是自底向上的贪心合并。初始时每个节点独立成一个社区，然后反复找一对“合并后 Q 增量最大”的社区合并，直到任何合并都不能让 Q 再变大。

假设当前要合并社区 i 和 j，合并后的 Q 增量有经典化简结果：

ΔQ = e_ij + e_ji - 2 * a_i * a_j

其中e_ij是 i 和 j 之间边权占全图总边权的比例，a_i是社区 i 内所有节点的度之和占全图总边权比例。对于无权图，e_ij = e_ji，所以式子简化为：

ΔQ = 2 * (e_ij - a_i * a_j)

这个增量公式是整个算法的发动机。每轮合并只需要看这个值，最大的正增量就是贪心方向。

我经常被问一个问题：为什么不用全局 Q 每轮重算？因为全局 Q 每次迭代要扫全图，合并 N 轮就是 O(N * m)，在大图上根本跑不动。用增量公式后，每轮只需要更新和合并社区相关的局部信息，整体复杂度降到了接近 O(m log n)。

2.3 为什么堆能快这么多：复杂度和选型

增量公式算出来了，下一个问题是“每次找最大增量”怎么找最高效。朴素做法是每轮扫一遍所有社区对，复杂度 O(n^2)，在十万节点级别就会卡死。fast-Newman 的做法是把所有社区对的 ΔQ 维护在一个最大堆里，堆顶就是当前最优合并。

选型理由很简单：

• 堆的插入和删除都是 O(log n)，比每次全量扫描快一个数量级。
• 但社区合并后，矩阵并不会整个重建，只有被合并社区相关的行和列需要更新，所以堆里会留下大量“过期”元素。这就需要惰性删除配合，后面第 5 章会详细讲这个坑。
• 相比 Louvain 算法，fast-Newman 不需要多层迭代，实现和调参都更直白；相比 Girvan-Newman 的边介数割裂，fast-Newman 不需要反复计算介数，速度优势在这里就已经体现出来了。

如果你的图是几十万节点以内的中等规模，fast-Newman 是性价比最高的选择。再大的图，就要考虑在第 6 章里说的增量缓存技巧，或者转向流式处理方法了。

3. 本地跑通 fast-Newman 最小实现：从邻接表到社区标签

3.1 数据准备：三种常见输入格式

fast-Newman 的输入不是坐标点，而是图结构。最常见的是这三种：

1. 边列表：每行两个节点 ID，代表一条无向边。
2. 邻接表：每个节点一行，后面跟它的邻居列表。
3. 权重边列表：在边列表基础上多一列权重，比如关系次数、共现频次。

我一般会建议先把数据统一成边列表加权重，因为它是三种格式里最不容易出错的，也最容易做去重和自环检查。下面这个函数把边列表读进来，转成内部需要的社区数据结构：

def load_edge_list(file_path, weight=True): edges = [] max_node_id = -1 with open(file_path, 'r') as f: for line in f: parts = line.strip().split() if len(parts) < 2: continue u, v = int(parts[0]), int(parts[1]) w = float(parts[2]) if weight and len(parts) >= 3 else 1.0 edges.append((u, v, w)) max_node_id = max(max_node_id, u, v) return edges, max_node_id + 1

逻辑说明：

• 返回edges列表和节点总数，后续所有数组都按节点总数初始化，避免动态扩容。
• 权重缺省时统一置 1.0，保证有权无权代码路径一致。
• 这里故意不把边做成邻接矩阵，因为矩阵在十万节点以上就是灾难，邻接表才是正解。

参数说明：

• weight=True：读取第三列作为权重；如果输入文件只有两列，就退化为无权图。
• max_node_id用来算出实际节点数，注意如果节点 ID 从 1 开始，节点数应该是最大 ID 加 1，而不是行数。

3.2 核心实现：用最大堆维护增量矩阵

现在写最核心的合并逻辑。这里我用 Python 的heapq实现最大堆。Python 的heapq默认是最小堆，所以存-ΔQ来模拟最大堆。

import heapq class FastNewman: def __init__(self, n, edges): self.n = n # 初始化每个节点独立成社区 self.community_size = [1] * n self.total_weight = sum(w for _, _, w in edges) # 记录每个社区与其他社区的连接权重 self.connections = [dict() for _ in range(n)] self.degree = [0.0] * n for u, v, w in edges: self.connections[u][v] = self.connections[u].get(v, 0.0) + w self.connections[v][u] = self.connections[v].get(u, 0.0) + w self.degree[u] += w self.degree[v] += w # 堆元素：( -delta_q, 社区a, 社区b, 版本号 ) self.heap = [] self.version = [0] * n def _delta_q(self, i, j): # 用当前连接矩阵计算模块度增量 eij = self.connections[i].get(j, 0.0) / self.total_weight ai = self.degree[i] / self.total_weight aj = self.degree[j] / self.total_weight return 2.0 * (eij - ai * aj) def build_heap(self): for i in range(self.n): for j in self.connections[i]: if i < j: dq = self._delta_q(i, j) if dq > 0: heapq.heappush(self.heap, (-dq, i, j, self.version[i])) # 注意：version[j] 也应该参与判断，这里简化为至少有一个版本号一致时才使用

逻辑说明：

• connections[i]是一个字典，记录社区 i 到其他社区的边权和。初始时每个社区只有一个节点，所以它其实就是节点的邻居权重表。
• 堆里存四元组，第四项是 i 的版本号。版本号是前面提过的“惰性删除”关键，每次合并后相关社区版本号加一，旧堆元素就自动失效。
• if i < j避免重复插入同一对社区，因为无向图的连接权重是对称的。

参数说明：

• total_weight是全域权重和，增量公式里所有比例都除以它，所以它对结果影响是全局性的，不能算错。
• 堆里只装dq > 0的社区对，因为负增量合并只会降低 Q，留着只会拖慢速度。这个预剪枝能让堆体积从 O(n^2) 降到 O(m)。

然后实现合并操作：

def merge(self, i, j): # 合并社区 j 到 i，并更新相关增量 self.version[i] += 1 self.version[j] += 1 # 重新调整共享邻居的权重 for neigh, w in self.connections[j].items(): if neigh == i: continue old_w = self.connections[i].get(neigh, 0.0) self.connections[i][neigh] = old_w + w self.connections[neigh][i] = old_w + w self.degree[i] += self.degree[j] self.community_size[i] += self.community_size[j] # 清理 j 的连接信息，标记 j 已并入 i self.connections[j].clear() self.connections[i][j] = 0.0 self.connections[j][i] = 0.0 self.community_size[j] = 0 self._push_new_candidates(i) def _push_new_candidates(self, i): # 为新合并的社区生成候选堆元素 for neigh, w in self.connections[i].items(): if neigh == i or w == 0.0: continue dq = self._delta_q(i, neigh) if dq > 0: heapq.heappush(self.heap, (-dq, i, neigh, self.version[i]))

逻辑说明：合并的方向是单向的，j 并入 i，所以只需要更新 i 的连接关系，把 j 的邻居权重叠加到 i 上。这个过程中涉及 i 的邻居的度数不变，但邻居的社区归属感知变了，所以 i 需要重新生成一批候选堆元素。j 的版本号加一，堆里同时指向 j 的旧元素全部失效。

参数说明：

• connections[i][j] = 0.0是关键，不直接删除而是置零，避免后续_delta_q里get出非对称数据。
• community_size[j] = 0用于后续统计社区数量，值为 0 的社区视为已消亡。

最后是迭代主循环：

def run(self, verbose=True): self.build_heap() q = 0.0 merges = [] while self.heap: neg_dq, i, j, ver = heapq.heappop(self.heap) # 惰性删除：版本不一致或社区已消亡则跳过 if self.version[i] != ver or self.community_size[i] == 0 or self.community_size[j] == 0: continue if i == j: continue if self.connections[i].get(j, 0.0) == 0.0: continue dq = -neg_dq if dq <= 0: break q += dq merges.append((i, j, q)) self.merge(i, j) return merges, q

逻辑说明：run不断从堆顶取候选。取出来先做三件事：版本号是否匹配、两个社区是否还活着、两者之间是否还有实际连接。任何一项不满足，就丢弃这个堆元素，继续取下一个。只要堆顶的 ΔQ 是正的，就执行合并；一旦堆顶变成非正，说明再合并也不会提升 Q，直接终止。

参数说明：

• verbose在这里没有用到，真实项目中可以打开来打印每轮的社区数和 Q 值，帮助观察收敛趋势。
• merges记录每次合并后的累计 Q，后面画 Q 增长率曲线时需要这个列表。

3.3 输出与解读：社区标签、模块度、收敛判断

跑完后需要把社区标签映射回原始节点。因为社区 ID 在合并过程中会变化，所以要维护一个并查集或者后处理映射。常见做法是：

def assign_labels(merges, n): parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[rb] = ra for i, j, _ in merges: union(i, j) labels = {} for node in range(n): root = find(node) labels.setdefault(root, []).append(node) return labels

这个函数把合并轨迹里的节点归到同一个根社区下。注意这里不是重新跑聚类，只是把 fast-Newman 的历史合并结果“翻译”成每个节点最终归属。得到labels后，社区大小分布、平均内部度、模块度 Q 就都能直接算了。

收敛判断建议不要只看 merge 数量，要看merges列表里最后几段 Q 值是否还在显著上升。如果最后几次合并 Q 增长小于1e-6，说明已经收敛，再往下合并只是过拟合噪声。这个阈值我会把它当作参数暴露出去，不同网络差很多。

4. 参数怎么设：在真实网络里把 fast-Newman 调到靠谱

4.1 权重归一化：最容易被忽略的参数

fast-Newman 的 ΔQ 公式里，a_i是社区 i 的“全图度占比”。如果图里有几根极端大权重边，它们会垄断total_weight，导致大多数社区的a_i接近 0，合并变得非常“脆”。

我一般会先做一次权重检查：

import numpy as np def check_weight_distribution(edges): ws = np.array([w for _, _, w in edges]) print(f"max/min = {ws.max() / ws.min():.2f}") print(f"top1% 权重占比 = {np.sort(ws)[-int(len(ws)*0.01):].sum() / ws.sum():.2f}")

如果发现 top 1% 的边贡献了超过一半权重，那就需要做归一化。常见做法是：

• 线性缩放到 [0, 1]：w / max_w。
• 对数缩放：log(1 + w)，适用于长尾分布。
• 二值化：如果边权只是频次，直接卡阈值变成无权图，有时候效果反而更稳。

参数说明：

• 线性缩放适合权重本身有可比性的场景，比如共现次数。
• 对数缩放适合边权跨多个数量级，比如成交金额、通话时长。
• 二值化适合业务上只关心“有没有关系”的场景。

4.2 停止条件：不是合并到底才算完

fast-Newman 原生流程是合并到不能再合并为止，但实际业务里这样会得到太多碎片社区。原因：小社区之间的合并增量可能是正的，但对业务没有任何意义。所以在工程实现里我会显式设置一个“最小模块度增益”阈值。

def run_with_threshold(self, min_gain=1e-6): self.build_heap() q = 0.0 merges = [] while self.heap: neg_dq, i, j, ver = heapq.heappop(self.heap) if self.version[i] != ver or self.community_size[i] == 0: continue dq = -neg_dq if dq < min_gain: break q += dq merges.append((i, j, q)) self.merge(i, j) return merges, q

逻辑说明：和原始版唯一差别是把dq <= 0换成了dq < min_gain。当增益低于阈值时，不再贪心合并，直接停止。这个参数能有效控制社区数量。

参数说明：

• min_gain=1e-6适合边权归一化后的图。如果你用的是原始权重，这个阈值要放大到1e-3甚至1e-2，因为它本质是 Q 的绝对增量，和total_weight尺度绑定了。
• 想要更多社区，调大min_gain；想要更少但更大的社区，调小。
• 我通常会在生产任务里跑一次不设阈值的，得到 Q 增长曲线，然后在曲线“膝盖”处选阈值。

4.3 现成库和自实现的边界

很多图算法库都内置了 fast-Newman 或其变体。如果你只想快速验证结果，不需要自己实现，可以直接用现成接口。常见做法是在图对象上调用快速贪心社区发现函数，返回每个节点的社区归属。但要注意，库实现通常是优化过的，结果和我上面写的最小版可能有细微差异，原因在于更新策略和惰性删除的处理方式不同。

我的建议是：验证阶段用现成库，生产阶段用自实现。理由有三个：

1. 库实现是黑匣子，出了问题不好排查，比如出现异常社区时你不知道是输入数据的问题还是合并策略的问题。
2. 自实现的合并轨迹里带着 Q 值，可以精确画出每轮增益，这是调业务参数的依据。
3. 真实数据往往带权重、带自环、带多重边，库实现内部可能做了一些你不知道的预处理。

如果你决定用库实现，也要记得做两件事：确认输入是无向、有权图，且节点 ID 连续；确认返回的社区列表里没有孤立节点被漏掉。这些边界问题在自实现里是一目了然的。

5. 避坑：fast-Newman 常见翻车现场与排查

5.1 现象：合并结果出现环 1 → 2 → 1，社区标签反复横跳

第一次跑是最容易遇到的。记录的合并轨迹里出现“先把 2 并入 1，之后又把 1 并入 2”，最后社区根变成一个循环，并查集 find 陷入死循环。

原因：这是堆里陈旧元素没有被正确跳过导致的。合并 1 和 2 后，1 的版本号变了，但对面的旧堆元素还在堆里，如果取到了(2, 1)的旧记录，而我的代码只检查了version[i]，没检查version[j]，就会重复合并同一对。

解决：在run里取堆元素后，同时检查两个社区的版本号或存活状态。上面代码用self.community_size[j] == 0已经挡住了大部分情况，但最保险的是i == j和连接权重为 0 的检查一起上。我建议这三个判断缺一不可：

if self.version[i] != ver or self.community_size[i] == 0: continue if self.community_size[j] == 0 or i == j: continue if self.connections[i].get(j, 0.0) == 0.0: continue

5.2 现象：模块度 Q 越合并越低，曲线像心电图

明明每一步都是取正增量，为什么整体 Q 会上下波动？

原因：问题出在“堆顶元素是过期的”。堆顶的负值可能来自一个已经失效的社区对，它的实际 ΔQ 可能是负的，但因为没检查版本号就当成了最大增量。另一个原因是浮点误差累积，尤其当网络里存在非常接近零的边权时，2 * (eij - ai * aj)的差值可能被舍入成负数。

解决：把浮点比较改成带容差的比较。我一般用if dq < -1e-12: break，让比零略小的浮点噪声直接放行成停止条件。同时还应该在每次合并后用compute_q函数直接算一次全局 Q，校验累计 Q 是不是真的上升。

5.3 现象：孤立节点和连通分量变成一堆单点社区

输入图里有大量孤立节点，或图本身是多个不连通的分量。fast-Newman 初始把每个节点当社区，孤立节点没有任何正增量，所以它们永远不会被合并，最终留在标签里成为一堆大小为 1 的社区。

原因：算法本身没问题，是业务期望和算法行为不匹配。孤立节点本来就不属于任何社区，硬要分配反而是错的。

解决：跑算法之前先做连通分量分析，对每个连通分量单独跑 fast-Newman，最后合并结果。这样大分量和小分量都有自己的社区，不会互相干扰。代码上可以在run之前加一个步骤：

from collections import deque def connected_components(n, adjacency): visited = [False] * n comps = [] for start in range(n): if visited[start]: continue stack = [start] visited[start] = True comp = [] while stack: u = stack.pop() comp.append(u) for v in adjacency[u]: if not visited[v]: visited[v] = True stack.append(v) comps.append(comp) return comps

5.4 现象：有向图跑出的社区和业务认知完全相反

fast-Newman 的 ΔQ 公式默认图是无向的，e_ij = e_ji。如果直接拿有向边列表喂给算法，合并方向会在两个方向上各统计一次，社区内部度被翻倍，模块度计算失真。

原因：算法设计里没有方向的概念，把入边和出边混在一起了。
解决：有两种常见做法。第一种是把有向图转成无向图：只要存在 u→v 或 v→u，就生成一条无向边，权重取两方向之和。第二种是老老实实用有向模块度版本，但那需要改公式。绝大多数业务场景里“有关系”就够了，所以我一般先转无向，跑完再看社区间方向比例。

5.5 现象：权重很大时结果不稳定，两次运行社区数不同

按理说贪心算法是确定性的，但如果你用了并行初始化或者哈希遍历字典，社区对的处理顺序不同，可能导致合并路径不同。Python 的字典遍历顺序在插入顺序不变时是稳定的，但如果你用了多线程预处理权重，同一张图可能得到不同的connections顺序。

原因：合并顺序本来就不是唯一的，多个社区对拥有相同 ΔQ 最大值时选择谁，会影响后续合并路径。
解决：在合并前给所有社区对按(-ΔQ, i, j)排序，保证选择是确定的。具体做法是堆元素里不只存(-dq, i, j)，而是存(-dq, i, j)，Python 的元组比较会自动按第二项、第三项排序。这样相同增量时固定选 ID 小的先合并，结果可复现。

6. 进阶：用 Q 增长率曲线做自检，跑上更大图

最后一件事，我每次跑完 fast-Newman 都会画一条 Q 增长率曲线，而不是只看最终 Q。把merges里的累计 Q 值按轮次画出来，你会看到一条先快后慢的弧线。弧线的“膝盖”就是业务上最合理的社区数量：再往下合并，Q 还在涨，但涨得太慢，社区解释力下降。这个曲线也是和业务方沟通的最直观工具。

对于更大规模图，我常用的技巧是“合并日志回放”。跑的时候把每轮合并的(i, j, dq)写到磁盘，而不是全部放在内存的列表里。这样即使图有上亿条边，算法主循环使用的空间也只有一个堆的大小。跑完之后再按着日志回放，用并查集算出最终社区标签。这种方法让内存占用从 O(n + m) 降到 O(m + log 合并次数)，我已经在几百万节点的图上验证过。

还有一个小细节：堆初始化的时候如果全图边数非常大，每对节点都heappush会很慢。我一般先对图做一次“邻居数量统计”，只对内部边权贡献大于total_weight / 1e7的社区对入堆。这个过滤阈值不影响结果，因为低于这个量级的增量对 Q 的贡献可以忽略，但它能把建堆时间缩短一半以上，算是血泪经验。

另一个值得养成的习惯是：在跑之前把边权重做一次 99 分位截断。把权重超过 99 分位的值压缩到 99 分位，能防止极端权重主导合并方向。这个处理只影响边权分布，不改变图结构，却常常能让社区结果从“几个巨无霸社区加一堆碎片”变成相对均匀的划分。

fast-Newman 算法的核心就三件事：模块度增量公式、最大堆、惰性删除。把这三件事理解透，调参和排错都顺理成章。如果你第一次跑出来的社区数不合理，先从连通分量和权重分布下手，不要急着改算法。希望帮到你。

本文还有配套的精品资源，点击获取