Link Prediction 链接预测算子集
算子类别：Link Prediction（链接预测、潜在关系预测与相似度评估）
算法数量：11 个
适用阶段：潜在边预测、关系推荐、相似节点发现、隐藏关系挖掘、社区内关系增强、跨社区连接分析、结构相似度评估、关系强度评分、路径与流量辅助预测
产品定位：为“哪些节点未来可能连边 / 哪些关系值得推荐 / 哪些节点结构相似 / 哪些隐藏关系更强 / 社区结构如何影响潜在连接”提供链接预测与关系评分能力底座。
一、算子集概述
Link Prediction 算子集聚焦于网络中潜在连接关系的预测、评分与排序，主要回答以下问题：
-
潜在关系预测
- 哪些当前尚未连接的节点，未来更可能产生连接？
- 哪些“非边”最值得推荐或重点关注？
- 哪些节点对具有较高的结构接近性？
-
共同邻居与局部结构
- 两个节点是否拥有足够多的共同邻居？
- 共同邻居是普通节点，还是低度、高价值、强信号节点？
- 高度节点是否更容易吸引新的连接？
-
社区感知预测
- 两个节点是否处于同一社区？
- 社区内部的共同邻居是否增强了连接可能性？
- 潜在关系更偏向社区内聚，还是跨社区桥接？
-
全局相似度与随机游走
- 两个节点是否在全局结构上相似？
- 是否可以通过路径、随机游走或采样方式估计节点相似度？
- 是否适合在大规模图上进行近似相似度计算？
-
关系强度与结构辅助判断
- 节点之间是否存在较强的可达能力或流量承载能力？
- 两个节点之间的共同邻居是否具有更强的关系区分度？
- 哪些潜在连接具有更高的解释价值？
二、算子能力分类
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 共同邻居比例 | jaccard_coefficient | 基于邻居集合交并比衡量节点相似度 |
| 稀有共同邻居加权 | adamic_adar_index | 稀有共同邻居贡献更高，用于发现高质量共同关系 |
| 资源分配评分 | resource_allocation_index | 低度共同邻居分配更高权重，强化隐蔽强关系 |
| 优先连接预测 | preferential_attachment | 基于节点度数乘积预测头部节点吸引力 |
| 社区感知共同邻居 | cn_soundarajan_hopcroft | 同社区共同邻居对潜在连接贡献更高 |
| 社区感知资源分配 | ra_index_soundarajan_hopcroft | 结合社区约束与资源分配思想进行评分 |
| 社区内外连接分析 | within_inter_cluster | 区分社区内共同邻居与跨社区共同邻居 |
| 全局结构相似度 | simrank_similarity | 基于“相似节点连接相似节点”的递归思想计算相似度 |
| 最大流关系强度 | maximum_flow | 基于节点间最大可传输流量评估连接能力或关系强度 |
| 采样式路径相似度 | panther_similarity | 通过随机路径采样估计节点之间的相似性 |
| 共同邻居离散度 | dispersion | 衡量共同邻居之间的分散程度，用于识别更有意义的潜在关系 |
三、通用输入输出约定
-
输入
G：NetworkX Graph / DiGraph -
常见输入参数：
ebunch：需要计算链接预测分数的节点对集合community：社区标签节点属性名，适用于社区感知类算法source/target：源节点与目标节点，适用于流量或相似度查询类算法capacity：边容量属性名，适用于最大流相关计算
-
常见输出类型：
- 链接预测类：
iterator of (u, v, score) - 相似度类：相似度分数、节点相似度字典或矩阵
- 流量类：最大流值及流分配结构
- 判分结果：数值越大通常表示潜在连接可能性、结构相似度或关系强度越高
- 链接预测类：
四、算子详细说明
1. jaccard_coefficient —— Jaccard 系数
功能说明 衡量两个节点邻居集合的重叠比例，即共同邻居占全部邻居的比例。
J(u, v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)|
产品价值
- 提供简单、直观、可解释的相似度评分
- 适合衡量两个节点的关系重叠程度
- 对高度节点有一定抑制作用，避免仅因邻居多而得分过高
典型场景
- 好友推荐
- 商品相似推荐
- 内容关联推荐
- 用户兴趣相似度分析
- 关系网络中的潜在边排序
适用与特性
- 图类型：通常用于无向图
- 输出：
(u, v, score) - 特点：强调共同邻居比例，而不是共同邻居绝对数量
2. adamic_adar_index —— Adamic-Adar 指数
功能说明 对共同邻居进行加权，度数越小的共同邻居贡献越大。低度共同邻居通常代表更稀有、更有区分度的关系信号。
AA(u, v) = Σ 1 / log(deg(w)), w ∈ CN(u, v)
产品价值
- 强化“稀有共同邻居”的预测价值
- 比普通共同邻居数量更能体现关系质量
- 适合发现小圈层、低曝光但强相关的潜在连接
典型场景
- 社交网络中的高质量好友推荐
- 反欺诈中的隐蔽中介关系发现
- 科研合作预测
- 小圈层关系挖掘
- 用户兴趣深度匹配
适用与特性
- 图类型：通常用于无向图
- 输出：
(u, v, score) - 特点：对高度共同邻居进行惩罚，但惩罚力度相对温和
3. preferential_attachment —— 优先连接
功能说明 基于“富者愈富”思想，认为度数越高的节点越容易产生新的连接。两个节点的得分通常由二者度数乘积决定。
PA(u, v) = deg(u) × deg(v)
产品价值
- 捕捉头部节点、枢纽节点的吸引效应
- 不依赖共同邻居，适合稀疏图中的连接预测
- 可用于衡量节点影响力驱动下的潜在连接概率
典型场景
- 社交平台关注推荐
- 大 V / 头部账号连接预测
- 引用网络预测
- 网页链接预测
- 交易网络中的高活跃节点关系预测
适用与特性
- 图类型：通常用于无向图
- 输出：
(u, v, score) - 特点：偏向影响力和活跃度预测，而不是相似性预测
4. resource_allocation_index —— 资源分配指数
功能说明 假设共同邻居向两端节点分配资源，度数越低的共同邻居能够分配给目标节点的资源越多。
RA(u, v) = Σ 1 / deg(w), w ∈ CN(u, v)
产品价值
- 强化低度共同邻居的贡献
- 比 Adamic-Adar 对高度节点惩罚更强
- 适合识别低曝光、强绑定、隐蔽型潜在关系
典型场景
- 隐藏关系发现
- 反欺诈团伙关系挖掘
- 小规模强关系推荐
- 供应链隐性关联分析
- 内部协作关系预测
适用与特性
- 图类型：通常用于无向图
- 输出：
(u, v, score) - 特点：更重视低度共同邻居，适合强调关系稀缺性的场景
5. cn_soundarajan_hopcroft —— 社区感知共同邻居
功能说明 在共同邻居基础上引入社区信息。同一社区内的共同邻居会被认为更重要，从而提高同社区潜在连接的得分。
产品价值
- 将局部结构与社区结构结合
- 强化社区内部关系推荐
- 对圈层、组织、兴趣群体内的关系预测更友好
典型场景
- 部门内部协作推荐
- 兴趣社区好友推荐
- 圈层内潜在关系发现
- 企业组织内部关系增强
- 社群运营中的关系补全
适用与特性
- 图类型：通常用于无向图
- 输入依赖：节点需具备社区标签属性
- 输出：
(u, v, score) - 特点：适合同社区关系强化，不适合无社区标签图直接使用
6. ra_index_soundarajan_hopcroft —— 社区感知资源分配指数
功能说明 将资源分配思想与社区结构结合。低度共同邻居本身贡献较高，如果共同邻居还处于相同社区，则进一步增强其预测价值。
产品价值
- 同时考虑共同邻居稀缺性与社区一致性
- 适合发现社区内部的隐性强关系
- 比普通资源分配指数更适合带有圈层结构的网络
典型场景
- 企业内部潜在协作发现
- 社区内强关系推荐
- 组织关系补全
- 兴趣小组成员推荐
- 风控网络中的同团伙关系挖掘
适用与特性
- 图类型：通常用于无向图
- 输入依赖：节点需具备社区标签属性
- 输出：
(u, v, score) - 特点：低度共同邻居 + 同社区关系通常具有更高得分
7. within_inter_cluster —— 社区内 / 跨社区连接评分
功能说明 比较节点对的社区内共同邻居与跨社区共同邻居，衡量潜在连接更偏向社区内聚还是跨社区桥接。
产品价值
- 区分内部强化关系与跨圈连接关系
- 适合分析关系是否具有“破圈”价值
- 可辅助判断潜在连接的结构角色
典型场景
- 跨部门协作发现
- 跨兴趣圈层推荐
- 社区桥接节点分析
- 组织网络结构优化
- 社交网络多样性推荐
适用与特性
- 图类型：通常用于无向图
- 输入依赖：节点需具备社区标签属性
- 输出：
(u, v, score) - 特点：适合同时关注社区内聚和跨社区连接的场景
8. simrank_similarity —— SimRank 相似度
功能说明 基于“两个节点如果被相似的节点连接，那么它们也相似”的递归思想，计算节点之间的全局结构相似度。
产品价值
- 不只依赖直接共同邻居，也考虑更深层的结构相似性
- 适合发现“结构角色相似”的节点
- 可用于推荐、实体匹配、图结构相似分析
典型场景
- 用户相似度分析
- 网页结构相似度计算
- 知识图谱实体相似度
- 引用网络相似论文发现
- 推荐系统中的结构相似召回
适用与特性
- 图类型：有向图 / 无向图
- 输出：节点相似度分数或相似度结果结构
- 注意：通常计算成本高于局部启发式链接预测算法
9. maximum_flow —— 最大流
功能说明 计算从源节点到目标节点在容量约束下能够传输的最大流量，可用于衡量两个节点之间的连接承载能力或关系强度。
产品价值
- 从路径和容量角度评估节点之间的连接强度
- 可辅助判断两个节点之间是否存在强可达关系
- 适合带权、带容量网络中的关系能力分析
典型场景
- 资金流关系强度分析
- 供应链通路能力评估
- 交通与物流网络承载分析
- 通信网络容量分析
- 风险传播通道能力评估
适用与特性
- 图类型：通常用于有向图，也可用于具备容量属性的网络
- 关键参数：
source、target、capacity - 输出：最大流值及流分配结构
- 特点：更偏向关系强度与通路能力评估，不是传统共同邻居类链接预测
10. panther_similarity —— Panther 相似度
功能说明 通过随机路径采样估计节点之间的相似性，适合在较大规模图上进行近似相似度计算。
产品价值
- 支持大规模图上的相似节点发现
- 相比全量精确计算，更适合近似召回
- 可作为推荐系统中的候选节点生成能力
典型场景
- 大规模用户相似度召回
- 内容相似推荐
- 图数据库中的相似节点检索
- 知识图谱近似相似实体发现
- 大规模关系网络探索
适用与特性
- 图类型：通常用于无向图
- 输出：相似节点或相似度结果
- 特点：采样式方法，适合效率优先的大图场景
11. dispersion —— 离散度 / 分散度
功能说明
衡量两个节点共同邻居之间的分散程度。相比仅统计共同邻居数量，dispersion 更关注共同邻居之间是否彼此分离，从而判断潜在关系是否更有信息量。
产品价值
- 帮助识别更有意义的潜在连接
- 可区分普通共同好友关系与更强的结构信号
- 适合在社交网络中发现非显而易见但值得关注的关系
典型场景
- 社交网络好友推荐
- 隐性强关系发现
- 社区边界关系识别
- 跨圈层弱连接分析
- 关系推荐质量优化
适用与特性
- 图类型：通常用于无向图
- 输出：节点对的离散度评分
- 特点：关注共同邻居之间的结构分布，而非只看共同邻居数量
五、推荐使用指南
1. 基于共同邻居的快速链接预测
- 计算共同邻居比例：
jaccard_coefficient - 强调稀有共同邻居：
adamic_adar_index - 更强惩罚高度共同邻居：
resource_allocation_index - 关注头部节点吸引力：
preferential_attachment
2. 社区感知链接预测
- 强化同社区共同邻居：
cn_soundarajan_hopcroft - 结合社区与低度共同邻居：
ra_index_soundarajan_hopcroft - 区分社区内聚与跨社区桥接：
within_inter_cluster
3. 全局相似度与近似相似度
- 计算递归结构相似度：
simrank_similarity - 大规模近似相似节点发现：
panther_similarity
4. 关系强度与路径能力分析
- 基于容量和通路能力评估关系强度：
maximum_flow - 判断共同邻居结构是否更有区分度：
dispersion
5. 场景化选型建议
- 想要简单、可解释的推荐分数：
jaccard_coefficient - 想突出高质量共同好友：
adamic_adar_index - 想挖掘隐蔽、低曝光强关系：
resource_allocation_index - 想预测头部节点吸引连接的能力：
preferential_attachment - 已有社区标签，做圈内推荐：
cn_soundarajan_hopcroft - 社区 + 隐性强关系挖掘：
ra_index_soundarajan_hopcroft - 想分析内聚关系还是跨圈连接：
within_inter_cluster - 想计算全局结构相似度：
simrank_similarity - 想从流量承载角度评估关系强度：
maximum_flow - 想在大图中高效查找相似节点：
panther_similarity - 想判断共同邻居结构是否具有更强关系信号：
dispersion
六、可直接回答的典型问题
- “哪些用户之间最可能产生新的关系？”
- “我最可能认识但还没认识的人是谁？”
- “哪些账号之间存在隐藏关系？”
- “哪些商品或内容之间存在潜在强关联？”
- “哪些节点虽然没有直接连接，但结构上很相似？”
- “共同好友中哪些关系信号更有价值？”
- “哪些潜在连接属于同社区内部强化关系？”
- “哪些潜在连接可能是跨社区桥接关系？”
- “哪些节点之间的通路能力或承载能力最强？”
- “在大规模图中，哪些节点最相似？”
- “哪些共同邻居结构更分散、更能说明潜在强关系？”
七、算子清单
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | jaccard_coefficient | Jaccard 共同邻居相似系数 |
| 2 | adamic_adar_index | Adamic-Adar 稀有共同邻居加权指数 |
| 3 | preferential_attachment | 优先连接得分 |
| 4 | resource_allocation_index | 资源分配指数 |
| 5 | cn_soundarajan_hopcroft | 社区感知共同邻居指数 |
| 6 | ra_index_soundarajan_hopcroft | 社区感知资源分配指数 |
| 7 | within_inter_cluster | 社区内 / 跨社区共同邻居评分 |
| 8 | simrank_similarity | SimRank 全局结构相似度 |
| 9 | maximum_flow | 最大流关系强度评估 |
| 10 | panther_similarity | Panther 随机路径采样相似度 |
| 11 | dispersion | 共同邻居离散度评分 |