Bipartite 二分图算子集
算子类别：Bipartite（二分图识别与结构合法性判断）
算法数量：1 个
适用阶段：图结构合法性校验、异构关系建模前置检查、二部网络分析准备、用户-物品图建模、实体-关系类型校验、推荐系统图结构诊断、匹配/投影/二分网络分析前置判断
产品定位：为“这个图是否可以划分为两个互不相交的节点集合 / 边是否只连接两个集合之间的节点 / 是否满足二分图建模要求”提供二分图结构识别能力底座。
一、算子集概述
Bipartite 算子集聚焦于二分图结构的识别与合法性校验，主要回答以下问题：
-
二分结构判断
- 图中的节点是否可以被划分为两个互不相交的集合？
- 是否所有边都只连接两个集合之间的节点？
- 同一集合内部是否不存在边？
-
异构关系建模校验
- 用户-商品、作者-论文、账户-交易对象等关系是否符合二部结构？
- 图中是否混入了同类型节点之间的非法连接？
- 是否可以安全地进入二分网络分析、匹配分析或推荐建模流程？
-
推荐与匹配场景前置判断
- 用户与物品是否构成标准二分图？
- 任务与人员、公司与职位、论文与作者之间是否满足二部关系结构？
- 是否适合进一步做投影、匹配、协同过滤或图表示学习？
-
结构异常发现
- 如果图不是二分图，是否可能存在奇环或同侧连接？
- 是否存在破坏二分结构的异常边？
- 数据建模时是否出现了错误的节点类型或关系类型？
二、算子能力分类
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 二分图判定 | is_bipartite | 判断图是否可以被划分为两个互不相交的节点集合，并且所有边都只连接不同集合中的节点 |
三、通用输入输出约定
-
输入
G：NetworkX Graph -
常见输入要求：
- 通常用于无向图
- 图可以是连通图，也可以是非连通图
- 如果图中存在奇数长度环，则不满足二分图条件
-
常见输出类型：
-
判定类：
boolTrue：图是二分图False：图不是二分图
-
四、算子详细说明
1. is_bipartite —— 是否为二分图
功能说明
判断图是否为二分图。二分图要求图中的节点可以被划分为两个互不相交的集合 U 和 V，并且每条边都只连接 U 中的节点与 V 中的节点，不允许同一集合内部存在边。
产品价值
- 快速校验图是否满足二部结构
- 支持推荐系统、匹配系统和异构关系网络的前置检查
- 帮助发现破坏二分结构的数据异常或建模错误
典型场景
- 用户-商品交互图校验
- 作者-论文关系图校验
- 账户-设备关系图校验
- 公司-职位匹配图校验
- 学生-课程选课图校验
- 医生-患者关系图校验
- 风控场景中的实体-事件二部图检查
适用与特性
- 图类型：通常用于无向图
- 输出：
bool - 特点：二分图中不存在奇数长度环
- 复杂度：通常为
O(V + E)
五、推荐使用指南
1. 二部结构合法性校验
- 判断图是否为二分图：
is_bipartite
2. 异构图建模前置检查
- 用户-商品图建模前：
is_bipartite - 作者-论文图建模前：
is_bipartite - 账户-设备图建模前：
is_bipartite - 公司-职位匹配图建模前：
is_bipartite
3. 推荐、匹配与投影分析准备
- 做用户-商品推荐前，先判断是否满足二分图结构：
is_bipartite - 做岗位-候选人匹配前，先判断是否存在同侧连接：
is_bipartite - 做二分图投影前，先确认输入结构合法：
is_bipartite
4. 场景化选型建议
- 想判断一个图能否分成两类节点：
is_bipartite - 想确认边是否只连接不同类型节点：
is_bipartite - 想检查用户-商品图是否建模正确：
is_bipartite - 想发现是否存在同侧异常连接：
is_bipartite - 想为匹配、推荐或投影算法做前置校验：
is_bipartite
六、工程与使用注意事项
-
二分图不是简单的“有两类节点” 即使业务上节点分为两类，只要同一类节点之间存在边，图就不满足二分图定义。
-
非连通图也可以是二分图 二分图不要求图必须连通。只要每个连通分量都能被合法二分，整个图就是二分图。
-
奇环会破坏二分结构 如果图中存在三角形、五边形等奇数长度环，则该图一定不是二分图。
-
节点类型属性不等于二分划分结果 业务属性中的
type=user、type=item可以作为解释依据，但二分图判定本身基于边结构。实际划分结果需要与业务类型一致时，还应额外检查节点类型和边端点类型。 -
推荐与匹配场景建议先做结构校验 在进入二分图投影、匹配、协同过滤或用户-物品图建模前，建议先用
is_bipartite进行结构合法性检查。
七、可直接回答的典型问题
- “这个图是不是二分图？”
- “这个用户-商品交互图是否合法？”
- “是否存在同一类节点之间的异常连接？”
- “这个作者-论文网络能不能按二部图建模？”
- “这个图是否可以分成两个互不相交的节点集合？”
- “这个图里是否可能存在奇数环？”
- “这个匹配图是否适合进入后续匹配算法？”
- “这个账户-设备关系网络是否满足二分结构？”
- “这个图能否用于二分图投影分析？”
- “这个推荐系统输入图是否符合用户-物品二部结构？”
八、算子清单
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | is_bipartite | 判断图是否为二分图 |