SCAN社团发现算法：结构相似度、核心节点与重叠社团聚类实战

简介本资源为基于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 多个节点的兴趣圈子关系图。我一开始图省事直接上了标签传播结果跑出来的社团像被狗啃过——同一个兴趣小组被切成七八块还有几个大社团把半个图都吞了。后来换成 SCANStructural Clustering Algorithm for Networks同一份数据社团边界干净了很多而且那些「既在这个圈子又在那个圈子」的节点被单独标了出来。这就是 SCAN 社团发现算法最核心的价值它不强行把每个节点塞进唯一社团而是允许枢纽节点和离群点存在。SCAN 属于基于结构相似度的社团发现算法2007 年由 Xu 等人提出。它的基本假设很朴素如果两个节点共享足够多的共同邻居它们就倾向于在同一个社团里。这个「足够多」由参数 εepsilon控制而「社团至少要有多少个节点」由 μmu控制。相比模块度优化那一派Louvain、LeidenSCAN 不追求全局最优划分而是从局部结构出发天然能识别重叠社团和噪声节点。适合谁用做社交网络分析、蛋白质相互作用网络、引文网络、风控团伙识别的从业者尤其是当你发现数据里存在「一人混多个圈子」或者「大量孤立节点」的时候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, epsilon0.4, mu2) for i, c in enumerate(clusters): print(f社团 {i1}: {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% 左右的离群点再去看这些离群点里有没有值得深挖的个案。希望帮到你。本文还有配套的精品资源点击获取