简介链路预测是网络分析中的重要研究方向用于在社交网络、生物网络等复杂系统中发现尚未被观测到的潜在连接。资源包名为LinkPrediction提供了一套完整的Python链路预测解决方案包含图数据结构定义、改进的共同邻居算法与资源分配算法实现、基于相似度的多种预测方法以及数据预处理、测试评估和可视化分析模块。压缩包共23个文件以10个Python脚本为核心辅以项目配置xml/iml、编译缓存pyc和数据可视化图像png整体仅86KB结构紧凑便于快速部署学习。已有973人学习下载该资源适合网络科学和数据挖掘方向的学生、研究人员快速入门和开展后续研究。通过学习代码可掌握图模型构建、链路预测算法原理及其Python实现并可直接在模拟网络上进行实验对比与二次开发对网络科学和机器学习研究者具有实用价值。1. 链路预测不只是“猜边”它解决的是图上“连接缺失”的问题微信的“你可能认识的人”、电商详情页的“猜你想要”、风控里的团伙识别骨子里是同一个算法问题链路预测link prediction。标题里这个 LinkPrediction.rar是这类 python 工程最常见的打包形态一套关于图数据、特征工程、分类器和评估指标的代码集合。它输入一张只画了一部分边的图输出的是剩下没出现的边里哪些最可能在未来连上。我把这套东西拆开从选型、负采样、特征构建到避坑给你能照着复现的落地路径。适合刚接触图数据、想用 python 做链路预测的工程师。2. 两条路线怎么选无监督相似度与有监督特征工程的边界链路预测的从业方案大致分两派一派直接用网络拓扑的相似度指标对候选边排序另一派把候选边抽成特征交给分类器判断“连不连”。这两条路线的实现难度、效果上限和踩坑方式都不同。做之前先选好路线比直接调算法参数重要得多。2.1 基于拓扑相似度的无监督路线从 Common Neighbors 到 RA最常见的无监督做法是算“两个节点有多像”像度高就预测它会连上。经典指标按从简单到复杂的顺序排Common NeighborsCN直接数共同邻居个数Jaccard 把共同邻居数除以两个节点的并集大小抵消度数影响Adamic-AdarAA认为共同邻居里度越低的人贡献的信息量越大所以用 1/log(deg(w)) 做权重Resource AllocationRA更激进直接用 1/deg(w) 做权重Katz 则把不同长度的路径都算进去。这些指标在 Python 里用 networkx 就能跑不需要任何训练nx.adamic_adar_index(G, ebunch)一次就返回候选边列表的分数。它们的共同特点是可以在秒级跑完十万节点级别的图结果完全可解释——你能够说清楚“这两个人是因为共同的同事 X 被预测认识的”。缺点是只用了图的局部结构节点自身的属性、行为时间线都没用上在稀疏图上往往力不从心。我一般把相似度指标当作基线和下界。如果 CN/Jaccard 的 AUC 就有 0.8 以上说明这个网络结构本身充满规律值得用重一点的有监督方法再挖如果基线只有 0.6 出头那问题大概率出在数据或负采样上盲目上复杂模型只会把翻车现场拖得更难看。2.2 有监督路线把链路预测转成二分类任务有监督路线的本质是把“这条边存不存在”当成一个二分类问题样本是候选边节点对标签 1 表示它真实存在0 表示不存在特征是这对节点的拓扑相似度、属性相似度、时间接近度等。在训练集里构造足够多的正负样本让逻辑回归、随机森林或 GBDT 这些标准分类器去学。这条路线比纯相似度多出两个关键工程点。第一是负采样图里不存在的边远远多于存在的边必须按一定策略抽出来当负样本。第二是特征计算必须小心泄漏如果特征是在包含测试边的整张图上算的模型会作弊离线指标虚高得离谱上线就现原形。这两块我在第三章和第五章分别展开。有监督方法的上限比无监督高因为可以自由叠加特征——节点度数、共同邻居数、历史交互次数、时间衰减权重甚至节点 embedding 都能塞进特征矩阵。常见做法是先把 CN/AA/RA 这些拓扑特征算好再拼上业务属性特征丢给分类器。逻辑回归在这种场景下是个好起点训练快、系数可解释、方便排查哪个特征在起作用。2.3 选型标准网络规模、边密度与可解释性要求选哪条路线我一般看三件事网络规模、边密度、业务要不要解释。网络规模上百万节点以下 networkx 还能直接抗住百万以上需要转稀疏表示或图嵌入边密度上边稀疏比如平均度小于 5时相似度指标区分度会很低有监督加额外属性特征更容易挽回可解释性上风控、社交推荐这类业务盯着问“为什么推荐这个人”相似度和逻辑回归能给出明确答案随机森林也能给出特征重要性而 GNN 这类端到端模型一旦训起来就是个黑匣子。一个比较务实的组合拳是无监督相似度先做召回给每个节点取相似度 top 100 的未连接节点当候选集有监督分类器在候选集上精排。这样既控制了候选空间又保住了可解释性。下表列了三条路线的取舍对比维度相似度指标特征分类器图嵌入/GNN数据要求只要边表边表节点属性可选边表大规模需采样训练成本无训练低到中高可解释性好中到好差适用规模十万级十万到百万级百万级以上效果上限低中高最高数据充足时这里要泼一盆冷水图嵌入和 GNN 不是银弹。在中小规模且有属性数据上一个调好的逻辑回归往往不输 GNN还省掉无数调参和踩坑时间。嵌入方法更适合节点特征本身有语义、或图大到相似度算不动的情况放到最后一章讲。3. 把图变成训练集负采样、特征构建与划分策略链路预测的工程实现七成精力花在数据准备上怎么读边表、怎么做负采样、怎么算特征、怎么划分训练测试。很多项目离线指标遥遥领先一上灰度就崩回看都是这步偷了懒。这一章按顺序把每一步给出一段能直接跑的代码。3.1 从边表到 NetworkX读入与基础统计常见的数据交付形式是 CSV/TSV 边表每行一条边起点、终点、可选的权重和时间戳。第一步是把它读进来并构建图对象顺手统计几个数字判断数据质量——节点数、边数、平均度、连通分量数。平均度低于 5 要小心稀疏问题连通分量太多要关注是不是数据采集遗漏了跨域连接。import pandas as pd import networkx as nx # 读边表假设三列分别是 src, dst, 时间戳 edges pd.read_csv(edges.csv, headerNone, names[src, dst, ts]) G nx.from_pandas_edgelist(edges, src, dst, create_usingnx.Graph()) print(节点数:, G.number_of_nodes()) print(边数:, G.number_of_edges()) print(平均度:, round(2 * G.number_of_edges() / G.number_of_nodes(), 2)) print(连通分量数:, nx.number_connected_components(G))这段代码的要点在create_using参数nx.Graph()得到无向图nx.DiGraph()得到有向图。金融转账、论文引用这类方向敏感的预测必须用有向图社交好友、蛋白质交互则用无向。读入之后建议先做一次连通分量统计如果出现大量孤岛要么是数据源问题要么是业务上本来就不通直接拿全图算特征会引入大量无意义节点。3.2 负采样策略为什么正负样本要按比例配图上存在的边通常远少于不存在的边直接全量当负样本既不现实也没必要——分类器会淹没在海量负样本里。标准做法是按一定比例随机采样不存在的边作为负样本。比例上我常用 1:1 到 1:3先 1:1 跑基线再逐步增加负样本看分类器的 AP 会不会继续涨。这里要固定随机种子否则每次实验的负样本不同对比失真。import random random.seed(42) def negative_sampling(G, n_neg): nodes list(G.nodes()) neg_pairs set() while len(neg_pairs) n_neg: u, v random.sample(nodes, 2) if u ! v and not G.has_edge(u, v): neg_pairs.add((u, v)) return list(neg_pairs)随机负采样是最朴素的方案但它有个隐患采出来的负样本大多是两个毫无关联的冷门节点分类器很容易学会“只要度数高就预测连边”AUC 很好看真上线预测未来新边时却不灵。进阶做法是难负采样——只在二跳以内、看起来像但实际没连的节点对里采逼模型学到结构规律而不是度数规律。代价是负样本区分度下降、训练变难AUC 数字可能下降但时间切片下的真实效果通常会更好。3.3 边特征计算用 batch 模式避开逐对计算的性能黑洞特征这一步新手最常见的错误是写双层 for 循环逐对调用nx.common_neighbors图一大就跑到天荒地老。networkx 对常用相似度指标提供了 batch 接口传一个候选边列表进去内部一次遍历把分数全算出来性能差几个数量级。候选边就是正样本训练集中真实存在的边和负样本采出来的不存在边的并集。import numpy as np from networkx import jaccard_coefficient from networkx import adamic_adar_index, resource_allocation_index def compute_features(G_train, candidate_edges): G_train: 训练子图必须已经剔除测试集边否则特征泄漏 candidate_edges: [(u, v), ...] 正负样本的节点对 feats {} for u, v in candidate_edges: feats[(u, v)] {} # 用 batch 接口一次算出三类拓扑特征 for algo in [jaccard_coefficient, adamic_adar_index, resource_allocation_index]: for u, v, score in algo(G_train, candidate_edges): feats[(u, v)][algo.__name__] score return feats逻辑说明每个 algo 返回一个生成器遍历候选边并计算对应分数分数统一塞到以(u, v)为 key 的字典里最后转成特征矩阵。G_train必须是已经删掉测试边的子图——这是链路预测里最要命的细节我因为忽略它吃过很大的亏第五章会详细说。如果你还想加度数乘积、共同邻居带权版本之类的自定义特征可以在同一套 dict 结构里继续追加。注意compute_features 的第一个参数必须是 G_train。把测试边删干净再开始算特征否则所有离线指标都会失真。3.4 训练与测试怎么划分时间切片优先于随机划分划分方式是链路预测评估有效性的命门。很多入门文章用train_test_split随机切边这在高维特征下会悄悄泄漏信息随机保留的测试边仍留在训练图里会和训练边互为邻居特征计算时测试信息已经混进来了。我的建议是严格按时间切边表按时间戳排序前 80% 的边进训练子图后 20% 进测试候选边特征只在训练子图上算。edges_sorted edges.sort_values(ts).reset_index(dropTrue) cut int(len(edges_sorted) * 0.8) train_edges edges_sorted.iloc[:cut] test_edges edges_sorted.iloc[cut:] G_train nx.from_pandas_edgelist(train_edges, src, dst, create_usingnx.Graph()) # 测试正样本test_edges 里的边在 G_train 中不存在 # 测试负样本再用 3.2 的 negative_sampling 从 G_train 里采相同数量这样划分的逻辑是链路预测的业务本质就是用历史连接预测未来连接时间切片最贴近上线场景。冷启动节点和永不活跃节点会在测试里暴露出来那些随机划分下永远看不到的失败模式时间切片会诚实地给你看。代价是正样本变少、评估波动变大但一个诚实但波动的指标比一个好看但虚假的指标更值得参照。4. 跑通最小可复现的链路预测从 networkx 基线到 sklearn 分类器现在把所有零件组装起来。目标是让你在本地 python 环境里跑通一整套链路预测先用相似度指标出基线再用 sklearn 分类器出有监督结果最后用 AUC 和 AP 判断好坏。环境直接用 Anacondapip install networkx scikit-learn pandas numpy一次到位。4.1 用 networkx 的相似度指标跑出无监督基线无监督基线不需要训练流程是在训练子图上对测试正样本和采样负样本分别计算相似度分数然后比较两组分数的分布。AUC 的含义可以简化成一句话随机取一对正负样本正样本分数更高的概率。用这个定义可以写一个很轻的评估函数不用依赖roc_auc_score也足够判断方向。import numpy as np def compute_scores(G_train, pos_edges, neg_edges): candidate pos_edges neg_edges pos_scores, neg_scores [], [] for algo in [jaccard_coefficient, adamic_adar_index, resource_allocation_index]: score_map { (u, v): s for u, v, s in algo(G_train, candidate) } pos_scores.append([score_map.get(e, 0.0) for e in pos_edges]) neg_scores.append([score_map.get(e, 0.0) for e in neg_edges]) return pos_scores, neg_scores def fast_auc(pos, neg): pos, neg np.array(pos), np.array(neg) n min(len(pos), len(neg)) if n 0: return 0.5 # 随机配对做 Mann-Whitney 近似避免 O(n^2) 穷举 idx np.random.RandomState(0).choice(n, sizemin(10000, n), replaceFalse) pos_s, neg_s pos[idx], neg[idx] return float((pos_s neg_s).mean() 0.5 * (pos_s neg_s).mean())逻辑说明score_map把每条候选边的分数按节点对存起来避免多次调用 algofast_auc用随机配对近似完整 AUC样本量大时精确 AUC 要两两比较 O(n^2) 次这里压缩到一万次比较误差可接受。跑出来的三个指标各自是一个分数如果 AA 和 RA 的 AUC 显著高于 Jaccard说明网络中度低的节点贡献更大、预测信号藏在“少数关键共同邻居”里这套判断对有监督的特征筛选同样有指导意义。4.2 特征矩阵进 sklearn逻辑回归与随机森林对比有监督步骤就是把上一章的特征 dict 转成矩阵拼上标签丢进分类器。逻辑回归先上快、系数能直接解释、方便排查哪个特征在起作用。随机森林作为对照看非线性相关性能不能再贡献几个点的 AP。特征尺度差异大时逻辑回归必须先标准化否则 C 值的正则化效果会被大数值特征带偏。from sklearn.linear_model import LogisticRegression from sklearn.ensemble import RandomForestClassifier from sklearn.preprocessing import StandardScaler from sklearn.model_selection import cross_val_score # feats: {(u,v): {jaccard: .., adamic_adar_index: .., resource_allocation_index: ..}} # pos_edges/neg_edges 来自上一章 all_edges pos_edges neg_edges X np.array([list(feats[e].values()) for e in all_edges], dtypefloat) y np.array([1] * len(pos_edges) [0] * len(neg_edges)) scaler StandardScaler() X_s scaler.fit_transform(X) lr LogisticRegression(C1.0, class_weightbalanced, max_iter500) rf RandomForestClassifier(n_estimators200, max_depth8, class_weightbalanced, n_jobs-1) for name, model in [(LR, lr), (RF, rf)]: ap cross_val_score(model, X_s, y, cv5, scoringaverage_precision) print(f{name} AP: {ap.mean():.4f} ± {ap.std():.4f})参数说明class_weightbalanced让分类器按反频率加权正样本少时不会一股脑预测负类C1.0是逻辑回归的正则化强度C 越小正则越强特征多、样本少时调小 C 能压住过拟合max_depth8限制树深随机森林在这个深度下通常已经够用深度过大容易在噪声特征上做无用功。交叉验证的average_precision比 accuracy 靠谱因为负样本占比大accuracy 会被“全预测 0”骗到很高。4.3 评估指标选哪个AUC、AP 还是 Top-K 命中率评估指标不是越多越好而是要匹配业务诉求。AUC 回答“模型整体排序对不对”适合做算法选型和调参的粗筛AP 聚焦排序的前段适合“模型给出的高概率边里到底有多少是真的”这个命题Top-K 命中率最贴近业务比如给每个用户推荐 10 个好友命中几个是 KPI 关心的。def topk_hit_rate(scores, true_edges, k10): # scores: {(u,v): score}true_edges: [(u,v), ...] true_set set(tuple(sorted(e)) for e in true_edges) users set() for u, v in true_edges: users.add(u) users.add(v) hits 0 for u in users: cand [] for (a, b), s in scores.items(): if a u and b ! u: cand.append((b, s)) elif b u and a ! u: cand.append((a, s)) cand.sort(keylambda x: -x[1]) hit False for v, _ in cand[:k]: if tuple(sorted((u, v))) in true_set: hit True break hits int(hit) return hits / len(users)这段计算的逻辑是以节点 u 为单位分别对它的 Top-K 预测边和真实新增边做比对命中至少一条就算这个节点的预测算成功。实际业务里AUC 从 0.85 涨到 0.86 未必会带来可感知的推荐量提升Top-K 命中率从 8% 涨到 10% 才是产品能够感知的收益。所以离线评估我通常三个指标都算汇报时主打 Top-K调参时盯 AUC 和 AP。5. 链路预测避坑数据泄漏、负采样失衡与内存爆炸的现场还原链路预测最大的特点就是“离线指标虚高、上线现原形”原因大多集中在数据划分和样本构造上。下面这五条是血泪经验汇总按“现象 → 原因 → 解决”的顺序还原帮你少走弯路。5.1 特征整图计算导致的数据泄漏现象随机 80/20 划分训练时 AUC 0.93时间切片一测掉到 0.68。原因算特征时用的是整张图测试边仍留在图里。比如测试边 (u, v) 在图里算共同邻居时 u 和 v 互为邻居CN 至少是 1模型学到的其实是“是不是测试边”这个作弊信号。解决特征计算只用训练子图 G_train。我后来形成一条铁律——所有特征构建函数第一个参数必须叫 G_train 而不是 G从命名上强制自己不传整图。5.2 随机负采样让指标虚高得离谱现象全图随机采样负样本逻辑回归 AUC 0.90上线后新边召回率不到一半。原因随机负样本集中在低度节点对正样本多是高度节点对模型实际学到的是“度数高的节点更可能有边”这种平庸规律不是网络结构规律。解决负采样改用二跳邻居——即距离为 2 但没有直接连边的节点对这类负样本和真实正样本难分得多模型被迫去学结构特征。def hard_negative_sampling(G, n_neg): nodes list(G.nodes()) neg_pairs set() while len(neg_pairs) n_neg: u random.choice(nodes) if G.degree(u) 0: continue w random.choice(list(G.neighbors(u))) v random.choice(list(G.neighbors(w))) if v ! u and not G.has_edge(u, v): neg_pairs.add((u, v)) return list(neg_pairs)逻辑说明u→w 是存在的边w→v 是存在的边所以 u 到 v 天然是二跳路径如果 u 和 v 没有直接边就是“看起来很近但没连上”的难负样本。代价是 AUC 数字会下降但时间切片下才是真实水平。5.3 稠密邻接矩阵内存爆炸现象五万节点一个np.zeros((N, N))直接把 16G 内存干满进程被杀。原因稠密矩阵是 O(N^2) 存储五万节点就是 25 亿个元素float64 就是 20GB。解决永远不要显式构建邻接矩阵。networkx 的 batch 接口和 scipy 稀疏矩阵都能避开这个问题如果必须用矩阵形式用csr_matrix。十万节点以上建议用 networkx 的同时对候选边做抽样不要把全图所有不存在的边都生成出来。5.4 类别不平衡没处理导致 AP 崩盘现象负样本占比 90%逻辑回归的 accuracy 高达 0.9AP 只有 0.2。原因分类器默认预测概率阈值固定在 0.5负样本绝对优势下样本全被推到 0.5 以下accuracy 骗人AP 曝光真面目。解决训练时设class_weightbalanced或者调决策阈值——在验证集上遍历 0.1 到 0.9选 AP 或 F1 最优的阈值上线。我一般两种都做class_weight 保证训练稳定阈值用验证集再精调一步。5.5 随机划分训练测试和业务时间线错位现象离线随机划分 AUC 0.85灰度上线新边命中率对不上账。原因随机划分时测试边参与了训练图结构时间顺序被打乱——用未来的边去预测过去本身就违背了业务定义。解决严格按时间戳划分前 80% 训练、后 20% 测试特征只在训练时段内计算如果数据没有时间戳至少也要按节点冷启动分组验证模拟“预测新边”的真实场景。这条和 5.1 是同一个病根划分方式一旦错了后面所有指标都是黑匣子。6. 从基线到落地调参顺序、时间切片验证与嵌入方法的取舍6.1 调参顺序先证明基线有效再上复杂模型链路预测落地时调参顺序比调参本身重要。我的习惯是先跑无监督基线确认网络结构有信号再上逻辑回归和随机森林对比最后才考虑图嵌入。逻辑回归阶段先看特征标准化有没有做、class_weight 有没有设、C 值在 0.01 到 10 之间做网格搜索随机森林阶段看 max_depth 和 n_estimators。如果这两个模型卡在某个水平上不涨再怀疑特征不够而不是怀疑模型不行。时间切片验证可以做成一个固定脚本按时间戳打训练测试集、在 G_train 上算特征、输出 AUC/AP/Top-K 三个指标。每次改特征或改参数先跑这个脚本指标没涨就回滚别让模型复杂度的增加伪装成效果提升。这个习惯让我避免了很多次的无效折腾。6.2 图嵌入的投入时机数据规模与业务价值都确认之后图嵌入方法DeepWalk、Node2Vec 这类值得试但条件是数据量够大或节点本身有语义。用 gensim 训练节点向量把边特征换成“起点向量 终点向量 向量内积”再喂分类器是成本适中的进阶路径GNN 需要更大的图和更长的调参周期建议等项目证明了链路预测本身的业务价值后再投入。我自己曾经在相似度基线只有 0.66 的情况下硬上 Node2Vec训了一夜时间切片 AUC 只到 0.67而那段时间明明是在负采样上偷了懒。这个教训让我学会了先把基线和数据问题排查干净再考虑模型复杂度。回想下来链路预测项目里 80% 的提升来自数据划分、负采样和特征选择模型反而是最后做的一步。希望这套踩坑换来的流程能帮到你少走几步冤枉路。本文还有配套的精品资源点击获取