简介：复杂网络社区发现是网络科学的重要方向，旨在从复杂网络中识别紧密连接的节点组，广泛应用于社交网络分析、生物信息学与引文分析；资源包面向相关领域的研究者与工程师，系统整理了社区发现常用算法、评价指标与经典数据集，可作为课程设计、科研实验或工程项目的参考基线。压缩包共28个文件，容量4.82MB，文件类型覆盖8个gml网络数据、6个Python算法脚本、6个dat数据集、4个png效果示意图以及说明文档等。其中Python脚本包含GN算法与谱聚类实现，并提供了可运行的示例脚本；gml与dat文件内置了空手道俱乐部、美国大学生足球、海豚社交网络、政治博客等经典网络数据。评价指标方面整合了NMI、模块度等相关计算代码，同时附有可视化对比图，便于直观理解不同算法划分效果。截至目前已有143人浏览学习，整体包体小巧、目录层次清晰，算法代码与数据配套，适合初学者快速上手，也便于研究者在此基础上扩展和改进。
1. 社区发现算法看起来像是「把图分几堆」，其实考验的是判断力
复杂网络社区发现算法，听起来就是把图中的节点按亲疏关系分成若干组，真跑到项目里却是一道选择题：同一张图，换一种算法，社区数量能从几十跳到几百。我在某跨平台系统的用户互动图上踩过这个坑，Louvain 给出八十多个社区，标签传播跑出三百多个，而且各自的模块度都「合理」。这个方向真正的难点从来不是把代码跑通，而是知道算法在什么结构上失效、指标在什么时候骗人、数据集到底带不带标准答案。这篇笔记围绕社区发现算法、评价指标与常用数据集整理这条操作链展开，适合刚进入网络分析、又要对结果负责的开发者照着落地。
社区发现本质上是一个无监督问题。没有标准答案时，你只能靠内部评价；有标准答案时，你又得小心标签对齐。把这两条路同时走通，才算真的会做社区发现。
2. 前置知识：模块度、图数据和三条算法路线的选择逻辑
2.1 模块度：从「组内密、组间疏」到可计算的优化目标
社区最通用的直觉是「组内连接密集、组间连接稀疏」。把这句话变成可计算的目标，最常用的是模块度。它的基本思想是把真实网络和一个随机重连的零模型比较：如果两个节点之间实际连边数明显高于随机情况下的期望连边数，它们就更应该被分到同一个社区。
模块度写成公式大致是这样：
[ Q = \frac{1}{2m}\sum_{i,j}\left[A_{ij}-\frac{k_i k_j}{2m}\right]\delta(c_i,c_j) ]
其中 (A_{ij}) 是邻接矩阵元素，(k_i) 是节点 (i) 的度，(m) 是总边数，(\delta(c_i,c_j)) 表示两个节点是否被分到同一个社区。这个值的直观含义是：社区内部的边数，比随机连边期望多出多少。
模块度最大的价值是把社区发现问题转成了一个优化问题：搜索一种划分，让 Q 尽量大。因此很多算法，比如 Louvain，本质上都在做模块度最大化。但要记住，模块度是一个优化目标，不是一个真理标准。它有分辨率极限，倾向于把小的真实社区并进大社区里。后面避坑部分我会单独展开，这里先把这个概念立住。
2.2 输入数据：边列表、邻接矩阵与带权图的选择
社区发现的第一步是把网络读进来。常见的数据格式有三种：边列表、邻接矩阵、邻接表。边列表最适合真实业务数据，因为大多数导出的日志、关系表就是「起点、终点」两列。邻接矩阵适合小图和数学推导，但规模一大就非常浪费内存。邻接表本质上是稀疏存储，适合写自定义算法时使用。
我一般先用边列表建图，再顺手做一次基础体检。这里给出一段可复用的 Python 片段：
import networkx as nx # 读取边列表：第一列源节点，第二列目标节点，第三列边的权重 G = nx.read_edgelist( "network.txt", delimiter="\t", nodetype=str, data=(("weight", float),), ) # 权重为 0 的边在多数算法里等于不存在，直接删掉，避免后续误解 zero_edges = [(u, v) for u, v, w in G.edges(data="weight") if w == 0] G.remove_edges_from(zero_edges) # 检查基本情况：节点数、边数、孤立点 print(G.number_of_nodes(), G.number_of_edges()) print(list(nx.isolates(G))[:10])这里的nodetype=str是为了防止节点 ID 被自动转成整数后丢失前导零，比如节点编号0123被读成123。data=(("weight", float),)表示第三列按浮点数读取，如果你的数据没有权重，把这一项去掉即可。孤立点对后续评估影响很大，因为社区编号里不会出现它们，标准答案里却有，少一个节点就会导致标签长度对不上。
2.3 算法路线图：优化式、传播式、谱式
社区发现算法虽然多，但按核心思想可以分为三类，理解这三类比背算法名字更有用。
第一类是模块度优化路线，代表是 Louvain。它的特点是快、不需要预先指定社区数量，适合作为任何项目的第一版基线。第二类是传播路线，代表是标签传播算法。它把一个节点的标签不断传给邻居，最终达成局部一致，速度极快但随机性强。第三类是谱路线，核心是构造拉普拉斯矩阵做特征分解，然后对特征向量聚类。谱方法对非凸形状的社区更鲁棒，但需要指定社区数量，计算成本也高。
这三条路线不是互斥的。我习惯的路径是：先用 Louvain 跑一版，看社区数量级和大小分布；再用标签传播验证稳定性；如果涉及小规模、有明确业务要求的场景，再上谱聚类。后面第 3 章会把每条路线的参数逐一讲透。
3. 社区发现算法跑通细节：从 Louvain 到标签传播和谱方法
3.1 Louvain：先贪后凝，resolution 才是关键参数
Louvain 是目前用得最多的社区发现算法，它的思路分两个阶段：先让每个节点尝试加入邻居社区，使模块度增量最大；然后把每个社区收缩成一个超节点，重复前面的过程。整个过程不需要指定社区数量，计算复杂度接近线性，非常适合百万节点级别的图。
在 Python 里，最省事的实现是 python-louvain 库，它对 NetworkX 的图对象直接操作。下面这段代码可以完成一次基础划分：
import networkx as nx import community as community_louvain G = nx.read_edgelist("edge_list.csv", delimiter=",", nodetype=int) # resolution 是分辨率参数，默认 1.0 partition = community_louvain.best_partition( G, weight="weight", resolution=1.0, ) # partition 是 dict：{节点: 社区编号} counts = {} for c in partition.values(): counts[c] = counts.get(c, 0) + 1 print(len(counts), sorted(counts.values(), reverse=True)[:10])resolution是最值得调的参数。它大于 1 时，算法倾向于切出更多小社区；小于 1 时，倾向于合并成大社区。如果你的业务里社区普遍偏小，比如用户兴趣小组，可以把resolution调到 1.2 到 1.5；如果目标是找大规模业务板块，比如产品大类，可以降到 0.8 左右。weight="weight"让算法把权重纳入模块度计算，如果你希望所有边一视同仁，就不要传权重。
3.2 标签传播：零参数背后的随机性陷阱
标签传播（Label Propagation Algorithm，简称 LPA）的思路非常朴素：每个节点初始持有自己的唯一标签，然后不断把邻居中出现最多的标签作为自己的新标签。这个过程迭代几轮后，同一社区内的节点会收敛到同一个标签。它最大的优点是没有参数、没有目标函数，跑起来极快。
NetworkX 里自带异步标签传播，可以直接调用：
import random from networkx.algorithms.community import asyn_lpa_communities # 先固定随机种子，否则同一次实验两次结果可能不同 random.seed(2024) # 返回的是生成器，需要转成列表 communities = list(asyn_lpa_communities(G, weight="weight", seed=2024)) print(len(communities))seed=2024是关键。LPA 的初始标签分配和节点遍历顺序都有随机性，不固定种子，你会在同一份数据上得到不同的社区数量。即便固定了种子，单次结果也不一定是最稳定的。我一般会跑 10 次，统计每个节点对出现的社区归属，按多数投票得到最终划分。这一招能明显减少偶发的碎片社区。
3.3 Infomap 与谱聚类：识别结构时的两个补充
如果社区内部结构比较松散、社区之间却存在较多长距离连接，基于模块度的算法容易失效。这时可以考虑 Infomap。它的思路来自信息论：把网络上的随机游走路径压缩成最短编码，同一个社区的节点共享同一个编码模块。Infomap 对边权重的尺度非常敏感，同样的数据，权重放大十倍，结果可能完全不同。因此使用前最好对权重做归一化。
谱聚类则是另一类常用补充。它的流程是构造图的拉普拉斯矩阵，取前 k 个特征向量，再对特征向量做 KMeans。由于涉及到特征分解，谱聚类在大图上非常吃内存。它最大的参数是n_clusters，也就是你必须提前知道或猜出社区数量。下面是一个基于稀疏邻接矩阵的实现片段：
import networkx as nx from sklearn.cluster import SpectralClustering G = nx.read_edgelist("edge_list.csv", delimiter=",", nodetype=int) # 转成 scipy 稀疏矩阵，避免用稠密矩阵撑爆内存 A = nx.to_scipy_sparse_array(G, nodelist=list(G.nodes()), weight="weight") sc = SpectralClustering( n_clusters=8, affinity="precomputed", random_state=42, ) labels = sc.fit_predict(A)affinity="precomputed"表示传入的矩阵就是相似度矩阵，这里用的邻接矩阵。random_state=42控制 KMeans 的随机初始中心，保证可复现。谱聚类的社区数量 k 如果定错了，结果会非常难看，通常我会先用 Louvain 跑一次，把得到的社区数量作为谱聚类的 k 初始值，再人工调整。
3.4 选型参考：不同数据规模下怎么搭配
没有万能算法，至少要有一张对比表，才能在拿到新数据时快速选型。下面是我常用的判断框架：
| 路线 | 是否需要指定社区数 | 适合规模 | 典型缺陷 | 我什么时候用它 |
|---|---|---|---|---|
| Louvain | 否 | 百万到千万边 | 分辨率盲区，易并吞小社区 | 默认第一版基线 |
| 标签传播 | 否 | 极大规模 | 单次随机性强 | 快速验证、多阶多数投票 |
| Infomap | 否 | 十万节点内 | 对权重尺度敏感 | 发现多层次结构 |
| 谱聚类 | 是 | 中到小图 | 特征分解代价高，k 难定 | 非凸社区、业务容忍低 |
对于百万边以内的数据，我常把 Louvain 和标签传播组合使用：Louvain 给出稳定主体，标签传播多数投票后给出碎片补充。两者结果重叠度高的社区，基本可以确定是天然社区；重叠度低的，就要谨慎对外输出。
4. 评价指标与常用数据集组合：让分数不再「自己骗自己」
4.1 模块度读法：什么算好，什么算可疑
模块度是社区发现最常用的内部评价指标，因为它不需要标准答案。一般来说，模块度超过 0.3 就可以说图里有明显的社区结构，超过 0.7 已经属于非常强的结构。但我在实际项目中不会单独看 Q 值，而是同时看两个附加信息：社区数量和最大社区占比。
如果 Q 值很高，但社区数量只有五六个，其中一个大社区占了 80% 的节点，这是典型的模块度分辨率问题，算法把大量细粒度社区并到了一起。这时不能迷信 Q 值，要调大resolution再跑一次，对比社区数量是否出现明显变化。模块度适合作为不同参数下的比较工具，而不是绝对质量标尺。
4.2 NMI 与 ARI：拿到标准答案后读什么
在合成数据上做评测时，我们手里有每个节点的真实社区标签。这时候需要用外部指标衡量「算法划分接近真实划分的程度」。最常用的两个是 NMI（归一化互信息）和 ARI（调整兰德指数）。NMI 衡量两个划分共享多少信息，取值范围 0 到 1，越接近 1 越好；ARI 基于兰德指数的随机期望修正，随机划分的期望值是 0，越接近 1 越好。
计算这两个指标时有一个非常容易犯的错：社区编号只是标签，不是有意义的顺序。算法输出的社区编号为 0、1、2，真实标签可能是 A、B、C，两者完全没有对应关系，不能直接按编号比较。所以要按节点对齐，而不是按社区编号对齐。下面是一个标准计算示例：
from sklearn.metrics.cluster import normalized_mutual_info_score, adjusted_rand_score import json truth = json.load(open("ground_truth.json")) pred = json.load(open("prediction.json")) # 两个列表等长，每个位置的元素表示同一个节点所属的社区 nmi = normalized_mutual_info_score(truth, pred) ari = adjusted_rand_score(truth, pred) print(f"NMI={nmi:.3f}") print(f"ARI={ari:.3f}")这里的truth和pred是节点顺序一致的标签列表。如果图里有孤立点，一定会出现长度不一致，处理方式放在第 5 章避坑部分。阅读指标时还要注意：NMI 对社区大小分布不敏感，哪怕你把一个大社区拆成两个，NMI 仍然可能很高；ARI 则对节点分配错误非常敏感，拆错一个社区都会明显拉低。所以两个指标要一起看，只报 NMI 是常见的单边行为。
4.3 常用数据集：真实图、小规模样例与 LFR 合成基准
做社区发现评测时，数据集分三类。第一类是真实网络数据，来自社交网络、论文合作、通信记录等场景，优点是有业务意义，缺点是没有完整的标准答案，只能做内部评价。第二类是小规模示例图，节点几十到几百，适合调试代码和验证流程。第三类是合成基准图，其中最常见的是 LFR 基准，它能在已知社区结构参数的控制下生成网络，是评价算法的标准场地。
LFR 基准最重要的一个参数是 mu，表示跨社区边的比例。mu 越小，社区边界越清晰；mu 越大，社区越模糊，算法越容易出错。用 python-igraph 可以很方便地生成 LFR 图：
from igraph import Graph # n：节点数；k：平均度；maxk：最大度数；mu：跨社区边比例 g, membership = Graph.LFR( n=500, k=8, maxk=30, mu=0.2, ) # membership 是每个节点的真实社区编号，作为 ground truth 使用 print(len(membership), max(membership) + 1)mu=0.2属于比较清晰的社区结构，一般算法都能跑好。真正区分算法能力的是 mu 从 0.3 到 0.6 的区间。评测时我习惯生成一组不同 mu 的图，比如 0.1、0.3、0.5，观察指标随模糊度下降的曲线，而不是只在一个参数上比较。
4.4 组合跑分：哪些指标放在一起结论才可信
单一指标很难支撑结论。我建议至少记录三样东西：模块度、NMI、ARI，外加一个业务指标，比如社区数量或最大社区占比。合成数据上看 NMI 和 ARI，真实数据上只看模块度和社区规模分布。两张表配合，既能说明算法在标准场景下的能力，也能说明它在真实数据上的行为。
一个参考组合是：在 LFR 不同 mu 数据集上跑 NMI 和 ARI，在真实图上跑模块度和社区数量，最后把算法稳定性的多次运行方差也记录下来。这样至少覆盖了「准确度、结构质量、稳定性」三个维度，比单独报一个 Q 值可信得多。
提示：真实网络一般没有 ground truth，不要试图给真实数据编造标准答案。把合成基准上的准确度指标和真实数据上的内部指标分开汇报，是行业里的常规做法。
5. 注意：五个常见的翻车现场，从分辨率问题到标签错位
5.1 现象：模块度很高，业务上却看不出社区意义
有次我在一个模拟项目 X 上做社区划分，Q 值到了 0.6，结果把结果交给同事后，对方直接反问「这二十个大组是拿什么业务口径切出来的」。细看才发现，算法把几个不同业务方向的节点全并到了一个大社区里，内部结构其实是散的。
原因：模块度存在分辨率极限。两三百个节点的小社区在模块度优化时，收益比不过并入大社区的代价，于是被悄悄吞并。这在大规模图上表现得非常明显。
解决：先用比默认值更大的resolution跑一遍，比如 1.5，对比社区数量变化；再按社区内部密度过滤，只保留内部边占比明显高于整体密度的社区。商业上宁可多分几个小社区，也不要一个说不清的大社区。
5.2 现象：NMI 很高、ARI 很低，两个指标打架
我在一组 LFR 数据上经常看到 NMI 0.9、ARI 只有 0.4 的情况。原因并不一定是算法差，而是两个指标对错误的敏感度不同。NMI 只关心「两个划分共享多少信息」，把一个大社区拆成两个，共享信息仍然很高；ARI 则把这种拆分当作分配错误，分数会明显下降。
解决：两个指标都要报，并且解释差异。如果 ARI 低但 NMI 高，大概率是算法把大社区切碎了。这时应该回到社区数量分布上，看看是不是分辨率参数过小。不要只挑好看的指标发出去。
5.3 现象：同样的代码连续跑两次，社区数量对不上
标签传播算法的一次运行，可能产生几十个随机碎片社区，第二次运行又是另一批碎片。我见过有同事用两次不同的 LPA 结果做业务统计，最后发现数据根本对不上，只能重跑。
原因：LPA 的标签初始化和节点遍历顺序有随机性，单次结果不是稳定解。
解决：固定随机种子，这是底线；更进一步的做法是运行 10 到 20 次，对每个节点的社区归属做多数投票。NetworkX 的asyn_lpa_communities支持seed参数，务必传入。如果策略允许，直接改用 Louvain 这类确定性更强的算法。
5.4 现象：百万节点图一跑就内存溢出
有次在某通信网络数据上跑谱聚类，代码写了不到十行，内存直接打满。原因也很简单，我用nx.to_numpy_array把网络转成了稠密矩阵。百万节点稠密矩阵需要 TB 级内存，任何机器都扛不住。
解决：改用稀疏矩阵。scipy.sparse和nx.to_scipy_sparse_array都是可靠选择。另外先过滤低度节点，比如把度为 1 的节点删掉，对社区主体结构影响很小，却能把内存降一个量级。Louvain 和 LPA 本身是稀疏友好的，把数据存成三元组边列表即可。
5.5 现象：评估时报标签长度不相等，社区编号还多了一类
这是最不值但最常见的报错。图里有孤立节点，Louvain 的partition字典里不会出现它们，而 ground truth 标签列表里包含了所有节点。结果两边长度天然对不上，脚本直接崩溃。
原因：孤立点没有参与社区分配，但在真实标签里占了一个位置。
解决：建图后先删孤立点，再按同一节点顺序生成两个标签列表。
import networkx as nx G.remove_nodes_from(list(nx.isolates(G))) # 以节点顺序为准，保证 truth 和 pred 一一对应 nodes = list(G.nodes()) pred_labels = [partition.get(n, -1) for n in nodes] truth_labels = [truth[n] for n in nodes] # 然后传入 NMI 或 ARI 计算这里的partition.get(n, -1)是双保险：万一有节点没进 partition，也能填一个占位值，而不是让程序中断。删孤立点是标准步骤，做完这一步，长度报错基本消失。
6. 把完整跑分收敛成一条命令：给复杂网络社区发现做基准入口
当你同时面对多套算法、多份数据集、多个指标时，最需要的是把整个评估流程压缩成一个可复现命令。我不想每次都在命令行里敲二十行 Python，所以我给标准流程做了一个入口脚本，下面是最小设计：
python run_benchmark.py \ --data lfr_n500_mu0.2.csv \ --algos louvain,label_propagation,infomap \ --metrics modularity,nmi,ari \ --seed 42--data传入数据标识，脚本内部根据标识找到图文件和 ground truth；--algos用逗号分隔算法；--metrics控制输出指标；--seed统一所有随机算法的种子。输出是一行 CSV：数据名、算法、种子、社区数量、模块度、NMI、ARI。同一条命令换一个--data参数，就能覆盖不同 mu 的跑分组合。
这个入口脚本的价值不只是少敲几行命令，而是把「哪个数据、哪个种子、哪次运行」全部记录在命令里。任何人拿到命令，都能复现同一组数。我现在的习惯是：正式评估至少跑三个 mu 档位，每个档位算法至少三次运行取均值，最后同时输出一张标准表和一张多径方差对比。走完这一轮，再决定哪个算法进入线上。
社区发现这条路上，最怕的不是算法报错，而是它不报错、结果还很好看，最后发现是参数没调对、指标看偏了。把算法、指标、数据集放在同一个工程里反复交叉验证，是我这几年趟过坑之后最想提醒的一句话。希望这些经验能帮到你少走一回弯路。
本文还有配套的精品资源，点击获取
