简介面向复杂网络与社团检测领域的学习者和研究者这组压缩包提供基于聚类渗透法CPM的MATLAB实现源码并包含算法原理与使用说明适合希望理解局部连接密度聚类思想并动手复现社团划分实验的用户。包体大小8.58MB文件总数达2026个其中包含大量社团划分结果数据如成员分布、度数分布、团结构、社区规模、重叠分布等每种类型均有235组样例另有文本说明、可视化图片及可执行的jar、dll等辅助工具可清晰还原CPM算法的运行过程与输出结构。目前已被307人浏览学习作者的介绍中详细阐述了从邻接矩阵构造、全局平均连接度计算、阈值迭代到社团生成的完整步骤并给出了MATLAB代码示例。借助这份资料读者可以对照CFinder相关脚本和结果图深入理解CPM参数调整对社团划分的影响也可直接基于源代码快速搭建自己的社团检测实验环境是复杂网络分析入门与进阶的实用参考。1. CPM.zip 里的 CPM 算法为什么社团划分会用到“团”这个概念打开 CPM.zip 之前先接受一个反直觉的设定CPMClique Percolation Method团渗透法不是在网络里“切一刀”做划分而是先在网络里找出所有不能再扩张的 k-团k 个节点两两相连的完全图再把共享 k-1 个节点的 k-团串起来串出来的连通块才是社团。这个机制让 CPM 天然支持重叠社团——一个节点可以同时属于多个圈子这正是社交网络里“一个人横跨同学、同事、发小三个圈子”的真实写照。相比 Louvain 这类把每个节点硬塞进一个社团的算法CPM 在生物网络、引文网络和推荐系统里有不可替代的位置。下面我会把这套 MATLAB 源代码怎么读、怎么跑、k 与渗透阈值怎么调、哪几步最容易翻车以及结果到底该怎么验证一次讲清楚。适合手里有 CPM.zip 却跑不出理想结果的从业者也适合准备把重叠社团划分纳入分析流程的新手。2. 从 k-团到社团CPM 的 MATLAB 核心代码与参数拆解2.1 邻接矩阵是唯一入口CPM 的输入形态决定一切CPM 的 MATLAB 代码通常只接受一种输入形态n×n 的方阵 AA(i,j)1 表示节点 i 和 j 之间有边。带权网络也不难把 1 换成权重即可但核心算法在二值矩阵上最稳。我不建议直接扔一个稀疏边表进去就跑因为后面每一处“两两相连”的判断都要随机访问矩阵邻接表在 MATLAB 里写起来又长又慢。这是拿到 CPM.zip 之后第一个要确认的事代码入口是不是邻接矩阵。如果是就老老实实把数据转成矩阵再喂进去。另一个容易看漏的点是自环。真实网络里几乎不会有自己指向自己的边但很多从 CSV 转过来的数据会带 A(i,i)1。CPM 在枚举 k-团时如果不对角线置零候选集合里会出现同一个节点出现两次的“伪团”结果直接崩。我一般会在调用前统一做一次无向化加去自环这两行是保命操作% 去自环对角线清零 A(logical(eye(size(A,1)))) 0; % 无向化上三角与下三角取并集防止单向边导致矩阵不对称 A max(A, A);注意max(A,A) 的原理是取 i→j 与 j→i 两个方向里较大的值作为边的存在性对无权网络来说只要任意一个方向有边结果就是 1。去自环要在无向化之前做虽然顺序反了也能跑但代码读起来容易误解。2.2 枚举 k-团再构建团图CPM 的“两次套娃”CPM 的实现可以拆成三个层次。第一层是在原网络里找所有 k-团。网络上“团”的定义是任意两个节点都相连的节点集合k-团就是包含 k 个节点的完全子图。第二层是把这些 k-团当作新节点如果两个 k-团恰好共享 k-1 个节点就在它们之间连一条边形成团图。第三层是在团图上找连通分量每个连通分量覆盖的原始节点取并集就是一个社团。这个“两次套娃”是 CPM 的核心也是它与其他社团算法最本质的区别。普通划分算法考虑的是“节点和节点怎么分开”CPM 考虑的是“小团体怎么通过重叠成员串成大团体”。共享 k-1 个节点意味着两个小团体只差一个成员就能互相融入这种弱连接是社交网络里最常见的抱团方式。k 越大要求越严社团越少这就是为什么把 k 从 3 调到 4 之后同一份网络往往只剩一两个大社团甚至什么都没有。CPM 内部并不是黑匣子它每一步都能被追踪k-团是原始结构里的“核”团图上的连通分量才是最终输出这也让后续排错变得有据可查。找 k-团是个组合问题理论上是 NP 完全的。常见的 MATLAB 实现里要么用 Bron-Kerbosch 回溯法要么像我下面这样用 nchoosek 枚举邻居组合。后者在稠密网络上会慢到让人想砸键盘但作为演示代码、或者处理几百个节点的中等网络它足够直观也更容易看出问题在哪。2.3 一段可抄的 CPM 核心代码骨架下面这段代码是我把常见的 MATLAB 版 CPM 源代码整理出的最小骨架两个函数分别是主函数和 k-团枚举函数保存到同一个 cpm_clustering.m 里就能跑function communities cpm_clustering(A, k) % CPM_CLUSTERING 团渗透法社团划分核心骨架版 % A : n×n 邻接矩阵要求无向、无自环、元素为 0/1 % k : k-团的团长度一般取 3k 越大社团越少 % communities : 1×m cell每个 cell 是一个社团的节点编号向量 n size(A, 1); % 第一步枚举所有 k-团 cliques find_all_cliques(A, k); if isempty(cliques) communities {}; return; end nc size(cliques, 1); % 第二步构建团图。两个 k-团共享 k-1 个节点就在团图中连边 adjC zeros(nc, nc); for i 1:nc for j i1:nc inter sum(ismember(cliques(i,:), cliques(j,:))); if inter k - 1 adjC(i, j) 1; adjC(j, i) 1; end end end % 第三步在团图上 BFS 找连通分量 seen false(nc, 1); communities {}; for s 1:nc if seen(s), continue; end comp []; q s; seen(s) true; while ~isempty(q) cur q(1); q(1) []; comp(end1) cur; nxt find(adjC(cur,:) ~seen); seen(nxt) true; q [q, nxt]; end % 该连通分量覆盖的所有原始节点 union_nodes unique([cliques(comp, :)]); if numel(union_nodes) k % 过滤碎片少于 k 个节点的块不算社团 communities{end1} union_nodes; end end end function cliques find_all_cliques(A, k) % 枚举所有 k-团对每个起点在邻居里选 k-1 个验证两两相连 n size(A, 1); cliques []; for s 1:n nb find(A(s, :)); if numel(nb) k - 1, continue; end comb nchoosek(nb, k - 1); for t 1:size(comb, 1) cand [s, comb(t, :)]; sub A(cand, cand); if all(sub(eye(k) 0)) % 非对角元素全为 1 才是完全图 cliques(end1, :) cand; end end end % 同一组节点可能被不同起点重复找到按行排序后去重 cliques unique(sort(cliques, 2), rows); end这段代码的逻辑分三块正好对应前面说的“两次套娃”。find_all_cliques 里 nchoosek(nb,k-1) 枚举当前节点的邻居组合然后 A(cand,cand) 取出候选之间的子矩阵用 all(sub(eye(k)0)) 判断除对角线外是否全为 1。eye(k)0 生成一个只取非对角线位置的逻辑矩阵这一行是全网最容易被抄错的点如果写成 all(sub(:))对角线上的 1 会把不是团的节点组合放进来因为无自环矩阵对角线本来就是 0判断结果会失真。主函数里的团图构建用 ismember 统计两个 k-团的重叠节点数复杂度是 O(nc^2*k^2)nc 是团的数量。这个双重循环在 k3、团数上万时会明显卡顿真实工程里可以先把 cliques 每行排序再按字典序哈希求交集能快一个数量级。但我建议第一步先跑通正确性性能优化放在后面否则你根本不知道是算法慢还是数据有问题。参数方面k 是唯一必须调的核心参数。k3 是默认起跑点适合大多数社交网络k4 适合网络密度较高、想把小团块过滤掉的场景k5 以上只适用于稠密网络或者你只想留下强绑定的铁板社团。小世界网络和稀疏网络用 k5 经常直接返回空这不是代码坏了是网络里根本没有 5-团下一章会说怎么在调参之前提前确认这件事。3. 跑通 CPM.zip 的最小流程数据准备、运行与可视化3.1 拿到 CPM.zip 先看这几样东西先看 readme 和主函数入口。一般源码包里会有一个主脚本、几个函数文件、一两个示例数据.mat 或 .txt 的边表。我拿到任何 MATLAB 代码包第一件事是打开主脚本按顺序念一遍它在干什么读数据、建矩阵、调算法、画图。很多 CPM.zip 里的代码有版本兼容问题比如用了 R2016b 才支持的 graph() 对象或者用到了并行工具箱这些在旧版 MATLAB 上会直接报错。装好 MATLAB 本体之后2020 之后的版本都行低版本要注意 nchoosek 在大组合数下会卡先确认路径里没有别的同名文件。MATLAB 的搜索路径规则是“谁靠前听谁的”如果你以前装过另一个 cpm_clustering.m新代码包怎么调都是旧函数在跑。常见解决办法是在代码包根目录右键 Set Path把当前文件夹加到路径最前或者干脆用 run 直接运行主脚本。3.2 把边表转成邻接矩阵最稳的输入姿势绝大多数公开数据给的是边表两列分别是边的两个端点。转换成邻接矩阵最直接的方法就是循环赋值% edge_list : nEdge×2 矩阵每一行是一条边 n max(edge_list(:)); A zeros(n, n); for i 1:size(edge_list, 1) u edge_list(i, 1); v edge_list(i, 2); A(u, v) 1; A(v, u) 1; end A(logical(eye(n))) 0; % 去掉可能存在的自环 A max(A, A); % 再保险一次的无向化把这段循环封装成一个 build_adjacency(edge_list) 函数主脚本里调用一次就行。循环赋值在几万条边内是可接受的超过十万条建议直接用 sparse 矩阵构造再转 full否则内存占用会很难看。这里最关键的是 nmax(edge_list(:)) 这一句它决定了矩阵尺寸如果节点编号不连续比如有 1 和 1000 却没有 2~999矩阵会变成 1000×1000 的稀疏大块跑起来会平白多出一堆空行。遇到这种数据先把节点编号重映射成 1~N 的连续整数否则后续可视化时节点标签会非常难看。3.3 跑最小例子Zachary 空手道俱乐部我一般用经典的 Zachary 空手道俱乐部网络做过烟测试34 个节点、78 条边任何社团算法论文里都有它的结果。等代码在你机器上跑通这个例子再上真实数据。整个流程只需要四步读数据、构图、调 CPM、看输出。假设你在当前路径下跑共用一个工作区% 以 Zachary 网络为例边表已经放在变量 edge_list 里 A build_adjacency(edge_list); % 用上面那段循环封装好的函数 k 3; communities cpm_clustering(A, k); % 打印每个社团的编号与规模 for i 1:numel(communities) c communities{i}; fprintf(社团 %d节点 [%s]规模 %d\n, i, mat2str(c), numel(c)); end这段运行结束后你应该看到四到六个社团其中有几个节点会出现在多个社团里这就是重叠社团的标志。如果输出里只有一个包含全部 34 个节点的大社团或者一个社团都没有先别急着怀疑算法多半是前面“去自环和无向化”两步没做干净或者 k 值选得和网络密度不匹配。注意fprintf 里的 mat2str 只是打印方便不要拿它当后续分析的输入。社团结果要用 cell 结构保存后面算模块度、做可视化都要靠它。3.4 可视化把社团画出来才算真跑通算法跑完是一堆编号不画图你永远不知道自己改的参数到底干了什么。MATLAB 的 graph 对象配合 plot 是成本最低的可视化方式G graph(A); figure; p plot(G, Layout, force); % 给每个节点上色优先按第一个所属社团上色 node_color zeros(n, 1); for c 1:numel(communities) node_color(communities{c}) node_color(communities{c}) c; % 重叠节点颜色会求和 end p.NodeCData node_color; colormap(lines(max(1, max(node_color)))); colorbar;这里的 node_color 用“所属社团编号累加”来处理重叠节点。多数软件的做法是重叠节点最后落在哪个社团就显示哪个颜色数据会被覆盖累加之后重叠节点会变成一个混合色扫一眼就能看出哪些节点横跨多个社团。如果觉得颜色太乱也可以单独把每个社团用 subgraph(G, communities{c}) 分开展示一张四宫格图比一个乱糟糟的大图有用得多。画图是一个很容易耗时间的地方——力导向布局在几百个节点的网络里每次拖拽都重算低配机器能把 MATLAB 卡成“无响应”。我的习惯是画图前先固定坐标p.XData 和 p.YData 在第一次渲染后立即复制一份之后所有子图都复用同一组坐标这样社团图和原图之间节点位置能对上对比才有意义。4. CPM 代码的 5 个常见翻车点排查矩阵、参数、内存与乱码CPM 的坑不像其他算法那样集中在“参数不收敛”它更多是工程问题。下面这五条是我把这类源码从头到尾跑过一遍之后最典型的血泪经验按出现频率排序每一条都按“现象 → 原因 → 解决”来写方便你直接对照自己的报错排查。4.1 结果漂移矩阵不对称社团每次都不一样现象同一份数据跑两次社团个数和成员都变而且往往伴随报错“Matrix must be symmetric”。原因输入的边表只写了一方向的边或者数据本身是有向网络但构造邻接矩阵时只赋了单侧值。CPM 在判断“两两相连”时会读到 A(i,j)1 而 A(j,i)0团枚举在不同遍历顺序下得出不同结论结果自然漂移。解决在调用算法前强制无向化A max(A, A)。这一行能在绝大多数情况下根治问题。如果数据带权重注意 max 会取大值比如 A(i,j)0.2、A(j,i)0.8 会变成 0.8。这在语义上是合理的CPM 判断连接只看“有没有”权重归一化放在转二值之前做更干净。4.2 k 一调大就空网络里根本没有那么多 k-团现象k3 时能跑出一堆社团改成 k4 后 communities 变空或者只剩一个由全部节点组成的大团。原因稀疏网络里 4-团本来就少。一个节点平均度只有 4 的网络找 4-团几乎等于大海捞针而 k3 时每个三角形都是一个团数量级完全不同。这和个人期望无关纯粹是网络密度决定的。解决调参数前先量化网络里各个大小的 k-团数量再决定用哪个 k。最简单的方法是写一个循环统计 cliques 的行数for k 2:5 C cpm_clustering(A, k); fprintf(k%d 时社团数%d\n, k, numel(C)); end如果 k4 时返回空不要硬调 k先去提高网络密度比如放宽边权阈值、合并弱边或者接受 k3 的结果。k 值的选取本质上是在“社团粒度”和“结果可靠性”之间做权衡没有玄学可碰看统计数字说话。4.3 内存溢出或卡死团枚举是组合爆炸重灾区现象几百个节点的网络k3 时直接卡死或者报 Out of Memory。原因find_all_cliques 里的 nchoosek 会枚举当前节点邻居的所有 k-1 组合。稠密网络里一个节点有 30 个邻居nchoosek(30,2)435 个组合还撑得住但 500 个节点全连在一起时3-团的数量是 C(500,3)≈2070 万纯枚举直接爆炸。这是 CPM 本身的计算复杂度决定的NP 完全不是开玩笑。解决三条路。第一把网络稀疏化再跑A(A 阈值) 0第二限制只搜索关心的局部子图比如按度排序只取大度节点为核心的子网络第三换用 Bron-Kerbosch 回溯实现它能剪掉大量不可能成团的节点组合。对大多数真实网络来说先用阈值过滤弱边是最有效的后悔药——弱边本来就不该参与社团凝聚。4.4 画图时重叠节点被覆盖看着像少了一堆节点现象社团图画出来某些节点明明在多个社团里视觉上却只显示最后被上色的那块颜色放大后才发现是后面的节点把前面的盖住了。原因MATLAB 的 plot 按绘制顺序渲染后画的点压先画的点。节点坐标完全重合时你只能看到最后一个社团的涂色。解决给重叠节点加一个很小的随机偏移或者把重叠节点单独画成实心大圆点放在所有社团之上。代码上可以维护一个 membership_count 数组先画普通节点最后用 hold on 把重叠节点重新 scatter 一遍顺便把属于几个社团的数字标在旁边。这种显示方式比一味追求“全图颜色不重”更有信息量。% 重叠节点单独高亮统计每个节点的社团归属数 cnt zeros(n, 1); for c 1:numel(communities) cnt(communities{c}) cnt(communities{c}) 1; end hold on; ov find(cnt 1); scatter(p.XData(ov), p.YData(ov), 100, r, filled); text(p.XData(ov), p.YData(ov), string(cnt(ov)), Color, w);4.5 中文注释乱码MATLAB 2023b 里的普遍现象现象打开 CPM.zip 里的 .m 文件中文注释全变成乱码有些甚至导致编辑器警告和脚本报错。原因代码文件是 GBK/ANSI 编码保存的而新版本 MATLAB2023b 及之后默认按 UTF-8 读取两边编码不一致中文字节被强行按 UTF-8 解释就成了乱码。这是典型的“代码本身没错、编辑器解码错了”的案例。解决MATLAB 编辑器里用“打开”对话框在编码下拉框选“GBK”重开或者用记事本打开 .m 文件另存为 UTF-8 后再用 MATLAB 打开。如果整个项目里中文注释很多建议写代码时统一用英文注释或者统一全工程 UTF-8 编码彻底根除这类问题不要每次换电脑都解码一次。提示判断乱码是编码问题而不是文件损坏可以看乱码是不是规律性的“锟斤拷”“鐢”这类固定字符组合。如果是直接按上面的方法重开即可如果乱码里混着随机汉字才需要怀疑文件本身被截断。5. 把 CPM 调出效果参数扫描、合成基准与模块度评估5.1 参数扫描k 和渗透阈值到底怎么选CPM 在无权网络里只有 k 一个主参数在带权网络里还有一个渗透阈值 μ有些实现写 w 或 threshold。μ 的语义是“边权重低于阈值就算不存在”跑之前先把矩阵二值化A_th zeros(size(A)); A_th(A mu) 1; % 高于阈值的边保留低于阈值的边丢弃 communities cpm_clustering(A_th, k);μ 的取值直接改变网络密度。μ 调高网络变疏k-团减少社团变少μ 调低网络变密小团容易串成一个大团社团变大。我在做带权社交网络时习惯的做法是把权重画一个直方图找到明显的断档处作为 μ 候选值然后跑一个二维扫描k_range 3:4; mu_range 0.1:0.1:0.9; for k k_range for mu mu_range A_bin double(A mu); C cpm_clustering(A_bin, k); fprintf(k%d mu%.1f #comm%d\n, k, mu, numel(C)); end end这段扫描不是让你拍脑袋挑一个好看的组合而是看社团数随参数的变化曲线正常网络里会有一段“平台期”社团数基本稳定越过某个临界点后会骤变。落在平台期里的参数组合才是可信的参数那些一碰就抖的区域往往意味着网络结构本身太弱无论怎么调都是噪声。这里还要多说一句别把 CPM 当成 Louvain 的替代品。两者适用场景完全不同——Louvain 在大规模网络上跑得快、输出互斥划分CPM 告诉你哪些节点在社团边界上游走。选型不是比谁更高级而是看业务要不要重叠信息。5.2 用合成网络验证SBM 生成与重叠度粗筛真实网络没有标准答案验证算法的唯一可靠方式是用合成网络——你自己知道社团归属然后看 CPM 能不能找回来。最简单的生成模型是随机块模型 SBM先把 N 个节点分进几个社团社团内的边概率设高一些社团间设低一些。function [A, true_labels] gen_sbm(n, num_comm, p_in, p_out) % 生成带社团结构的随机图true_labels 是标准答案 true_labels randi(num_comm, n, 1); A zeros(n, n); for i 1:n for j i1:n if true_labels(i) true_labels(j) p p_in; else p p_out; end if rand p A(i, j) 1; A(j, i) 1; end end end end调用时取 p_in0.3、p_out0.02这会生成一个社团结构明显的网络。跑完 CPM 后把“预测社团”和“真实社团”做一个最大重叠比例的粗筛function score overlap_coverage(true_labels, communities) % 每个真实社团与预测社团的最大重合比例取平均 u unique(true_labels); s 0; for i 1:numel(u) mask (true_labels u(i)); best 0; for c 1:numel(communities) inter sum(mask(communities{c})); best max(best, inter / sum(mask)); end s s best; end score s / numel(u); end这段代码比直接看 Accuracy 更接近“重叠社团”的语义它允许一个真实社团被多个预测社团覆盖只要每个真实社团都能被某个预测社团完整覆盖得分就高。分数达到 0.7 以上说明 CPM 在这个参数下找回了大部分结构低于 0.3 就要回头检查参数或网络密度了。正式的科研流程建议用 NMI 或 ARI不过作为工程验证这个粗筛指标足够用。5.3 扩展模块度 EQ唯一适合 CPM 的内部评估指标合成网络能验证“找回能力”但真实网络没有标准答案。这时候需要一个内部评估指标衡量划分本身好不好。经典 Newman 模块度 Q 假设每个节点只属于一个社团CPM 输出重叠社团直接套用会严重低估那些横跨社团的节点。扩展模块度 EQ 是专门处理重叠的修正版公式里多了一个 O_i 归一化项O_i 是节点 i 所属的社团个数function eq calc_eq(A, communities) % EQ重叠社团版的模块度值域大约在 0~1越大说明社团结构越明显 n size(A, 1); m sum(A(:)) / 2; deg sum(A, 2); O zeros(n, 1); for c 1:numel(communities) O(communities{c}) O(communities{c}) 1; end eq 0; for c 1:numel(communities) nodes communities{c}; for i nodes for j nodes if i j, continue; end if A(i, j) 0 eq eq (1 - deg(i) * deg(j) / (2 * m)) / (O(i) * O(j)); end end end end eq eq / (2 * m); endEQ 的取值经验真实网络里一般落在 0.2~0.6越高说明划分与网络结构越吻合。对比不同 k 的 CPM 结果时EQ 是比社团数更靠谱的选参依据——k3 和 k4 都能跑出结果就用 EQ 更高的那个。不过 EQ 也有它自己的毛病它偏爱“大而全”的社团因为大社团内部的边贡献的累加项更多。所以我自己的习惯是 EQ 只用来横向对比同一个网络的不同参数绝不在不同网络之间比较谁的 EQ 更高那是没有意义的。6. 一个能验证 CPM 结果的完整脚本重叠社团的评估与我的使用习惯完整的验证流程不是一个函数能搞定的至少应该是“生成或读取网络 → 跑 CPM → 画图 → 算 EQ → 和基准方法对比”五步。最后给一个短脚本模板把前文的所有片段串起来你拿到 CPM.zip 之后可以直接往这个骨架里填数据。% 1. 数据准备 A build_adjacency(edge_list); % 2. 跑 CPMk 取 3 起步 C cpm_clustering(A, 3); % 3. EQ 评估 eq calc_eq(A, C); fprintf(k3 EQ%.3f社团数%d\n, eq, numel(C)); % 4. 和经典互斥划分算法做对比验证重叠信息是否带来额外价值 % 这里用你手头任意一个 louvain 实现占位函数名按实际调整 if exist(louvain_comm, file) [G, Q] louvain_comm(A); fprintf(Louvain Q%.3f社团数%d\n, Q, max(G)); end这个脚本的意义不在于做了多高级的事而在于把“跑出来”和“跑对了”分开看。CPM 的社团数会因人而异地“看起来合理”EQ 和基准方法才是客观参照。把它当流水线一样每次调数据、调参数都走一遍而不是跑出来看一眼就完。我的个人习惯是永远先跑 k3 的基准结果把它当作整个流程的冒烟测试然后做参数扫描选平台期参数最后用合成网络做一次“找回能力”验证。这套流程走完才敢把结果交给下游业务使用。重叠社团这件事最怕的就是只看社团数就声称发现了结构——那是最容易自欺欺人的一刻。希望上面这些能帮你把 CPM.zip 里的代码真正用起来也希望你在拿到下一个源码包时能先问一句“它到底在找什么”再动手改参数。希望帮到你。本文还有配套的精品资源点击获取