2. 图论基础

在反欺诈图谱中，我们处理的不是孤立的数据行，而是“谁和谁有关系”的网络。图论正是描述这种关系结构的语言。把账户、设备、手机号、银行卡、IP 地址看作顶点，把转账、登录、绑定、共享设备等行为看作边，欺诈团伙就会自然浮现为图中紧密连接的区域。本章先把图论中最核心的概念讲清楚，为后续“连通分量发现团伙”打下基础。

一、核心原理：图由顶点和边构成

一个图 G = (V, E) 由顶点集合 V 和边集合 E 组成。顶点是实体，边是实体之间的关系。在反欺诈场景中，顶点通常包括：用户账户、设备指纹、手机号、银行卡、身份证、IP、WiFi、收货地址等；边则包括：转账、登录、绑定、共用设备、同一 IP 登录、同一收货地址等。

根据边是否有方向，图分为无向图和有向图。无向图的边 {u, v} 表示 u 与 v 之间存在对称关系，例如“共用同一台设备”。有向图的边 (u, v) 表示从 u 指向 v 的关系，例如“u 向 v 转账”。方向在反欺诈中非常重要：A 给 B 转账与 B 给 A 转账，含义可能完全不同。

概念	定义	反欺诈示例
顶点 V	图中的实体节点	账户、设备、手机号、银行卡
边 E	实体之间的关系	转账、登录、绑定、共用设备
无向图	边无方向，关系对称	两个账户共用一台设备
有向图	边有方向，关系不对称	A 向 B 转账
路径	顶点与边交替的序列	A→设备→B→银行卡→C
连通	两顶点间存在路径	A 与 C 通过设备间接关联
连通分量	极大连通子图	一个独立欺诈团伙

二、路径、连通性与连通分量

路径是图中从一个顶点到另一个顶点经过的顶点和边序列。例如在设备关联图中，路径 A → 设备D1 → B → 银行卡K1 → C 说明 A、B、C 通过设备和银行卡形成了关联链。路径长度通常用边的数量衡量。若路径中不重复经过顶点，称为简单路径。

连通性描述两个顶点之间是否存在路径。在无向图中，若顶点 u 与 v 之间存在路径，则称 u 和 v 连通。若图中任意两个顶点都连通，则整个图是连通图。在有向图中，连通性进一步分为弱连通和强连通：忽略方向后连通为弱连通；任意两点互相可达为强连通。

连通分量是无向图中的极大连通子图。所谓“极大”，是指不能再加入任何其他顶点而保持连通。直观理解：把图想象成若干张彼此分离的网，每一张网就是一个连通分量。在反欺诈中，一个连通分量往往对应一个潜在团伙——因为团伙成员之间通常通过设备、转账、手机号等关系直接或间接地连在一起，而与外部账户缺乏关联。

三、方法流程：从原始数据到连通分量

在实际工程中，计算连通分量通常遵循以下流程：

1. 实体抽取：从交易、登录、绑定等日志中抽取顶点，如账户 ID、设备 ID、手机号。
2. 关系构建：根据业务规则生成边，例如同一设备登录两个账户则建立无向边。
3. 图存储：使用邻接表或邻接矩阵存储图。稀疏图优先用邻接表。
4. 遍历算法：使用 BFS 或 DFS 遍历所有顶点，标记已访问顶点，每次从未访问顶点出发得到一个连通分量。
5. 团伙输出：输出每个连通分量的顶点集合、规模、边密度等特征，供风控策略使用。

下面是一个使用 Python 邻接表计算无向图连通分量的最小示例：

from collections import defaultdict, deque

def connected_components(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    components = []

    for node in graph:
        if node in visited:
            continue
        queue = deque([node])
        visited.add(node)
        comp = []

        while queue:
            cur = queue.popleft()
            comp.append(cur)
            for nxt in graph[cur]:
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append(nxt)

        components.append(comp)

    return components

edges = [
    ("A", "D1"), ("B", "D1"), ("B", "K1"),
    ("C", "K1"), ("X", "D2"), ("Y", "D2")
]
print(connected_components(edges))
# 输出: [['A', 'D1', 'B', 'K1', 'C'], ['X', 'D2', 'Y']]

运行结果中，第一个分量包含 A、B、C 三个账户以及设备 D1、银行卡 K1，第二个分量只包含 X、Y 和设备 D2。前者规模更大、关联更复杂，应优先进入人工审核或团伙评分流程。

四、案例与场景：设备共享团伙识别

假设某平台发现一批账户在短时间内通过同一设备频繁登录。我们构建无向图：账户和设备都是顶点，登录关系是边。计算连通分量后得到三个簇：

• 簇一：12 个账户共用 3 台设备，且账户之间还有转账关系，风险极高。
• 簇二：4 个账户共用 1 台设备，但无资金往来，可能是家庭共用设备，风险中等。
• 簇三：2 个账户共用 1 台设备，注册时间接近，需进一步观察。

这说明连通分量本身只是“分组”，并不直接等于欺诈结论。它提供的是高效的候选集合，后续还需结合转账金额、时间密度、设备异常度等特征进行评分。

五、误区与复盘

误区一：把有向图当无向图处理。转账关系有方向，若忽略方向，可能把“收款方”和“付款方”混为一谈，导致团伙边界失真。建议根据业务问题选择图类型：设备共享用无向图，资金流向用有向图。

误区二：认为连通分量越大越危险。大分量可能包含大量正常用户，例如热门设备或公共 WiFi。应结合分量内部边密度、异常顶点比例等指标综合判断。

误区三：忽略孤立顶点。孤立顶点自身构成一个大小为 1 的连通分量。它们通常不是团伙，但在统计分量规模分布时不应遗漏。

复盘要点：连通分量是团伙发现的“粗筛”手段，核心价值在于把全局图切分为互不相交的候选群体，降低后续分析复杂度。掌握顶点、边、路径、连通性这些基础概念，才能正确选择算法并解释结果。