企业官网建设流程全解析

社区发现里，FN算法是绕不开的经典。我之前处理一张一万多节点的社交网络图时，对比过几种社团划分方案，最后还是回到最朴素的FN（Fast 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. 增量合并背后的矩阵账本：手把手推导ΔQ

2.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_j；
• j对应的行列直接删掉。

我一开始写代码时差点在这里翻车：只更新了第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(axis=1) 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, axis=0) self.E = np.delete(self.E, j, axis=1) new_a = np.delete(self.a, j, axis=0) 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_partition

main函数里的调用方式很简单：

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(axis=1) 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_degree=5, min_community=30, seed=2024 ) # 去掉额外属性，保留社区标签 ground_truth = {node: comm[0] for node, comm in G.nodes(data="community")}

跑FN算法后，最佳划分的真实社区数和LFR生成的ground truth基本对得上。mu=0.1时几乎完全吻合；mu调到0.4以上，FN会出现社区合并过头的现象，这点和理论预期一致，毕竟贪心合并天然容易被稠密子图带偏。

评估划分质量和ground truth的一致性，我推荐用调整兰德指数（ARI）。scikit-learn里面直接有函数：

from sklearn.metrics import adjusted_rand_score

ARI值大于0.8说明划分质量相当好，0.5到0.8属于尚可。FN算法在mu=0.1的LFR图上通常能到0.9以上。

4.3 性能观察表

我整理了一份本机测试的大致时间感受，图都是LFR生成的稀疏网络，配置是普通笔记本：

这里的耗时不是精确基准，但量级很有参考价值。可以看出基础版在小规模图上完全够用，堆优化版本的优势在大图上才真正体现。

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值几乎没有变化。社区发现这类工作，预处理往往比算法本身更值得花时间。