简介：本资源为基于Java实现的SCAN社团发现算法代码包，面向复杂网络分析、数据挖掘方向的学习者与研究者，可用于理解结构聚类算法在社区划分中的具体落地方式。包内共67个文件，以27个java源码文件为核心，涵盖SCAN、Network、Vertex、Edge、Evaluate等类，完整呈现算法主流程与评估逻辑；另有20个txt与20个pairs文件，提供zachary-karate、football2006、polbooks、college-football、KDD-toy等多组示例数据集及真实类别标签，便于直接运行验证聚类效果。压缩包整体约44KB，体量轻便，目录结构清晰，适合对照论文《SCAN: A Structural Clustering Algorithm for Networks》进行源码研读与实验复现。目前已有551人学习下载，可作为社团发现入门实践与算法对比实验的参考素材。
1. 从一次社群划分翻车说起：SCAN社团发现算法到底在算什么
去年帮某高校实验室做一份社交网络分析的技术验证，数据是 3000 多个节点的兴趣圈子关系图。我一开始图省事，直接上了标签传播，结果跑出来的社团像被狗啃过——同一个兴趣小组被切成七八块，还有几个大社团把半个图都吞了。后来换成 SCAN（Structural Clustering Algorithm for Networks），同一份数据，社团边界干净了很多，而且那些「既在这个圈子又在那个圈子」的节点被单独标了出来。这就是 SCAN 社团发现算法最核心的价值：它不强行把每个节点塞进唯一社团，而是允许枢纽节点和离群点存在。
SCAN 属于基于结构相似度的社团发现算法，2007 年由 Xu 等人提出。它的基本假设很朴素：如果两个节点共享足够多的共同邻居，它们就倾向于在同一个社团里。这个「足够多」由参数 ε（epsilon）控制，而「社团至少要有多少个节点」由 μ（mu）控制。相比模块度优化那一派（Louvain、Leiden），SCAN 不追求全局最优划分，而是从局部结构出发，天然能识别重叠社团和噪声节点。适合谁用？做社交网络分析、蛋白质相互作用网络、引文网络、风控团伙识别的从业者，尤其是当你发现数据里存在「一人混多个圈子」或者「大量孤立节点」的时候，SCAN 比硬划分算法更贴合现实。
2. 结构相似度怎么算：SCAN 的两个核心参数与判定逻辑
2.1 结构相似度的定义与直觉
SCAN 的核心公式是结构相似度：
σ(u, v) = |Γ(u) ∩ Γ(v)| / sqrt(|Γ(u)| * |Γ(v)|)其中 Γ(u) 是节点 u 的邻居集合（包含 u 自身）。这个公式本质上是余弦相似度在邻接表上的变体。分子是共同邻居数，分母是两边邻居数的几何平均，起到归一化作用。为什么要包含自身？因为如果不包含，两个直接相连但都没有其他邻居的节点相似度会是 0，这显然不合理。
我一般会这样跟团队解释：把每个节点想象成一个人，他的邻居就是他的微信好友。两个人共同好友越多，关系越铁。但光看共同好友数量不够，还得看各自好友总数——一个加了 5000 好友的人和另一个加了 50 好友的人有 30 个共同好友，跟两个都只有 60 好友的人有 30 个共同好友，亲密度完全不是一回事。分母就是在做这个修正。
2.2 ε 和 μ 的取值逻辑
ε 是相似度阈值。当 σ(u, v) ≥ ε 时，称 u 和 v 是「结构相似」的，它们之间形成一条「强连接」。ε 越大，要求共同邻居比例越高，社团越紧凑、数量越多；ε 越小，社团越松散、越大。
μ 是社团规模下限。一个节点要成为核心节点（core node），它的 ε-邻居数量必须 ≥ μ。核心节点是社团的「种子」，非核心但和核心强连接的节点是边界节点，既不核心也不边界的就是离群点（outlier）。
| 参数 | 含义 | 典型范围 | 调大后果 | 调小后果 |
|---|---|---|---|---|
| ε | 结构相似度阈值 | 0.3 ~ 0.8 | 社团变多、变小、离群点增多 | 社团合并、边界模糊 |
| μ | 核心节点最小邻居数 | 2 ~ 5 | 核心节点减少、小社团消失 | 大量节点成为核心、社团膨胀 |
这两个参数没有万能值。我的血泪经验是：先在 0.5 和 2 附近跑一版，看社团数量和你对数据的先验认知差多少，再微调。如果数据平均度很低（比如 2~3），μ 设 3 以上会导致几乎没有核心节点，整个图全是离群点。
2.3 用 Python 实现结构相似度计算
下面是一个不依赖第三方图算法的纯 Python 实现，方便你理解每一步在做什么：
import math from collections import defaultdict def build_adjacency(edges): """从边列表构建邻接表，包含节点自身""" adj = defaultdict(set) for u, v in edges: adj[u].add(v) adj[v].add(u) # 每个节点把自己也加进去 for node in adj: adj[node].add(node) return adj def structural_similarity(adj, u, v): """计算节点 u 和 v 的结构相似度""" neighbors_u = adj[u] neighbors_v = adj[v] common = neighbors_u & neighbors_v denom = math.sqrt(len(neighbors_u) * len(neighbors_v)) if denom == 0: return 0.0 return len(common) / denom def find_similar_pairs(adj, epsilon): """找出所有结构相似度 >= epsilon 的节点对""" nodes = list(adj.keys()) similar = defaultdict(set) for i in range(len(nodes)): for j in range(i + 1, len(nodes)): u, v = nodes[i], nodes[j] sim = structural_similarity(adj, u, v) if sim >= epsilon: similar[u].add(v) similar[v].add(u) return similar这段代码里build_adjacency把自身加入邻居集合，这是 SCAN 原文的定义，不能省。structural_similarity用集合交集算共同邻居，用math.sqrt做归一化。find_similar_pairs是 O(n²) 的暴力枚举，3000 节点以内还能忍，再大就得用倒排索引或者稀疏矩阵优化。参数 epsilon 直接决定哪些边被保留为强连接。
3. 从相似度到社团：核心节点、边界节点与离群点的完整聚类流程
3.1 核心节点的判定与种子选取
有了相似度矩阵之后，SCAN 的聚类流程分三步走。第一步，标记核心节点：对每个节点 u，统计它在相似度图中邻居的数量（即与它强连接的节点数），如果 ≥ μ，则 u 是核心节点。
def find_core_nodes(similar, mu): """找出所有核心节点""" cores = set() for node, neighbors in similar.items(): if len(neighbors) >= mu: cores.add(node) return cores注意这里统计的是「强连接邻居数」，不是原始图上的度。一个节点在原始图上可能有 20 个邻居，但如果 ε 设得高，强连接可能只有 1 个，那它照样不是核心。
3.2 社团扩展与重叠处理
第二步，从每个未分配的核心节点出发，做 BFS 扩展：把与核心节点强连接的所有节点拉进同一个社团。如果两个核心节点强连接，它们属于同一社团。这个过程会产生重叠——一个边界节点可能同时强连接两个不同社团的核心节点，那它就同时属于两个社团。
def scan_clustering(adj, epsilon, mu): """完整的 SCAN 聚类流程""" similar = find_similar_pairs(adj, epsilon) cores = find_core_nodes(similar, mu) # 构建核心节点之间的连通分量 visited = set() clusters = [] for core in cores: if core in visited: continue # BFS 扩展 cluster = set() queue = [core] visited.add(core) while queue: current = queue.pop(0) cluster.add(current) for neighbor in similar[current]: if neighbor in cores and neighbor not in visited: visited.add(neighbor) queue.append(neighbor) elif neighbor not in cores: # 边界节点直接加入，不继续扩展 cluster.add(neighbor) clusters.append(cluster) # 找出离群点：不属于任何社团的节点 all_assigned = set() for c in clusters: all_assigned |= c outliers = set(adj.keys()) - all_assigned return clusters, outliers这段代码的关键在于：只有核心节点才会触发 BFS 扩展，边界节点被拉进社团但不继续往外扩。这保证了社团不会通过边界节点「串门」而合并。visited集合只记录核心节点，边界节点可以被多个社团重复加入，这就是重叠社团的来源。
3.3 在真实图上跑通的最小示例
用一个 12 节点的哑铃图加一个桥接节点来验证：
edges = [ (1,2),(1,3),(2,3),(2,4),(3,4),(4,5), (5,6),(6,7),(7,8),(8,9),(9,10),(10,11), (11,12),(10,12),(5,10) # 5-10 是桥接边 ] adj = build_adjacency(edges) clusters, outliers = scan_clustering(adj, epsilon=0.4, mu=2) for i, c in enumerate(clusters): print(f"社团 {i+1}: {sorted(c)}") print(f"离群点: {sorted(outliers)}")跑出来你会看到两个主要社团，节点 5 和 10 可能同时出现在两个社团里（如果它们的强连接跨了两边），而如果某个节点只挂在桥接边上且不满足核心条件，它就会掉进离群点。ε=0.4 和 μ=2 这组参数对这个小图比较友好，你可以试着把 ε 调到 0.6 看社团怎么碎掉，或者把 μ 调到 3 看核心节点怎么消失。
4. 避坑指南：SCAN 落地时最容易翻车的五个地方
4.1 现象：跑出来全是离群点，一个社团都没有
原因：μ 设得比图中节点的平均强连接数还大。比如数据平均度是 3，ε=0.5 时强连接平均只有 1~2 条，μ=3 就导致没有任何节点能成为核心。
解决：先统计一下在给定 ε 下，每个节点的强连接数分布。用numpy.percentile看中位数，μ 不要超过中位数。我一般会写个快速诊断脚本：
import numpy as np strong_degrees = [len(similar[n]) for n in adj] print(f"强连接度中位数: {np.median(strong_degrees)}") print(f"强连接度 75 分位: {np.percentile(strong_degrees, 75)}")4.2 现象：社团大得离谱，半个图连成一个
原因：ε 太小，导致大量弱连接被当成强连接，核心节点通过边界节点间接串联。SCAN 虽然不直接合并社团，但如果两个核心节点之间存在一条强连接路径，它们就会被划进同一个社团。
解决：逐步提高 ε，观察社团数量变化曲线。通常 ε 从 0.3 提到 0.5，社团数量会有明显跳变。找到那个跳变点附近的 ε 值。
4.3 现象：重叠节点过多，一个节点属于五六个社团
原因：数据本身存在大量「社交蝴蝶」节点，或者 ε 设得刚好让很多边界节点同时满足多个核心的强连接条件。
解决：这未必是 bug，可能是数据特性。如果确实不想要这么多重叠，可以后处理：对每个边界节点，只保留相似度最高的那个社团。但这样做会丢失 SCAN 的核心优势，慎用。
4.4 现象：O(n²) 相似度计算在大图上跑不动
原因：暴力枚举所有节点对，10000 节点就是 5000 万次计算，Python 里基本不可接受。
解决：用稀疏矩阵或者倒排索引。常见做法是先用 Jaccard 相似度的近似算法（如 MinHash）做候选筛选，只对可能相似的对做精确计算。或者直接用 networkx 的nx.algorithms.community里没有 SCAN，但可以用scipy.sparse做矩阵运算加速。
4.5 现象：结果每次跑都不一样
原因：如果用了随机化优化（比如随机采样候选对），结果会有波动。纯暴力实现是确定性的，但慢。
解决：如果必须用近似算法，固定随机种子。如果结果波动大到影响结论，说明 ε 处于临界区域，稍微调一点就会改变社团结构，这时候应该报告多个参数下的结果，而不是只报一个。
5. 进阶技巧：用 SCAN 做团伙识别时的参数扫描与结果验证
5.1 参数扫描的工程化做法
在实际风控场景里，我不会只跑一组 ε 和 μ。通常做法是做一个网格扫描，把 ε 从 0.3 到 0.7 按 0.05 步进，μ 从 2 到 5 按 1 步进，每组参数记录：社团数量、最大社团占比、离群点比例、重叠节点比例。然后画一张热力图，找那个「社团数量稳定、离群点比例在 5%~15% 之间」的区域。
import itertools results = [] for eps in [0.3, 0.35, 0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7]: for mu in [2, 3, 4, 5]: clusters, outliers = scan_clustering(adj, eps, mu) n_clusters = len(clusters) max_ratio = max(len(c) for c in clusters) / len(adj) if clusters else 0 outlier_ratio = len(outliers) / len(adj) results.append({ 'epsilon': eps, 'mu': mu, 'n_clusters': n_clusters, 'max_cluster_ratio': round(max_ratio, 3), 'outlier_ratio': round(outlier_ratio, 3) }) for r in results: print(r)这段代码的输出可以直接喂给 pandas 做透视表。我一般会重点关注max_cluster_ratio超过 0.5 的参数组合，那意味着有一个社团吞掉了半个图，通常不可接受。
5.2 结果验证：用模块度和轮廓系数做交叉检查
SCAN 不优化模块度，但你可以用模块度来评估划分质量。把重叠节点随机分配到其中一个社团，然后算模块度。如果模块度低于 0.3，说明社团结构不明显，可能数据本身就不适合做社团发现。
另一个验证手段是看社团内部的平均结构相似度。健康的社团，内部平均相似度应该明显高于全局平均相似度。如果两者差不多，说明 ε 设得太低，社团没有区分度。
5.3 一个我常犯的错误
早期我总想把所有节点都塞进社团，看到离群点就想调参数消灭它们。后来才想明白：离群点本身就是信息。在风控场景里，那些不属于任何团伙的孤立节点，往往才是需要单独关注的异常点。SCAN 把离群点显式标出来，这是特性，不是缺陷。现在我的习惯是：先接受 10% 左右的离群点，再去看这些离群点里有没有值得深挖的个案。希望帮到你。
本文还有配套的精品资源，点击获取
