简介基于Java实现的SCAN社团发现算法源码包面向网络科学、图挖掘方向的学习者与研究者用于复现和验证结构聚类算法。SCAN通过结构相似度识别社团、枢纽节点与离群点是社交网络、引文网络等场景中常用的聚类方法。包内包含完整的Java工程文件约27个java源码文件涵盖数据加载、聚类执行、结果保存与评价等模块同时提供多个经典公开数据集如空手道俱乐部、美国大学橄榄球赛、政治书网络等数据以边列表pairs和真实类别标签txt形式组织方便直接运行并对比社区划分效果。压缩包共67个文件总大小仅44KB结构紧凑且便于本地快速测试。已有551人浏览/学习适合正在研读SIGKDD 2007原论文或需要动手复现算法的读者参考。 做图数据分析这些年社团发现一直是我绕不开的环节。SCAN社团发现算法全称 Structural Clustering Algorithm for Networks是我在业务场景里用得最多的一类“找抱团结构”的算法。它名字里带SCAN但搜资料的时候经常撞到 HP Print and Scan Doctor、Modbus Scan、Oracle RAC SCAN IP 这些同名关键词第一次搜的时候我还真点错过。这个算法能做什么简单说它能从一张网络里划出若干联系紧密的社团顺带把那些横跨社团的 hub 节点和哪都不靠的离群点识别出来。适合做社交网络群体发现、金融异常团伙识别、生物网络模块划分的同学参考也是理解结构聚类一个很好的起点。1. SCAN算法到底是什么一个连离群点都照顾到的社团发现算法1.1 基于“结构相似度”的核心思想大多数聚类算法要么看节点属性要么看节点之间的最短路径SCAN完全换了个思路它看的是两个节点“身边熟人重叠得有多厉害”。如果两个人共同认识的人特别多哪怕他们没有直接业务往来也很可能属于同一个圈子。这个直觉翻译成图论语言就是结构相似度两个节点的邻居集合重叠程度越高越可能是强关联关系。SCAN 把每个节点的邻居集合定义为包含它自己的闭邻域然后计算相似度σ(u, v) |N(u) ∩ N(v)| / √( |N(u)| × |N(v)| )这里的 N(u) 是 u 自身加上所有与 u 相邻的节点。很多初学者第一次实现时会省略自身节点结果发现任何一条边两端的节点相似度都变成了 0因为一条边的两个端点除了彼此之外共同邻居很可能本来就是空的。包含自身之后一条边的两个端点至少会因为“u 在 N(v) 里v 也在 N(u) 里”而得到一个大于 0 的结构相似度这样才能往下做。这个相似度本质上就是余弦相似度的一种变体只不过向量空间换成了邻接空间。分子是共同邻居数分母用两个节点的邻域规模做归一化。这样设计的好处是天然考虑了节点度的影响一个度非常高的“明星节点”和一个度很低的普通节点哪怕共同邻居有好几个归一化之后相似度也会被压下来不会被误判为一个高凝聚力的团体核心。换句话讲SCAN 天然对“泛连接型”节点不友好而这恰恰是社交网络中识别真实小团体所需要的。当两个节点之间的结构相似度不低于一个阈值 epsilon 时就称它们为“强连接”。社团就是由一批强连接关系编织起来的节点集合团体的边界就是强连接关系断裂的地方。这个说法非常直觉化也非常容易向非技术同事解释。1.2 相比 Louvain、标签传播SCAN 赢在哪里很多人做社团发现时第一反应是用 Louvain 或者标签传播因为它们在几百张图上跑得快。但我在实际项目里经常被问到同一个问题这些算法把图分完块之后你能不能告诉我哪些节点是“中间人”哪些节点是“孤狼”Louvain 和标签传播一般给不出这种答案。Louvain 基于模块度优化目标是让划分后的模块内部连边尽量密集外部连边尽量稀疏。它在超大图上速度极快结果也稳定但它很容易把规模很小的但结构很紧的社团吞并进一个大块里而且每个节点都必须属于某个社团离群点无处安放。标签传播的思路更简单每个节点随机采纳邻居中最多的标签迭代几次后自然收敛成若干块。速度最快但随机性很强跑两次可能得到两个完全不同的划分而且结果几乎没办法解释“为什么这个节点在这个社区”。SCAN 的优势在于它同时给出四类信息核心节点、社团、hub 节点、离群点。核心节点是社团的骨架hub 节点是连接多个社团的“桥梁”离群点是游离在整个网络之外的数据点。在反欺诈场景里hub 往往是团伙之间资金中转的关键账户离群点则是刷单或者孤立异常样本这些信息比单纯一个社团编号有价值得多。下表是我在实际选型时常用的对比算法核心优势主要短板适合场景Louvain快、适合大规模图会吞并小社团不标记离群点初步探索、超大图标签传播实现简单、速度极快结果不稳定、可解释性弱实时性要求极高的场景GN能体现层次结构时间复杂度高不太适合大图小规模精确分析SCAN结构可解释、能识别hub和离群点对参数敏感需要调参需要业务解释和异常识别的场景所以如果你的目标只是“把图分成几块看个大概”Louvain 够了如果你需要给业务方讲清楚“这块用户为什么是一个团伙谁是核心谁在中间做传导谁的关联度非常弱”SCAN 会友好得多。2. 两个参数背后的逻辑epsilon 和 mu 怎么理解、怎么调2.1 epsilon结构相似度阈值SCAN 只有两个核心参数epsilon 和 mu。先说 epsilon它是判定“强连接”的门槛。比如 epsilon 设为 0.7意味着两个节点之间必须达到至少 70% 的归一化共同邻居比例才能被算作强连接。这个值越高社团内部成员之间的共同熟人比例要求就越严格社团往往更小、更紧凑这个值越低强连接边越多社团会逐渐向外蔓延最后可能出现一大片所有节点连成一团的局面。那 epsilon 到底设多少合适经验上稀疏社交网络里我通常从 0.5 开始试稠密网络比如设备互联、交易网络从 0.7 开始试。阈值的含义跟图的平均度密切相关。平均度低的图节点之间的共同邻居本身就少再设一个很高的 epsilon几乎所有边都达不到强连接标准最后每个核心节点只能带十几个孤立的小碎片平均度很高的图两个节点随便一点就能有大量共同邻居epsilon 太低又会让社区之间彻底糊在一起。一个非常实用的调参方法是把 epsilon 当扫描控制变量从 0.3 到 0.9 每一步加 0.05记录每次跑出来的社团数量。你会发现曲线往往先缓慢下降然后出现一个明显的拐点之后社团数量迅速崩坏或者急剧碎片化。这个拐点附近的 epsilon 就是比较合理的起步值。不要一上来就按论文里常见的 0.7 套论文用的图跟你的业务图大概率不在一张尺度上。2.2 mu最少强连接数量mu 决定了一个节点要成为“核心节点”的门槛。核心节点的定义并不复杂在它的直接邻居里与它形成强连接的邻居数量必须不少于 mu。所以 mu 不是全局平均度也不是总邻居数它衡量的是“一个节点周围到底有多少个真正与自己高度同频的节点”。mu 为什么通常设成 2因为在社交网络里两个强连接只能说明你和某个人关系很近一个人要成为社团核心至少要有两个关系紧密的邻居才能形成一个稳定的小骨架。如果 mu 设成 1几乎所有一条边连接到的节点都可能成为核心社团会膨胀得非常厉害如果 mu 设得太大比如 10只有那些连接了大量强邻居的节点才能当核心很多真实存在的小社团会被直接忽略掉。在调整 mu 时我习惯先看一眼图的度分布。如果大部分节点度集中在 2 到 5mu 设 2 到 3 是合理的如果这是一个高度密集的交易网络节点度普遍超过 50mu 可以相应提高到 5 以上否则连核心节点都找不出几个。mu 的取值和 epsilon 是联动的调参时千万不要觉得“我先固定一个再调另一个”就万事大吉。2.3 参数联动别单独看一个值很多新手纠结 epsilon 和 mu 哪个更重要其实它们像是一个“阀门”的两块挡板。epsilon 控制单条边能不能成为强连接mu 控制节点能不能利用这些强连接成为核心。参数组合效果epsilon 高、mu 低强连接不多但每个核心只要少数强邻居就能成立结果会出现大量小碎团epsilon 低、mu 高强连接很多但核心门槛很高社团容易合并成巨型块两个都低强连接多且核心容易成立最后大概率一个大团两个都高强连接少且核心门槛高大量节点变离群点结果碎片化严重实际项目中我一般先用一组相对温和的参数epsilon 0.6、mu 2跑通全流程然后再根据业务对“碎片数量”的容忍度做细调。如果业务方不希望把用户切得太碎就适当提高 epsilon、降低 mu如果希望更严格地识别异常点就反过来降低 epsilon、提高 mu。参数没有标准答案只有适合业务场景的答案。3. 一个能跑起来的 SCAN 实现从伪代码到 Python3.1 核心步骤拆解SCAN 的完整实现不复杂主要分成四步。第一步遍历图上的每一条边计算两端的结构相似度凡是相似度不低于 epsilon 的边都标记为强连接边。第二步对每个节点统计它与邻居之间的强连接边数量数值不小于 mu 的节点记为核心节点。第三步把所有通过强连接边彼此相连的核心节点合并成“社团骨架”这一步用并查集最方便。第四步把非核心节点挂到相邻核心节点所在社团上如果一个非核心节点能通过强连接边连到多个不同社团的核心节点它就是一个 hub 节点不需要强行塞进某个社团。这个流程看起来简单但实现时有两个细节容易出错。第一个是强连接边判定时一定要用闭邻域计算相似度也就是把节点自身算进邻居集合否则全图相似度可能直接变成零。第二个是并查集合并时只能合并核心节点不要顺手把非核心节点也并进去否则后续 hub 和离群点的判断就全乱套了。3.2 用 NetworkX 手写一个极简版直接调 NetworkX 就能跑一组社区发现实验。下面这段代码是我在空手道俱乐部图上常用来做演示的版本也是我日常理解 SCAN 的小工具箱之一。先装一下依赖pip install networkx然后实现算法import networkx as nx import math def similarity(G, u, v): nu set(G.neighbors(u)) | {u} nv set(G.neighbors(v)) | {v} common len(nu nv) return common / math.sqrt(len(nu) * len(nv)) def scan(G, epsilon0.6, mu2): strong set() for u, v in G.edges(): if similarity(G, u, v) epsilon: strong.add((u, v) if u v else (v, u)) core set() for node in G.nodes(): cnt 0 for nb in G.neighbors(node): if (node, nb) in strong or (nb, node) in strong: cnt 1 if cnt mu: core.add(node) parent {node: node for node in core} 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 u, v in strong: if u in core and v in core: union(u, v) clusters {} for node in core: root find(node) clusters.setdefault(root, set()).add(node) for u, v in strong: for core_node in (u, v): other v if core_node u else u if other in core: continue target_root find(core_node) clusters.setdefault(target_root, set()).add(other) return clusters, core, strong这段代码里strong是强连接边的集合core是核心节点集合clusters是一个“社团根节点 - 节点集合”的字典。我在遍历强连接边时做了一个很刻意的处理一个非核心节点只要连到某个社团里的核心节点就会被加入该社团如果它同时连到两个不同社团的核心节点它就会同时出现在两个集合里。这在业务上就是我们需要的 hub 信息只是在最终展示时要注意去重说明。你可以用自带数据集跑一下G nx.karate_club_graph() clusters, core, strong scan(G, epsilon0.6, mu2) print(核心节点数量:, len(core)) for rid, nodes in clusters.items(): print(社团:, sorted(nodes))空手道俱乐部图是一个经典的社交网络节点是俱乐部成员边是成员之间在训练之外的交情。跑出来的社团通常不是标准答案里那两个大块而是若干更小的结构密集区域同时还会出现少量跨社团的中间节点。这个实验结果恰恰说明了 SCAN 的定位它不追求“整体模块度最高”它更关心局部结构关系是否足够紧密。3.3 输出结果怎么解读得到clusters字典之后建议不要只看数字把结果可视化出来。NetworkX 提供spring_layout你可以把核心节点画成深色、非核心节点画成浅色再用不同颜色区分社团。如果某几个节点反复出现在多个社团里它们在图上往往就是连接不同密集区域的桥梁这些节点在反欺诈场景里通常是最值得重点建模的对象。我还会额外统计“没有归属任何社团的节点”它们就是离群点。如果离群点数量远超预期不要急着怀疑图有问题先回去看 epsilon 是不是定得过高。离群点比例在 5% 到 20% 都是比较常见的如果超过 50%说明参数和图的密度极度不匹配或者这张图本来就不适合用 SCAN 建模。4. 我在真实图上跑 SCAN 踩过的坑4.1 结果碎片化或者过度合并第一次在真实业务图上跑 SCAN 时我直接把 epsilon 设成了 0.7mu 设成 2结果非常“惊艳”——全图 20 多万个节点输出了一万多个平均只有三四人的小社团大量节点都是离群点。问题出在业务图的平均度太高节点之间共同邻居比例普遍很低0.7 的阈值几乎把强连接边全部切断了。后来我把 epsilon 逐步降到了 0.45社团数量才恢复正常。所以第一建议是永远不要从论文值出发而是先统计图上所有边的相似度分布。你甚至可以写一行代码把所有边的相似度排序看看 25%、50%、75% 分位点分别在哪里然后选一个 60 到 80 分位之间的值作为初始 epsilon。这个操作比反复试参要高效得多。另一个常见问题是过度合并。有些图里存在几个高度互联的“核心圈子”它们之间仅仅通过一两条强连接边搭在一起结果整个图被并成了一个超级大团。这时候需要提高 epsilon把那些搭桥的强连接边切断让边界重新显现。要记住SCAN 不是越“准确”越好而是越接近业务直觉越好。4.2 性能优化与实现细节SCAN 的原始复杂度不算低因为要计算每条边的结构相似度整体开销可以近似看成 O(m × 平均度)。在小图和中等规模图上完全没问题但到了百万边以上朴素实现就会开始卡。我常用的优化手段有这么几个。第一只对边做相似度计算不要对全节点对做计算。第二算共同邻居时选邻居集合更小的那个节点去遍历每个邻居在另一个集合里做一次哈希查找而不是两个集合交叉全扫描。第三核心节点判断前先快速过滤如果一个节点的度本身就小于 mu它必然不是核心节点不用参与后续并查集计算。第四并查集一定要做路径压缩否则核心节点之间的合并会退化成很长的链社团一多性能就崩。如果图的规模再上一个量级我会考虑用 pSCAN 或 SCAN 这类优化变体。它们的核心思想是预先筛掉大量不可能成为核心的节点再通过倒排索引加速相似度计算能把速度提升一个数量级。不过在大多数业务场景里我自己写一个基于 NetworkX 的版本已经足够做原型验证了。4.3 别把 SCAN 和同名工具搞混搜索避坑指南这个我必须单独写一节。SCAN 这个名字在互联网上实在太多重名了。我之前搜资料时连续看到 HP Print and Scan Doctor、Modbus Scan、Oracle RAC SCAN IP一度以为自己记错了算法名。HP Print and Scan Doctor 是惠普官方的一个打印和扫描故障排查工具解决驱动识别、扫描仪连接这类问题跟社团发现没有任何关系。Modbus Scan 是工业自动化领域常用的 Modbus 从站扫描工具用来遍历设备地址或寄存器。如果你遇到 Modbus TCP 能 ping 通但 mod scan 不通的问题一般先去查 TCP 502 端口是否被防火墙拦截、从站设备有没有开启 Modbus TCP 服务、Unit ID 配置是不是正确这些排查方向和图聚类算法八竿子打不着。Oracle RAC 里的 SCAN IP 全称 Single Client Access Name是集群对外提供的一个统一接入域名跟 VIP 的区别是VIP 是每个节点各自漂移的地址SCAN IP 是整个集群层面的单一入口用于客户端负载均衡和故障透明切换这里的 SCAN 只是名字缩写。以后再搜 SCAN 算法时看到这些词直接跳过就行别让它们干扰你查资料。5. 哪些场景适合用 SCAN应用与扩展方向5.1 最值得用的场景SCAN 最值得用的场景并不是“随便分个组”而是社区结构需要有明确业务解释的场景。社交网络中做用户群体画像可以用 SCAN 找到真正的“兴趣同好群”同时通过 hub 节点发现跨群传播者这类节点在运营里往往就是KOL。反欺诈场景里SCAN 的离群点往往是异常交易、刷单账户hub 节点可能是资金归集账户这两个角色比社团本身更有建模价值。推荐系统里做用户冷启动分组时SCAN 能把强关联用户圈成一个稳定的小群体再基于群体行为做物品推荐比只看单用户历史要稳得多。生物网络里也常有人用 SCAN 做蛋白质功能模块识别。蛋白质相互作用网络中功能模块往往表现为结构紧密的团簇SCAN 的强连接定义和生物模块的共现特性天然匹配。总的来说凡是“不仅要分块还要解释边界和异常”的场景都可以优先考虑 SCAN。5.2 从 SCAN 引申到结构聚类家族SCAN 本身只是一个起点。围绕它衍生出的优化版本很多比如 pSCAN 通过基于度的剪枝减少无效计算SCAN 用更高效的核心节点查找方式处理大规模图。如果想把 SCAN 用到动态图上还可以在每次增量更新时只重算受影响节点的局部相似度避免全图重跑。更进一步的思路是替换相似度定义。SCAN 的相似度本质是共同邻居的余弦归一化你也可以换成 Jaccard 系数、资源分配指标或者 Adamic-Adar 指标。每一种相似度对“节点度”的惩罚方式不同换掉之后社团形状会有明显变化。到这一步SCAN 就不再是一个固定算法而是一套“结构相似度 核心扩展 异常点识别”的方法论。我个人在实际操作中的体会是SCAN 的参数敏感既是缺点也是优点。缺点是你必须认真调参不能无脑套默认值优点是当你把 epsilon 和 mu 调到与业务直觉吻合时它的结果解释性远超很多黑盒社区发现算法。最后再分享一个小技巧当你只关心最大连通社团的时候可以先把核心节点筛出来然后只看核心节点之间的连通分量这会比完整跑一遍 SCAN 快很多而且基本不影响最大社团的发现。本文还有配套的精品资源点击获取 
长河君 · 2026/9/2 4:38:35 · 阅读 1.2k SCAN社团发现算法：原理、参数与实战
简介基于Java实现的SCAN社团发现算法源码包面向网络科学、图挖掘方向的学习者与研究者用于复现和验证结构聚类算法。SCAN通过结构相似度识别社团、枢纽节点与离群点是社交网络、引文网络等场景中常用的聚类方法。包内包含完整的Java工程文件约27个java源码文件涵盖数据加载、聚类执行、结果保存与评价等模块同时提供多个经典公开数据集如空手道俱乐部、美国大学橄榄球赛、政治书网络等数据以边列表pairs和真实类别标签txt形式组织方便直接运行并对比社区划分效果。压缩包共67个文件总大小仅44KB结构紧凑且便于本地快速测试。已有551人浏览/学习适合正在研读SIGKDD 2007原论文或需要动手复现算法的读者参考。 做图数据分析这些年社团发现一直是我绕不开的环节。SCAN社团发现算法全称 Structural Clustering Algorithm for Networks是我在业务场景里用得最多的一类“找抱团结构”的算法。它名字里带SCAN但搜资料的时候经常撞到 HP Print and Scan Doctor、Modbus Scan、Oracle RAC SCAN IP 这些同名关键词第一次搜的时候我还真点错过。这个算法能做什么简单说它能从一张网络里划出若干联系紧密的社团顺带把那些横跨社团的 hub 节点和哪都不靠的离群点识别出来。适合做社交网络群体发现、金融异常团伙识别、生物网络模块划分的同学参考也是理解结构聚类一个很好的起点。1. SCAN算法到底是什么一个连离群点都照顾到的社团发现算法1.1 基于“结构相似度”的核心思想大多数聚类算法要么看节点属性要么看节点之间的最短路径SCAN完全换了个思路它看的是两个节点“身边熟人重叠得有多厉害”。如果两个人共同认识的人特别多哪怕他们没有直接业务往来也很可能属于同一个圈子。这个直觉翻译成图论语言就是结构相似度两个节点的邻居集合重叠程度越高越可能是强关联关系。SCAN 把每个节点的邻居集合定义为包含它自己的闭邻域然后计算相似度σ(u, v) |N(u) ∩ N(v)| / √( |N(u)| × |N(v)| )这里的 N(u) 是 u 自身加上所有与 u 相邻的节点。很多初学者第一次实现时会省略自身节点结果发现任何一条边两端的节点相似度都变成了 0因为一条边的两个端点除了彼此之外共同邻居很可能本来就是空的。包含自身之后一条边的两个端点至少会因为“u 在 N(v) 里v 也在 N(u) 里”而得到一个大于 0 的结构相似度这样才能往下做。这个相似度本质上就是余弦相似度的一种变体只不过向量空间换成了邻接空间。分子是共同邻居数分母用两个节点的邻域规模做归一化。这样设计的好处是天然考虑了节点度的影响一个度非常高的“明星节点”和一个度很低的普通节点哪怕共同邻居有好几个归一化之后相似度也会被压下来不会被误判为一个高凝聚力的团体核心。换句话讲SCAN 天然对“泛连接型”节点不友好而这恰恰是社交网络中识别真实小团体所需要的。当两个节点之间的结构相似度不低于一个阈值 epsilon 时就称它们为“强连接”。社团就是由一批强连接关系编织起来的节点集合团体的边界就是强连接关系断裂的地方。这个说法非常直觉化也非常容易向非技术同事解释。1.2 相比 Louvain、标签传播SCAN 赢在哪里很多人做社团发现时第一反应是用 Louvain 或者标签传播因为它们在几百张图上跑得快。但我在实际项目里经常被问到同一个问题这些算法把图分完块之后你能不能告诉我哪些节点是“中间人”哪些节点是“孤狼”Louvain 和标签传播一般给不出这种答案。Louvain 基于模块度优化目标是让划分后的模块内部连边尽量密集外部连边尽量稀疏。它在超大图上速度极快结果也稳定但它很容易把规模很小的但结构很紧的社团吞并进一个大块里而且每个节点都必须属于某个社团离群点无处安放。标签传播的思路更简单每个节点随机采纳邻居中最多的标签迭代几次后自然收敛成若干块。速度最快但随机性很强跑两次可能得到两个完全不同的划分而且结果几乎没办法解释“为什么这个节点在这个社区”。SCAN 的优势在于它同时给出四类信息核心节点、社团、hub 节点、离群点。核心节点是社团的骨架hub 节点是连接多个社团的“桥梁”离群点是游离在整个网络之外的数据点。在反欺诈场景里hub 往往是团伙之间资金中转的关键账户离群点则是刷单或者孤立异常样本这些信息比单纯一个社团编号有价值得多。下表是我在实际选型时常用的对比算法核心优势主要短板适合场景Louvain快、适合大规模图会吞并小社团不标记离群点初步探索、超大图标签传播实现简单、速度极快结果不稳定、可解释性弱实时性要求极高的场景GN能体现层次结构时间复杂度高不太适合大图小规模精确分析SCAN结构可解释、能识别hub和离群点对参数敏感需要调参需要业务解释和异常识别的场景所以如果你的目标只是“把图分成几块看个大概”Louvain 够了如果你需要给业务方讲清楚“这块用户为什么是一个团伙谁是核心谁在中间做传导谁的关联度非常弱”SCAN 会友好得多。2. 两个参数背后的逻辑epsilon 和 mu 怎么理解、怎么调2.1 epsilon结构相似度阈值SCAN 只有两个核心参数epsilon 和 mu。先说 epsilon它是判定“强连接”的门槛。比如 epsilon 设为 0.7意味着两个节点之间必须达到至少 70% 的归一化共同邻居比例才能被算作强连接。这个值越高社团内部成员之间的共同熟人比例要求就越严格社团往往更小、更紧凑这个值越低强连接边越多社团会逐渐向外蔓延最后可能出现一大片所有节点连成一团的局面。那 epsilon 到底设多少合适经验上稀疏社交网络里我通常从 0.5 开始试稠密网络比如设备互联、交易网络从 0.7 开始试。阈值的含义跟图的平均度密切相关。平均度低的图节点之间的共同邻居本身就少再设一个很高的 epsilon几乎所有边都达不到强连接标准最后每个核心节点只能带十几个孤立的小碎片平均度很高的图两个节点随便一点就能有大量共同邻居epsilon 太低又会让社区之间彻底糊在一起。一个非常实用的调参方法是把 epsilon 当扫描控制变量从 0.3 到 0.9 每一步加 0.05记录每次跑出来的社团数量。你会发现曲线往往先缓慢下降然后出现一个明显的拐点之后社团数量迅速崩坏或者急剧碎片化。这个拐点附近的 epsilon 就是比较合理的起步值。不要一上来就按论文里常见的 0.7 套论文用的图跟你的业务图大概率不在一张尺度上。2.2 mu最少强连接数量mu 决定了一个节点要成为“核心节点”的门槛。核心节点的定义并不复杂在它的直接邻居里与它形成强连接的邻居数量必须不少于 mu。所以 mu 不是全局平均度也不是总邻居数它衡量的是“一个节点周围到底有多少个真正与自己高度同频的节点”。mu 为什么通常设成 2因为在社交网络里两个强连接只能说明你和某个人关系很近一个人要成为社团核心至少要有两个关系紧密的邻居才能形成一个稳定的小骨架。如果 mu 设成 1几乎所有一条边连接到的节点都可能成为核心社团会膨胀得非常厉害如果 mu 设得太大比如 10只有那些连接了大量强邻居的节点才能当核心很多真实存在的小社团会被直接忽略掉。在调整 mu 时我习惯先看一眼图的度分布。如果大部分节点度集中在 2 到 5mu 设 2 到 3 是合理的如果这是一个高度密集的交易网络节点度普遍超过 50mu 可以相应提高到 5 以上否则连核心节点都找不出几个。mu 的取值和 epsilon 是联动的调参时千万不要觉得“我先固定一个再调另一个”就万事大吉。2.3 参数联动别单独看一个值很多新手纠结 epsilon 和 mu 哪个更重要其实它们像是一个“阀门”的两块挡板。epsilon 控制单条边能不能成为强连接mu 控制节点能不能利用这些强连接成为核心。参数组合效果epsilon 高、mu 低强连接不多但每个核心只要少数强邻居就能成立结果会出现大量小碎团epsilon 低、mu 高强连接很多但核心门槛很高社团容易合并成巨型块两个都低强连接多且核心容易成立最后大概率一个大团两个都高强连接少且核心门槛高大量节点变离群点结果碎片化严重实际项目中我一般先用一组相对温和的参数epsilon 0.6、mu 2跑通全流程然后再根据业务对“碎片数量”的容忍度做细调。如果业务方不希望把用户切得太碎就适当提高 epsilon、降低 mu如果希望更严格地识别异常点就反过来降低 epsilon、提高 mu。参数没有标准答案只有适合业务场景的答案。3. 一个能跑起来的 SCAN 实现从伪代码到 Python3.1 核心步骤拆解SCAN 的完整实现不复杂主要分成四步。第一步遍历图上的每一条边计算两端的结构相似度凡是相似度不低于 epsilon 的边都标记为强连接边。第二步对每个节点统计它与邻居之间的强连接边数量数值不小于 mu 的节点记为核心节点。第三步把所有通过强连接边彼此相连的核心节点合并成“社团骨架”这一步用并查集最方便。第四步把非核心节点挂到相邻核心节点所在社团上如果一个非核心节点能通过强连接边连到多个不同社团的核心节点它就是一个 hub 节点不需要强行塞进某个社团。这个流程看起来简单但实现时有两个细节容易出错。第一个是强连接边判定时一定要用闭邻域计算相似度也就是把节点自身算进邻居集合否则全图相似度可能直接变成零。第二个是并查集合并时只能合并核心节点不要顺手把非核心节点也并进去否则后续 hub 和离群点的判断就全乱套了。3.2 用 NetworkX 手写一个极简版直接调 NetworkX 就能跑一组社区发现实验。下面这段代码是我在空手道俱乐部图上常用来做演示的版本也是我日常理解 SCAN 的小工具箱之一。先装一下依赖pip install networkx然后实现算法import networkx as nx import math def similarity(G, u, v): nu set(G.neighbors(u)) | {u} nv set(G.neighbors(v)) | {v} common len(nu nv) return common / math.sqrt(len(nu) * len(nv)) def scan(G, epsilon0.6, mu2): strong set() for u, v in G.edges(): if similarity(G, u, v) epsilon: strong.add((u, v) if u v else (v, u)) core set() for node in G.nodes(): cnt 0 for nb in G.neighbors(node): if (node, nb) in strong or (nb, node) in strong: cnt 1 if cnt mu: core.add(node) parent {node: node for node in core} 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 u, v in strong: if u in core and v in core: union(u, v) clusters {} for node in core: root find(node) clusters.setdefault(root, set()).add(node) for u, v in strong: for core_node in (u, v): other v if core_node u else u if other in core: continue target_root find(core_node) clusters.setdefault(target_root, set()).add(other) return clusters, core, strong这段代码里strong是强连接边的集合core是核心节点集合clusters是一个“社团根节点 - 节点集合”的字典。我在遍历强连接边时做了一个很刻意的处理一个非核心节点只要连到某个社团里的核心节点就会被加入该社团如果它同时连到两个不同社团的核心节点它就会同时出现在两个集合里。这在业务上就是我们需要的 hub 信息只是在最终展示时要注意去重说明。你可以用自带数据集跑一下G nx.karate_club_graph() clusters, core, strong scan(G, epsilon0.6, mu2) print(核心节点数量:, len(core)) for rid, nodes in clusters.items(): print(社团:, sorted(nodes))空手道俱乐部图是一个经典的社交网络节点是俱乐部成员边是成员之间在训练之外的交情。跑出来的社团通常不是标准答案里那两个大块而是若干更小的结构密集区域同时还会出现少量跨社团的中间节点。这个实验结果恰恰说明了 SCAN 的定位它不追求“整体模块度最高”它更关心局部结构关系是否足够紧密。3.3 输出结果怎么解读得到clusters字典之后建议不要只看数字把结果可视化出来。NetworkX 提供spring_layout你可以把核心节点画成深色、非核心节点画成浅色再用不同颜色区分社团。如果某几个节点反复出现在多个社团里它们在图上往往就是连接不同密集区域的桥梁这些节点在反欺诈场景里通常是最值得重点建模的对象。我还会额外统计“没有归属任何社团的节点”它们就是离群点。如果离群点数量远超预期不要急着怀疑图有问题先回去看 epsilon 是不是定得过高。离群点比例在 5% 到 20% 都是比较常见的如果超过 50%说明参数和图的密度极度不匹配或者这张图本来就不适合用 SCAN 建模。4. 我在真实图上跑 SCAN 踩过的坑4.1 结果碎片化或者过度合并第一次在真实业务图上跑 SCAN 时我直接把 epsilon 设成了 0.7mu 设成 2结果非常“惊艳”——全图 20 多万个节点输出了一万多个平均只有三四人的小社团大量节点都是离群点。问题出在业务图的平均度太高节点之间共同邻居比例普遍很低0.7 的阈值几乎把强连接边全部切断了。后来我把 epsilon 逐步降到了 0.45社团数量才恢复正常。所以第一建议是永远不要从论文值出发而是先统计图上所有边的相似度分布。你甚至可以写一行代码把所有边的相似度排序看看 25%、50%、75% 分位点分别在哪里然后选一个 60 到 80 分位之间的值作为初始 epsilon。这个操作比反复试参要高效得多。另一个常见问题是过度合并。有些图里存在几个高度互联的“核心圈子”它们之间仅仅通过一两条强连接边搭在一起结果整个图被并成了一个超级大团。这时候需要提高 epsilon把那些搭桥的强连接边切断让边界重新显现。要记住SCAN 不是越“准确”越好而是越接近业务直觉越好。4.2 性能优化与实现细节SCAN 的原始复杂度不算低因为要计算每条边的结构相似度整体开销可以近似看成 O(m × 平均度)。在小图和中等规模图上完全没问题但到了百万边以上朴素实现就会开始卡。我常用的优化手段有这么几个。第一只对边做相似度计算不要对全节点对做计算。第二算共同邻居时选邻居集合更小的那个节点去遍历每个邻居在另一个集合里做一次哈希查找而不是两个集合交叉全扫描。第三核心节点判断前先快速过滤如果一个节点的度本身就小于 mu它必然不是核心节点不用参与后续并查集计算。第四并查集一定要做路径压缩否则核心节点之间的合并会退化成很长的链社团一多性能就崩。如果图的规模再上一个量级我会考虑用 pSCAN 或 SCAN 这类优化变体。它们的核心思想是预先筛掉大量不可能成为核心的节点再通过倒排索引加速相似度计算能把速度提升一个数量级。不过在大多数业务场景里我自己写一个基于 NetworkX 的版本已经足够做原型验证了。4.3 别把 SCAN 和同名工具搞混搜索避坑指南这个我必须单独写一节。SCAN 这个名字在互联网上实在太多重名了。我之前搜资料时连续看到 HP Print and Scan Doctor、Modbus Scan、Oracle RAC SCAN IP一度以为自己记错了算法名。HP Print and Scan Doctor 是惠普官方的一个打印和扫描故障排查工具解决驱动识别、扫描仪连接这类问题跟社团发现没有任何关系。Modbus Scan 是工业自动化领域常用的 Modbus 从站扫描工具用来遍历设备地址或寄存器。如果你遇到 Modbus TCP 能 ping 通但 mod scan 不通的问题一般先去查 TCP 502 端口是否被防火墙拦截、从站设备有没有开启 Modbus TCP 服务、Unit ID 配置是不是正确这些排查方向和图聚类算法八竿子打不着。Oracle RAC 里的 SCAN IP 全称 Single Client Access Name是集群对外提供的一个统一接入域名跟 VIP 的区别是VIP 是每个节点各自漂移的地址SCAN IP 是整个集群层面的单一入口用于客户端负载均衡和故障透明切换这里的 SCAN 只是名字缩写。以后再搜 SCAN 算法时看到这些词直接跳过就行别让它们干扰你查资料。5. 哪些场景适合用 SCAN应用与扩展方向5.1 最值得用的场景SCAN 最值得用的场景并不是“随便分个组”而是社区结构需要有明确业务解释的场景。社交网络中做用户群体画像可以用 SCAN 找到真正的“兴趣同好群”同时通过 hub 节点发现跨群传播者这类节点在运营里往往就是KOL。反欺诈场景里SCAN 的离群点往往是异常交易、刷单账户hub 节点可能是资金归集账户这两个角色比社团本身更有建模价值。推荐系统里做用户冷启动分组时SCAN 能把强关联用户圈成一个稳定的小群体再基于群体行为做物品推荐比只看单用户历史要稳得多。生物网络里也常有人用 SCAN 做蛋白质功能模块识别。蛋白质相互作用网络中功能模块往往表现为结构紧密的团簇SCAN 的强连接定义和生物模块的共现特性天然匹配。总的来说凡是“不仅要分块还要解释边界和异常”的场景都可以优先考虑 SCAN。5.2 从 SCAN 引申到结构聚类家族SCAN 本身只是一个起点。围绕它衍生出的优化版本很多比如 pSCAN 通过基于度的剪枝减少无效计算SCAN 用更高效的核心节点查找方式处理大规模图。如果想把 SCAN 用到动态图上还可以在每次增量更新时只重算受影响节点的局部相似度避免全图重跑。更进一步的思路是替换相似度定义。SCAN 的相似度本质是共同邻居的余弦归一化你也可以换成 Jaccard 系数、资源分配指标或者 Adamic-Adar 指标。每一种相似度对“节点度”的惩罚方式不同换掉之后社团形状会有明显变化。到这一步SCAN 就不再是一个固定算法而是一套“结构相似度 核心扩展 异常点识别”的方法论。我个人在实际操作中的体会是SCAN 的参数敏感既是缺点也是优点。缺点是你必须认真调参不能无脑套默认值优点是当你把 epsilon 和 mu 调到与业务直觉吻合时它的结果解释性远超很多黑盒社区发现算法。最后再分享一个小技巧当你只关心最大连通社团的时候可以先把核心节点筛出来然后只看核心节点之间的连通分量这会比完整跑一遍 SCAN 快很多而且基本不影响最大社团的发现。本文还有配套的精品资源点击获取