企业官网建设流程全解析

简介：基于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 够了；如果你需要给业务方讲清楚“这块用户为什么是一个团伙，谁是核心，谁在中间做传导，谁的关联度非常弱”，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 到 5，mu 设 2 到 3 是合理的；如果这是一个高度密集的交易网络，节点度普遍超过 50，mu 可以相应提高到 5 以上，否则连核心节点都找不出几个。mu 的取值和 epsilon 是联动的，调参时千万不要觉得“我先固定一个再调另一个”就万事大吉。

2.3 参数联动：别单独看一个值

很多新手纠结 epsilon 和 mu 哪个更重要，其实它们像是一个“阀门”的两块挡板。epsilon 控制单条边能不能成为强连接，mu 控制节点能不能利用这些强连接成为核心。

实际项目中，我一般先用一组相对温和的参数（epsilon 0.6、mu 2）跑通全流程，然后再根据业务对“碎片数量”的容忍度做细调。如果业务方不希望把用户切得太碎，就适当提高 epsilon、降低 mu；如果希望更严格地识别异常点，就反过来降低 epsilon、提高 mu。参数没有标准答案，只有适合业务场景的答案。

3. 一个能跑起来的 SCAN 实现：从伪代码到 Python

3.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, epsilon=0.6, mu=2): 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, epsilon=0.6, mu=2) 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.7，mu 设成 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 快很多，而且基本不影响最大社团的发现。

本文还有配套的精品资源，点击获取