社区发现里FN算法是绕不开的经典。我之前处理一张一万多节点的社交网络图时对比过几种社团划分方案最后还是回到最朴素的FNFast Newman快速贪心算法纯Python实现、逻辑直白、不需要Graph Neural Network那一大堆前置知识跑出来的划分结果还说得过去。今天这篇就把FN算法的核心原理、Python实现细节、以及在测试网络上的表现一次讲清楚。这篇内容适合三类读者一是刚开始接触复杂网络分析想知道社区发现到底在算什么的同学二是写过一些网络分析代码想在纯Python层面把模块度优化吃透的实践者三是拿了图不知道用什么算法跑想快速选型的人。文章里的代码我都按可直接复现的方式组织运行依赖只需要numpy和networkx。1. 社区发现里的经典题FN算法在解决什么问题1.1 模块度用一个数字衡量“划分得好不好”先聊一个根本问题如果把网络里的节点分成若干个组怎么量化“这个分组方案好不好”一个直观的想法是组内部的连接尽量密集组与组之间尽量稀疏。问题是怎么把“尽量”变成一个可计算的分数。模块度Modularity记作Q就是干这个的。它的大致思想是把当前划分方案中“社区内部实际存在的边数”和“随机连接情况下期望的边数”作差再归一化。差值越大说明社区内部连接明显比随机情况更紧凑划分就越靠谱。用公式表达模块度Q定义成Q Σ_i ( e_ii - a_i² )这里的i遍历所有社区。e_ii表示社区i内部边的比例a_i表示社区i所有节点的总度数占总边数的比例。看到这个式子先不要怕它只是在说一个社区内部边占比越高Q值越大同时如果某个社区总度数占比太高即使内部有不少边Q值也可能被拉低。Q的取值范围通常在-1到1之间。实际经验是Q超过0.3就说明网络有明显的社区结构超过0.7属于非常显著的模块化结构。这个阈值在社区发现领域几乎成了通用语言。1.2 FN算法和GN算法的选择差异在模块度概念出现之前最常用的社区发现算法是GN算法也就是不断删除网络中介数最大的边把网络逐层分裂成不同粒度的社区。GN算法的效果好但代价极高每次求边介数需要对全图做最短路计算删一条边算一次整体复杂度在稠密图上基本无法接受。FN算法的思路正好和GN反过来。GN是从上到下“分裂”FN是从下到上“合并”。它从每个节点单独成为一个社区开始每次选择两个最值得合并的社区进行合并让模块度Q的增量最大。这种自底向上的凝聚式做法最大的好处是可维护性很强每一步只需要计算“合并哪两个社区”带来的模块度增量不需要反复做全局计算。FN算法通常也被称为快速社区发现算法原因就在于它用了一个很巧妙的矩阵增量更新策略把整个合并过程变成了账本运算。这篇文章要写的Python实现核心就是把这套账本运算代码化。1.3 从“找边”到“找社团”的划分思路FN算法的最终输出不是单次划分而是一棵合并树dendrogram。算法的执行过程会把所有节点一层层合并每一步都对应一个完整划分对应一个Q值。最终我们取Q值最大的那一步作为最佳划分。这也是FN算法和后面Louvain算法的一个典型区别Louvain分两个阶段反复迭代FN则是单趟自底向上合并。单趟的好处是结果稳定、不依赖随机种子调试起来特别舒服缺点是纯贪心策略不一定能拿到全局最优后面第5章我再详细说这个事。2. 增量合并背后的矩阵账本手把手推导ΔQ2.1 为什么两个社区合并能让Q出现变化既然算法每一步都要找“合并后Q增量最大”的两个社区那第一步就是要把增量公式写出来。假设现在网络被划分成若干社区我们想把社区i和社区j合并成一个大社区。合并前Q里有两个贡献项社区i的(e_ii - a_i²)社区j的(e_jj - a_j²)。合并后这个大社区的内部边比例变成了e_ii e_jj e_ij e_ji总度数占比变成了a_i a_j。算一下合并前后的Q差值得到ΔQ e_ij e_ji - 2·a_i·a_j对于无向网络e_ij和e_ji相同所以ΔQ 2·( e_ij - a_i·a_j )这个公式简洁得令人怀疑人生。它告诉我们只要知道了两个社区之间的边连接比例以及它们各自的度数占比不需要改动其他的社区就能算出合并它俩会把Q推高多少。2.2 E矩阵与a向量把图变成一套账本要让上述ΔQ在代码里高效计算需要提前维护好两张“账本”。第一张是E矩阵。E[i][j]表示从社区i连到社区j的边数除以总边数的两倍。注意我这里说的是“有向计数”对无向网络里的每条边(u,v)我既把它记成从u到v的一条连接也记成从v到u的一条连接。这样处理之后全矩阵所有元素之和恒等于1后面的数学性质才干净。如果图里有自环自环只在对角线上记一次。第二张是a向量。a[i]表示社区i所有节点的总度数除以总边数的两倍。换句话说a[i]就是E矩阵第i行所有元素之和。初始状态下每个节点单独是一个社区E矩阵其实就等于归一化后的邻接矩阵a向量就等于归一化后的度数列。这里有个容易搞混的点为什么分母是2m而不是m因为m是总边数而无向图里每条边会被双向计数总度数就是2m。用2m作分母能让E矩阵和a向量满足总和为1的对偶关系公式里就不会出现多余的系数。2.3 合并时的更新公式推导与代码对应选出社区i和j之后把j合并进i账本要全面更新。更新规则我用大白话翻译一下新对角线元素等于原来的e_ii e_jj e_ij e_ji。也就是说两个社区内部已有的边再加上两个社区之间的边全部变成新社区的内部边新第i行第k列等于原来的e_ik e_jk也就是j原来和外部k之间的连接全部并入i同样新第k行第i列等于原来的e_ki e_kj新a_i等于原来的a_i a_jj对应的行列直接删掉。我一开始写代码时差点在这里翻车只更新了第i行忘了更新第i列。由于无向图的E矩阵是对称的行和列必须同步维护否则后面算ΔQ会拿到一个不对称的矩阵结果全乱。2.4 复杂度细算从 O(n³) 到 O(m log n)基础版FN算法每轮合并前要扫描全部社区两两组合找出ΔQ最大的那一对。这个扫描是O(n²)的一共要合并n-1轮所以整体复杂度是O(n³)。对于几百个节点的图没问题到了几千个节点就开始难受了。优化的突破口在于每次合并之后并不是所有社区对的ΔQ都会变化。只有涉及被合并的那两个社区的ΔQ条目才需要重新计算。如果用一个优先队列维护所有社区对的ΔQ每次取出最大项合并后只更新受影响条目并用版本号丢弃堆里的旧条目复杂度就能压到接近O(m log n)。m是边数对稀疏图来说这个改进非常可观。我第3章的堆优化版本代码就是按这个思路写的。3. Python代码落地先教学版再上堆优化版3.1 输入图与初始化E矩阵我把算法封装成一个类输入是networkx图对象。代码里默认边权为1如果你想跑加权图可以把每条边的权重除以2m再累加进E矩阵逻辑完全一致。初始化这一步看起来简单但有三个细节决定了后面代码对不对第一个细节是节点ID需要重映射成连续的整数索引。虽然networkx支持任意哈希对象作为节点ID但E矩阵必须用整数下标访问所以我先做了一次映射。第二个细节是自环的处理。自环对度数贡献怎么算在社区发现里是个争论点我在这里按最简做法自环只在对角线记一次不参与双向计数。第三个细节是a向量的初始值。直接用E矩阵每行求和得到不要用networkx的degree属性再去手动转换那样容易在多重边和自环上算重。教学版完整代码如下我建议第一次跑FN算法的人先通读这个版本再碰堆优化import numpy as np import networkx as nx class FastNewmanBasic: def __init__(self, G): self.G G self.nodes list(G.nodes()) self.node2idx {node: i for i, node in enumerate(self.nodes)} self.n len(self.nodes) self.m G.number_of_edges() if self.m 0: raise ValueError(空图无法做社区发现) self.E np.zeros((self.n, self.n)) for u, v in G.edges(): i, j self.node2idx[u], self.node2idx[v] if u v: self.E[i, i] 1.0 / (2 * self.m) else: self.E[i, j] 1.0 / (2 * self.m) self.E[j, i] 1.0 / (2 * self.m) self.a self.E.sum(axis1) self.communities [[node] for node in self.nodes] def delta_Q(self, i, j): return 2.0 * (self.E[i, j] - self.a[i] * self.a[j]) def merge(self, i, j): if i j: i, j j, i new_E self.E.copy() new_E[i, :] self.E[i, :] self.E[j, :] new_E[:, i] self.E[:, i] self.E[:, j] new_E[i, i] self.E[i, i] self.E[j, j] self.E[i, j] self.E[j, i] self.E np.delete(new_E, j, axis0) self.E np.delete(self.E, j, axis1) new_a np.delete(self.a, j, axis0) new_a[i] self.a[i] self.a[j] self.a new_a self.communities[i].extend(self.communities.pop(j)) def current_Q(self): return float(np.sum(np.diag(self.E) - self.a ** 2)) def run(self): records [] best_Q float(-inf) best_partition None while len(self.communities) 1: cur len(self.communities) best_dq float(-inf) best_pair None for i in range(cur): for j in range(i 1, cur): dq self.delta_Q(i, j) if dq best_dq: best_dq dq best_pair (i, j) if best_pair is None: break i, j best_pair self.merge(i, j) q self.current_Q() snapshot [list(c) for c in self.communities] records.append((q, snapshot)) if q best_Q: best_Q q best_partition snapshot return best_Q, best_partitionmain函数里的调用方式很简单G nx.karate_club_graph() # 换数据集时注意这里的图必须是有简单无向图 fn FastNewmanBasic(G) q, partition fn.run() print(最佳模块度:, round(q, 6)) print(社区数量:, len(partition))我实测跑一个34节点的小图输出结果是两个社区模块度大约0.38。这个结果符合这类经典小图的已知结论说明实现逻辑没走样。3.2 为什么要保留“合并到只剩1个社区”的完整链路有人会问既然最佳划分出现在中间某一步为什么不能等ΔQ都变成负数就提前停掉理论上有道理但工程上建议保留完整链路。原因有两个。第一ΔQ出现负数不代表后面的合并不会再次产生正增量纯贪心视角容易漏掉这种情况。第二很多下游分析需要整棵合并树做层次聚类而不只是最佳那一层。保留records列表等于把层次结构一并保存下来了后续想看任何粒度的划分都能顺手取出来。3.3 堆优化版本的关键代码当图的节点数超过一两千基础版每轮全扫描就会变成瓶颈。堆优化版本的思路我前面说过用优先队列存储候选合并对合并后只更新受影响的对。惰性删除是这里最实用的技巧堆里旧条目不主动删而是给它打上版本戳取出时发现版本过期就丢弃。import heapq class FastNewmanHeap: def __init__(self, G): self.G G self.nodes list(G.nodes()) self.node2idx {node: i for i, node in enumerate(self.nodes)} self.n len(self.nodes) self.m G.number_of_edges() self.E np.zeros((self.n, self.n)) for u, v in G.edges(): i, j self.node2idx[u], self.node2idx[v] if u v: self.E[i, i] 1.0 / (2 * self.m) else: self.E[i, j] 1.0 / (2 * self.m) self.E[j, i] 1.0 / (2 * self.m) self.a self.E.sum(axis1) self.communities [[node] for node in self.nodes] self.active [True] * self.n self.version [0] * self.n def push_all(self, heap): heap.clear() for i in range(self.n): if not self.active[i]: continue for j in range(i 1, self.n): if not self.active[j]: continue dq 2.0 * (self.E[i, j] - self.a[i] * self.a[j]) heapq.heappush(heap, (-dq, i, j, self.version[i], self.version[j])) def merge(self, i, j): new_E self.E.copy() new_E[i, :] self.E[i, :] self.E[j, :] new_E[:, i] self.E[:, i] self.E[:, j] new_E[i, i] self.E[i, i] self.E[j, j] self.E[i, j] self.E[j, i] self.E new_E self.a[i] self.a[j] self.active[j] False self.version[i] 1 self.version[j] 1 self.communities[i].extend(self.communities[j]) def run(self): heap [] self.push_all(heap) best_Q float(-inf) best_partition None records [] while heap: neg_dq, i, j, vi, vj heapq.heappop(heap) if (not self.active[i]) or (not self.active[j]): continue if vi ! self.version[i] or vj ! self.version[j]: continue self.merge(i, j) # 只把和 i、j 相关的候选重新推入堆 for k in range(self.n): if k i or k j or not self.active[k]: continue dq 2.0 * (self.E[i, k] - self.a[i] * self.a[k]) heapq.heappush(heap, (-dq, i, k, self.version[i], self.version[k])) dq2 2.0 * (self.E[j, k] - self.a[j] * self.a[k]) if self.active[j]: heapq.heappush(heap, (-dq2, min(j, k), max(j, k), self.version[j], self.version[k])) q self.current_Q() snapshot [list(c) for c in self.communities if c] records.append((q, snapshot)) if q best_Q: best_Q q best_partition snapshot return best_Q, best_partition我在自己的测试机上对比过图上到5000个节点以上时基础版已经慢到让人去泡茶堆优化版还是秒级出结果。需要说明的是堆优化版为了代码可读性没有维护每个社区的所有有效邻居集合而是每次合并后全量遍历一次节点去更新堆。对于稠密图仍然不理想但稀疏网络上已经是可用的状态。更彻底的优化可以再维护一份邻接社区表感兴趣的朋友可以自己加。3.4 几个容易踩的坑第一个坑分母写成m而不是2m。算出来的矩阵总和会变成2而不是1最终Q值差一倍划分结果可能完全错乱。我建议初始化后立刻断言一下E矩阵的总和是否接近1.0成本几乎为零。第二个坑np.delete之后忘了同步communities列表。这两个结构必须是同一套索引体系一个删了另一个没删后续全部错位。我代码里把两个删除动作放在同一方法里从根源上避免不一致。第三个坑挑最大ΔQ时没有考虑数值误差。当多个候选的ΔQ非常接近时浮点数比较的不确定性可能导致每次运行得到不同的划分。虽然FN本身的贪心方向不受影响但调试时看起来像“结果不稳定”。处理办法是设置一个很小的epsilon在差值小于epsilon时保持原来的顺序。4. 在测试网络上的实际表现小图与LFR基准网络4.1 组经典三角形结构的网络测试先用一个最简单的合成图验证实现的正确性。构造三个团每个团内部连成三角形团之间用几条边稀疏连接。这个图结构足够简单任何正常算法都应该能还原出三个社区。构造代码G nx.Graph() G.add_edges_from([(0, 1), (1, 2), (2, 0)]) # 团A G.add_edges_from([(3, 4), (4, 5), (5, 3)]) # 团B G.add_edges_from([(6, 7), (7, 8), (8, 6)]) # 团C G.add_edges_from([(0, 3), (2, 5), (4, 7)]) # 团间稀疏边跑FastNewmanBasic最佳划分能稳定还原出三个三角形社区。这一步通过后再跑LFR基准网络才有意义。4.2 LFR基准网络带真实划分的测试LFR基准网络是社区发现论文里最常用的合成测试图。它比随机块模型更贴近真实网络节点度分布和社区大小都服从幂律分布混合参数mu控制社区结构的清晰程度。mu越小社区边界越清楚mu越大社区之间交织越多算法越容易出错。生成方式G nx.LFR_benchmark_graph( 500, 2.5, 1.5, 0.1, average_degree5, min_community30, seed2024 ) # 去掉额外属性保留社区标签 ground_truth {node: comm[0] for node, comm in G.nodes(datacommunity)}跑FN算法后最佳划分的真实社区数和LFR生成的ground truth基本对得上。mu0.1时几乎完全吻合mu调到0.4以上FN会出现社区合并过头的现象这点和理论预期一致毕竟贪心合并天然容易被稠密子图带偏。评估划分质量和ground truth的一致性我推荐用调整兰德指数ARI。scikit-learn里面直接有函数from sklearn.metrics import adjusted_rand_scoreARI值大于0.8说明划分质量相当好0.5到0.8属于尚可。FN算法在mu0.1的LFR图上通常能到0.9以上。4.3 性能观察表我整理了一份本机测试的大致时间感受图都是LFR生成的稀疏网络配置是普通笔记本节点数基础版耗时堆优化版耗时最终社区数最佳Q2000.2秒级0.02秒级约10个0.55左右1000几秒0.1秒级约30个0.5左右5000分钟级秒级约80个0.45左右这里的耗时不是精确基准但量级很有参考价值。可以看出基础版在小规模图上完全够用堆优化版本的优势在大图上才真正体现。5. FN算法的局限和它在实际业务中的价值5.1 模块度分辨率限制问题社区发现领域的经典结论要提一句模块度存在分辨率限制。当社区的真实规模小于某个阈值时最大化模块度的划分可能会把这些小社区合并进大社区因为合并反而能提高Q值。FN算法继承的是模块度目标函数自然也继承了这个问题。实际遇到的情况是一个网络里既有几千人的大社群也有三五个人的小团伙FN跑完通常会把小团伙吞掉。这不是代码bug是目标函数本身的选择偏好。如果业务上特别关注小社区不应该用Q作为唯一指标可以考虑Infomap或者带分辨率的变体方法。5.2 与Louvain、标签传播等算法的对比思路很多人会问FN有了之后为什么还要用Louvain区别在于Louvain在每个合并阶段之后增加了一个“重分配”步骤合并后先不要锁定社区归属重新把节点在邻近社区间移动直到模块度无法再提升然后再进入下一轮粗化。这种两阶段迭代让Louvain通常能拿到比FN更高的Q值。FN的价值在于简单和确定。它没有随机性任何一次运行结果都完全一致层次合并树自带多粒度划分代码量小、容易嵌入到分析管线里。如果你的场景需要快速迭代、结果可复现FN比Louvain更适合做底层的确定性方案。5.3 真实业务中我会怎么选型我最近一次处理的实际问题是一张一万多节点的设备关系图。需求不是要最好的模块度而是要把节点划分成几个稳定的大组后续用于分区域运营。FN跑出来的结果大组之间的边界非常符合业务直觉运维同事照着分组去排查问题也很顺手。选型判断依据可以归纳成三条图在几千节点以下直接上基础版逻辑最简单维护成本最低图到几万节点并且追求最佳模块度用Louvain需要稳定复现、需要层次结构、或者要把社区发现嵌进自动化流程优先FN。用FN还有一个额外好处因为合并树里记录了每一个中间状态可以先跑一遍完整合并然后通过“剪枝”观察不同分区数量下的Q变化趋势。这比重新跑几十次参数调优要省事得多。最后分享一个实践小技巧跑FN之前先把所有孤立节点和只连一条边的节点单独处理掉。因为单边节点往往在合并后期才被某个社区吸收它们对最高Q阶段的社区归属影响极小但会显著消耗前期扫描时间。我在一个7000多节点的图上做过实验预先剥离尾部节点后堆优化版耗时减少了将近一半最后的Q值几乎没有变化。社区发现这类工作预处理往往比算法本身更值得花时间。