跳到主要内容

Link Prediction 链接预测算子集

算子类别：Link Prediction（链接预测）
描述：用于预测网络中“尚不存在但可能出现”的连接关系，或评估潜在边的形成概率。广泛应用于好友推荐、关系挖掘、反欺诈、推荐系统、科研合作预测等场景。

一、算子集概述​

Link Prediction 算子集主要解决这样一类问题：

  • 哪些节点 更有可能在未来产生连接？
  • 在当前网络结构下，哪些“非边（non-edge）”最值得关注？
  • 如何结合 共同邻居、节点活跃度、社区结构 等因素，对潜在关系进行打分和排序？

本算子集中的算法大多属于 基于局部结构的启发式方法，特点是：

  • 无需监督学习与历史标签
  • 计算高效、可解释性强
  • 非常适合作为推荐/风控/探索分析的第一层能力

二、算子列表与能力分类​

2.1 基于共同邻居（Common Neighbors）​

算子核心思想
jaccard_coefficient共同邻居占比（交集 / 并集）
adamic_adar_index稀有共同邻居权重更高
resource_allocation_index通过低度节点分配“资源”
preferential_attachment高度节点更容易连边

2.2 融合社区结构（Community-aware）​

算子核心思想
cn_soundarajan_hopcroft同社区内的共同邻居更重要
ra_index_soundarajan_hopcroft社区约束下的资源分配
within_inter_cluster区分“社区内”与“跨社区”共同邻居

三、通用输入输出约定​

3.1 输入（Input）​

  • G：NetworkX 无向图（Undirected Graph）
  • ebunch（可选）：指定需要计算分数的节点对 (u, v)
    • 若为 None，则对所有 当前不存在的边 进行计算
  • community（部分算法）：节点属性名，表示社区标签

3.2 输出（Output）​

  • iterator of (u, v, score)
    • u, v：节点对
    • score：链接预测得分（数值越大，越可能形成连接）

四、算子详细说明​

4.1 jaccard_coefficient —— Jaccard 系数​

功能说明​

衡量两个节点邻居集合的 重叠比例：

J(u,v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)|

适用场景​

  • 好友推荐中的“共同好友比例”
  • 项目/商品/内容的相似性评估
  • 强调 相似度比例 而非绝对数量

特点​

  • 简单直观、易解释
  • 对高度节点有一定惩罚（并集变大）

4.2 adamic_adar_index —— Adamic–Adar 指数​

功能说明​

对共同邻居进行加权：
度数越小（越“稀有”）的共同邻居，贡献越大。

AA(u,v) = Σ(w ∈ CN(u,v)) 1/log(deg(w))

适用场景​

  • 社交网络中的“高质量共同好友”
  • 反欺诈/AML 中的隐蔽中介关系
  • 协作网络中“小圈子内的强信号”

4.3 resource_allocation_index —— 资源分配指数（RA）​

功能说明​

假设共同邻居向两端节点各“分配资源”，
度数越小，分到的资源越多：

RA(u,v) = Σ(w ∈ CN(u,v)) 1/deg(w)

适用场景​

  • 与 Adamic–Adar 类似，但惩罚高度节点更强
  • 适合寻找 隐蔽、低曝光但关系紧密 的潜在连接

4.4 preferential_attachment —— 优先连接​

功能说明​

假设网络遵循“富者愈富”原则：

PA(u,v) = deg(u) × deg(v)

适用场景​

  • 社交平台中，新用户更可能关注“大 V”
  • 引用网络、网页链接、交易网络中的“枢纽效应”

特点​

  • 不依赖共同邻居
  • 更偏向 流量/影响力预测，而非相似性

4.5 cn_soundarajan_hopcroft —— 社区感知共同邻居​

功能说明​

在普通共同邻居基础上，引入 社区约束：

  • 同一社区内的共同邻居贡献更高
  • 跨社区连接被自然抑制

适用场景​

  • 部门/圈子/兴趣社区内部推荐
  • “同圈层关系强化”的预测任务

4.6 ra_index_soundarajan_hopcroft —— 社区感知 RA 指数​

功能说明​

将 资源分配思想 与 社区结构 结合：

  • 低度共同邻居 + 同社区 → 最高贡献

适用场景​

  • 企业/团队内部的潜在协作关系
  • 社区内的隐性强关系挖掘

4.7 within_inter_cluster —— WIC（社区内 / 跨社区）​

功能说明​

比较两类共同邻居：

  • 社区内共同邻居
  • 跨社区共同邻居

通过二者比例衡量“关系是内聚型还是桥接型”。

适用场景​

  • 跨部门 / 跨圈层协作发现
  • 鼓励“破圈”连接 vs 强化内部连接
  • 网络探索与结构多样性分析

五、选型指南（怎么选）​

  • 想要简单相似度：jaccard_coefficient
  • 强调稀有共同邻居：adamic_adar_index
  • 更强惩罚高度节点：resource_allocation_index
  • 关注头部/枢纽吸引力：preferential_attachment
  • 已有社区标签，做圈内推荐：cn_soundarajan_hopcroft
  • 社区 + 隐蔽强关系：ra_index_soundarajan_hopcroft
  • 想区分“内聚 vs 跨圈”关系：within_inter_cluster

六、可直接回答的典型问题​

  • “我最可能认识但还没认识的人是谁？”
  • “哪些账号之间存在隐藏关系？”
  • “哪些跨部门员工最有可能产生合作？”
  • “哪些商品/内容之间存在潜在强关联？”
  • “这个网络更倾向于内聚发展还是跨圈连接？”