简介基于Python实现的社交网络链路预测算法完整项目包含源码、项目文档与使用教程适用于毕业设计、课程设计和项目开发。项目覆盖变分图自编码器VGAE、Node2Vec、谱聚类以及Adamic-Adar、Jaccard系数、优先连接等基线方法可支撑链路预测实验对比与结果分析。环境依赖已明确列出Python 3.6.6、TensorFlow 1.12.0、NetworkX等并提供setup.py安装配置便于快速搭建。资源包共345个文件大小33.94MB。文件类型以pkl、txt、svg、json、py、pdf、png为主pkl为序列化特征数据edgelist/edges为图边集合py为算法源码pdf为项目文档svg/png为可视化输出结构清晰方便按模块检索。目前已有51人学习。源码经严格测试可放心参考和二次开发结合内置的Facebook ego网络数据适合深入理解节点嵌入与链路预测方法。1. 链路预测不是玄学从社交网络里“猜”出下一根连线你在社交 App 上刷到“你可能认识的人”觉得它像个黑匣子其实背后一类最常见、最朴素的算法就叫链路预测。给定一张社交网络图——节点是人、边是关注或好友关系——链路预测要做的事就是判断哪些“暂时没有连接”的节点对未来最有可能产生一条边。这个标题里的社交网络、链路预测算法和Python 源码凑在一起解决的正是毕业设计里那种“有数据、有算法、有评估、能写文档”的完整闭环需求课程设计能跑通最小示例毕业设计能扩成对比实验项目开发能留出接口接真实数据。适合谁准备交毕设的本科生、被课设卡住的高年级学生以及想快速上手一个图算法 Demo 的开发者。一句话链路预测不是靠直觉猜是靠网络结构算出一个可排序、可验证的分数。2. 从共同邻居到资源分配先选对指标再谈写代码2.1 为什么相似性指标是链路预测的“第一类武器”链路预测的算法家族大致可以分成三类基于相似性指标的方法、基于矩阵分解或概率模型的方法、基于图嵌入和神经网络的方法。对于课程设计和大多数本科毕业设计第一类是最值得先做透的——理由很现实数据量小、可解释性强、代码量可控、指标对比方便。你不需要一台 GPU 服务器也不需要攒几十万条边一张几百个节点的小网络图就能把结论讲清楚。而那些动不动就上 GNN 的方案数据不够时反而容易翻车评估指标还不一定比朴素指标好看。相似性指标的核心思想异常直白两个节点未来会不会连边取决于它们当前在结构上有多“像”。最经典的Common Neighbors共同邻居就用一句话概括——两个人共同好友越多越可能认识。这个指标在社交网络里天然成立因为现实中社交关系的建立大量依赖“朋友的朋友”这条路径。而 Jaccard、Adamic-AdarAA、Resource AllocationRA都是在共同邻居基础上做修正Jaccard 用共同邻居数除以两个节点的度并集把“大家都认识很多人”的干扰消掉AA 对共同邻居里度特别大的节点降权因为一个拥有 5000 好友的人出现在你的共同好友列表里说明不了太多问题RA 则进一步模拟资源在节点之间传播时的分配比例。选型时的一个通用建议是数据偏稀疏、节点度数差异大优先试 RA 和 AA数据均匀稠密CN 和 Jaccard 已经够用。下面这张表可以放在毕设文档的算法介绍小节里直接参考。指标计算方式复杂度擅长场景弱点Common Neighbors共同邻居数O(d(u)d(v))稠密社交图、快速基线偏好高度数节点Jaccard共同邻居/并集度数同上度数差异大时更公平稀疏图下区分度低Adamic-Adar对每个共同邻居取 1/log(度) 求和O(d(u)d(v))社交网络、引文网络需要对数运算略慢Resource Allocation对每个共同邻居取 1/度 求和O(d(u)d(v))稀疏网络、传播场景对极端度数敏感2.2 训练集和测试集怎么切这一步错了后面全白做链路预测里的“训练/测试”划分和传统机器学习不一样。传统分类是随机抽行链路预测则是在一张图上“遮住”一部分边。常见做法有两种。第一种是时间切分如果数据带时间戳取前 80% 时间的边作为训练图后 20% 的边作为测试正样本。这种切分最符合“预测未来”的业务语义也最容易被答辩老师认可。第二种是随机遮边把所有边随机分成训练边和测试边比例通常设为 9:1 或 8:2。随机遮边实现简单但有一个经典大坑——测试集中的边一旦参与共同邻居计算就相当于把答案提前泄露给了模型后面讲避坑时我会详细展开。不管用哪种切分负样本的构造都容易被低估。链路预测的评估需要正样本未来真实出现的边和负样本一直没出现的边但一个包含 n 个节点的图理论上有 n*(n-1)/2 个节点对其中绝大多数都是负样本。直接全量塞进评估计算量爆炸而且负样本里大量“八竿子打不着”的节点对会让指标虚高——因为任何一个算法都能轻松判断两个距离十万八千里的节点不会连边这有什么可预测的业界通行做法是“负采样”从不存在边的节点对里随机抽出一批数量与正样本相当或略多抽样时限定在“二跳邻居”范围内更公平。也就是只考察“距离为 2、中间隔着一个人”的节点对因为距离超过 2 的节点对在社交场景里基本没有连边可能预测它们没有意义。2.3 评估指标为什么选 AUC 而不是准确率链路预测论文里出现频率最高的评估指标是 AUCArea Under the Curve而不是准确率。原因在于正负样本天然不平衡即使随机猜准确率也可能高达 90% 以上因为负样本太多。AUC 的含义是随机从正样本中选一条边随机从负样本中选一条不存在的边模型给正样本打分高于负样本的概率。AUC 越接近 1 越好0.5 等于随机猜。这个指标的好处是它和阈值无关不需要你纠结“分数超过多少算预测成功”。同时再配一个 PrecisionK把所有预测分数降序排列取前 K 条看里面有多少条真的出现在了测试集中。两个指标一起用一个看整体排序质量一个看前几个推荐是否靠谱正好对应社交网络里“推荐列表”和“全量预测”两个场景。3. 用 Python 实现链路预测从读数据到出 AUC 的完整代码3.1 数据准备把社交关系整理成边表这一步是复现链路预测的起点也是很多新手第一个翻车点。你需要准备一张图最常见的数据格式是 CSV 边表每一行两条节点 ID表示一条边。用 NetworkX 读入变成Graph对象。下面这段代码处理的是无向无权图如果数据里带权重可以在nx.read_edgelist里指定dataTrue。import networkx as nx # 读取边表节点 ID 按字符串处理避免 int/str 转换麻烦 G nx.read_edgelist(social_network.csv, delimiter,, nodetypestr) print(节点数:, G.number_of_nodes()) print(边数:, G.number_of_edges()) # 检查是否有孤立节点链路预测里孤立节点几乎没有预测价值 isolated list(nx.isolates(G)) print(孤立节点数:, len(isolated))这里read_edgelist把每个节点当作字符串读入后面所有操作都基于字符串 ID不容易在类型转换上报错。isolates检查很有必要一张社交网络里如果有大量从不出现在任何边中的孤立点它们和任何节点的共同邻居都是 0在评估阶段只会拖慢速度、拉低指标实际项目中通常会先把它们过滤掉。如果你手里的数据是邻接矩阵或者 JSON 格式先统一转成边表 CSV 再进行这一步后面所有代码都会省事很多。3.2 划分训练集和测试集遮边时要保住连通性下面这段代码实现了随机遮边划分但加了一个重要保护——保证训练图不产生过多孤立节点。因为一个节点连向训练图的边全被遮掉后它在训练图里就成了孤立点共同邻居直接归零预测结果就是 0这会让评估结果严重失真。import random def train_test_split_preserve(g, test_ratio0.1, seed42): random.seed(seed) edges list(g.edges()) random.shuffle(edges) test_count int(len(edges) * test_ratio) test_edges set(edges[:test_count]) train_edges set(edges[test_count:]) train_g nx.Graph() train_g.add_nodes_from(g.nodes()) train_g.add_edges_from(train_edges) # 过滤掉在训练图中已经孤立的节点评估时不考虑它们 valid_nodes {n for n in train_g.nodes() if train_g.degree(n) 0} train_g train_g.subgraph(valid_nodes).copy() return train_g, test_edges, valid_nodes参数test_ratio控制在 0.1 到 0.2 之间太小测试样本不足评估结果抖动大太大训练图信息损失严重。seed固定随机种子非常关键否则每次跑结果都不一样毕业设计里“可复现实验”这条要求过不了。过滤孤立节点的操作发生在划分之后别忘了test_edges里的边如果涉及被过滤节点后续评估时要跳过。3.3 相似性指标实现CN、Jaccard、AA、RA 逐个算接下来是核心部分把所有候选节点对的相似性分数算出来。注意候选节点对来自训练图中“不直接相连”的节点但我们要给它们的分数排序分数高的视为更可能在未来连边。import math def similarity_scores(g, node_pairs, methodcn): scores {} for u, v in node_pairs: u_neighbors set(g.neighbors(u)) v_neighbors set(g.neighbors(v)) common u_neighbors v_neighbors if method cn: s len(common) elif method jaccard: s len(common) / max(len(u_neighbors | v_neighbors), 1) elif method aa: s sum(1.0 / math.log(1 g.degree(w)) for w in common) elif method ra: s sum(1.0 / g.degree(w) for w in common) else: raise ValueError(未知指标: method) scores[(u, v)] s return scoresg.neighbors(u)在 NetworkX 里返回一个迭代器转成 set 主要是为了快速求交集和并集。math.log(1 g.degree(w))里的1是为了防止度数为 1 时出现 log(0) 除零错误——这是很多人初次实现 AA 会踩的细节。jaccard里分母max(..., 1)同理防止并集为 0 出现除零。复杂度上CN 和 Jaccard 的主成本在len(common)的集合运算在几千条边的规模下跑起来完全无压力上万节点时建议先nx.ego_graph缩小范围。四个指标的返回结构完全一致后面换指标评估只需要改method参数。3.4 负采样与正样本构造只选“差一跳”的节点对链路预测里“预测哪些未来出现的边”只是问题的一半另一半是拿什么做负样本。如下代码构造了两种负样本全随机抽样和二跳邻居内抽样。全随机好理解从所有不存在的边里随机抽二跳邻居是指两个节点之间有共同邻居但当前没有直接连边也就是“朋友的朋友”。二跳负采样实现的原理是对训练图里每条边 (u, w)再从 w 的邻居里取一个 v 使得 (u, v) 不在图中这样 u 和 v 距离为 2。它更贴近真实场景因为社交网络里连不上边的节点对实在是太多了算法真正需要分辨的是“看起来可能认识”的节点对到底谁更可能认识。def sample_negatives(g, positive_pairs, num_negativesNone): non_edges [] nodes list(g.nodes()) visited set(positive_pairs) if num_negatives is None: num_negatives len(positive_pairs) attempts 0 while len(non_edges) num_negatives and attempts num_negatives * 20: attempts 1 u random.choice(nodes) # 随机挑一个邻居的邻居保证距离为2 u_nbrs list(g.neighbors(u)) if not u_nbrs: continue w random.choice(u_nbrs) w_nbrs list(g.neighbors(w)) if not w_nbrs: continue v random.choice(w_nbrs) pair tuple(sorted([u, v])) if pair (u, v) or pair in visited: continue if g.has_edge(u, v) or g.has_edge(v, u): continue non_edges.append(pair) visited.add(pair) return non_edges这段代码每一轮尝试选一个节点u跳到它的邻居w再跳到w的邻居v于是u和v天然隔了一个w属于二跳关系。visited集合用来去重同时过滤掉已经是正样本的节点对。attempts上限是num_negatives * 20防止死循环。当图太稀疏、二跳邻居不足时这个采样策略可能凑不够数常见的兜底方案是退回全随机采样补足差额毕设文档里可以写明“二跳为主全随机兜底”这个策略。3.5 评估算 AUC 和 PrecisionK有了正样本测试集中的边、负样本和每个节点对的分数接下来就是评估。AUC 的朴素实现是逐对比较正样本数一万、负样本数一万时逐对比较就是一亿次循环跑起来非常慢。更高效的做法是用随机抽样代替全量比较随机抽一部分正负对比较分数大小估计出“正样本分数高于负样本”的概率。下面代码实现了这个思路。import random def evaluate_auc(scores, positive_pairs, negative_pairs, sample_times100000): hits 0 comparisons 0 for _ in range(sample_times): pos random.choice(positive_pairs) neg random.choice(negative_pairs) # 没有分数的按 -inf 处理即直接认输 s_pos scores.get(pos, float(-inf)) s_neg scores.get(neg, float(-inf)) if s_pos s_neg: hits 1 elif s_pos s_neg: hits 0.5 comparisons 1 return hits / comparisons def precision_at_k(scores, positive_pairs, k100): sorted_pairs sorted(scores.items(), keylambda x: x[1], reverseTrue) top_k sorted_pairs[:k] hit 0 for pair, _ in top_k: # 只统计两个节点都在有效集合里的预测 if pair in positive_pairs or (pair[1], pair[0]) in positive_pairs: hit 1 return hit / khits 0.5处理的是分数相等的情况——AUC 定义中相等按 0.5 算。sample_times设到 10 万次基本够稳定AUC 的波动能控制在 0.01 以内如果想精确复现实验结果可以设为 100 万次。precision_at_k里的sorted会返回从大到小的所有键值对如果候选节点对有几十万条耗时会明显建议先用heapq.nlargest(k, ...)代替全排序代码里注释一下即可。4. 链路预测避坑指南五个让 AUC 虚高或归零的经典事故4.1 数据泄露测试边混进了共同邻居计算AUC 虚高到 0.95现象测试集切分完AUC 高达 0.95 以上你甚至开始怀疑论文里的指标是不是都这么容易。换一个指标跑还是高换一个随机种子也高。原因划分时只把测试边从训练图里“摘出来”用于评估但计算共同邻居时用的是全量图、或者下一次运行又直接读入了完整边表。测试边的端点还留在训练图里测试边本身参与了邻居集合构建相当于告诉模型“这两个人已经通过某条路径连上了”。解决务必用只包含训练边的train_g计算邻居集合和相似性分数不要在函数内部再去read_edgelist读全量数据。写完评估后做一个快速自检随机挑几条测试边打印它们的共同邻居是否有通过测试边本身搭桥的路径如果有查代码。4.2 随机遮边把图拆成了碎片大量节点分数恒为 0现象跑完评估AUC 只有 0.52和随机猜差不多打印候选节点对里分数非零的比例不足 5%。原因遮边比例设到 20% 甚至更高后很多节点的所有边都被遮掉了在训练图里变成孤立点和谁都算不出共同邻居。分数全是 0排序等于随机。解决训练之前先过滤degree 0的节点并且通过subgraph只保留最大连通分量。同时把test_ratio控制在 0.10.15大于 0.2 的遮边比例在社交网络数据上通常都会引发严重的连通性下降。4.3 负样本采样太“容易”算法不用学就赢了现象AUC 高得离谱但把预测出来的 Top-K 边打印出来一看全是“两位共同好友都超过 30 个”的高度数节点推荐结果毫无惊喜换随机分数排序也能得到类似结果。原因负样本全部来自全图随机抽样绝大多数负样本节点对相距很远、共同邻居为 0。模型只需要学会“共同邻居数大于 0 就加分”就能把 AUC 刷到 0.9 左右而这根本体现不出算法优劣。解决负采样改成上一节代码里的二跳邻居抽样。二跳样本的节点对都有至少一个共同邻居模型必须进一步分辨“哪些共同邻居更重要”AUC 会回落到一个真实水平通常在 0.70.85 区间。这也是最容易让答辩老师眼前一亮的改进点。4.4 NetworkX 版本差异API 返回迭代器误判导致结果飘忽现象代码在 Jupyter Notebook 里跑得好好的换到命令行脚本再次运行common_neighbors报错“TypeError: generator object is not subscriptable”或者在某些节点上计算结果时好时坏。原因NetworkX 2.x 到 3.x 版本迭代中不少函数从返回列表改为返回迭代器g.neighbors()、nx.common_neighbors()都是重灾区。迭代器只能遍历一次如果你在循环里多次复用第二次就是空结果。解决所有邻居相关返回统一在外面套一层set(...)确保可以多次遍历。同时在requirements.txt里锁住networkx3.0别再让环境自动升级引入莫名其妙的行为差异。4.5 精度问题分数相等但排序不稳定PrecisionK 抖动剧烈现象固定随机种子跑出来的 PrecisionK 每次不一样有时差 10 个百分点。原因排序时没有处理分数相等的情况sorted()在相等键值对上的顺序由内存地址或迭代顺序决定Python 里不可复现。解决按分数降序后对相同分数再按节点 ID 的字典序升序作为次级排序键。代码写法是sorted(scores.items(), keylambda x: (-x[1], x[0][0], x[0][1]))这样相同分数下谁的 ID 小谁靠前排序结果完全确定。5. 从算法到项目面向毕设和课设的代码结构与文档组织5.1 目录怎么设计答辩老师想看到“工程感”很多同学做课程设计喜欢一个.ipynb从头写到尾这本身没问题但如果题目命中“源码 项目文档 使用教程”这个组合说明评审方期待你交出一份可以运行的完整项目而不是一段散装代码。常见做法是把项目按模块拆成五个部分data/放原始数据和预处理脚本src/放核心算法docs/放设计文档和实验报告scripts/放跑实验的入口脚本requirements.txt锁住依赖版本。下面这份结构可以直接抄它是这一类项目最常见也最稳妥的组织方式。目录/文件作用data/存放边表 CSV、预处理脚本src/graph_loader.py负责读数据、过滤孤立节点、切分训练测试集src/indicators.py实现 CN / Jaccard / AA / RA 指标src/evaluation.py实现负采样、AUC、PrecisionKscripts/run_experiment.py串联全流程接收命令行参数docs/设计文档.md需求、算法原理、实验方案、结果分析README.md环境配置、运行方式、目录说明requirements.txtnetworkx / pandas / matplotlib 等固定版本5.2 入口脚本怎么设计argparse 参数化一次跑完四组实验实验入口脚本的价值在于“一条命令复现整个实验”。用argparse接收数据路径、算法名称、负采样策略、随机种子这些参数默认值设好别人拿到项目可以直接python scripts/run_experiment.py --data data/example.csv跑通。下面这段代码展示了入口脚本的主线逻辑省略了函数内部实现只保留流程骨架方便你替换成自己的函数名。import argparse from src.graph_loader import load_graph, split_data from src.indicators import similarity_scores from src.evaluation import sample_negatives, evaluate_auc def main(): parser argparse.ArgumentParser(description链路预测实验入口) parser.add_argument(--data, requiredTrue, help边表CSV路径) parser.add_argument(--method, defaultaa, choices[cn, jaccard, aa, ra]) parser.add_argument(--test-ratio, typefloat, default0.1) parser.add_argument(--neg-strategy, defaulttwo_hop, choices[two_hop, random]) parser.add_argument(--seed, typeint, default42) args parser.parse_args() graph load_graph(args.data) train_g, test_edges, valid_nodes split_data(graph, args.test_ratio, args.seed) # 候选节点对 训练图中不相连但端点都在 valid_nodes 中的节点对 candidates build_candidates(train_g) scores similarity_scores(train_g, candidates, methodargs.method) pos_pairs [(u, v) for u, v in test_edges if u in valid_nodes and v in valid_nodes] neg_pairs sample_negatives(train_g, pos_pairs, strategyargs.neg_strategy) auc evaluate_auc(scores, pos_pairs, neg_pairs) print(fmethod{args.method} auc{auc:.4f} pos{len(pos_pairs)} neg{len(neg_pairs)}) if __name__ __main__: main()build_candidates这一步要特别注意复杂度全图所有不相连节点对数量巨大可以用nx.non_edges()但这个接口在大图上极慢。实际用的时候建议把候选集限定在“共同邻居不为空”的节点对里即先找二跳邻居再算相似度能省下 90% 以上的计算量。这也暗示了链路预测的现实工程做法——不是所有不相连的节点对都有预测必要先筛“够得着”的再算“谁更可能”。6. 把 AUC 0.85 的结果讲出说服力对比实验与验证技巧毕设答辩里链路预测项目的说服力不来自“我的 AUC 是 0.8721”而来自“我知道这个数字在什么条件下成立、换一个条件会怎么变”。一个值得做进文档的进阶实验是“指标 × 负采样策略”的交叉对比。你可以用同一份数据、同一个随机种子跑 CN、Jaccard、AA、RA 四种指标分别搭配全随机负采样和二跳负采样出一张 4×2 的 AUC 表格。你会几乎必然看到全随机负采样给出的 AUC 普遍虚高 0.050.1而二跳负采样下 AA 和 RA 通常会略优于 CN 和 Jaccard。这个现象本身就是很好的分析素材说明在不同结构密度下不同的降权策略各有优劣而不是简单说“RA 最好”。我个人的习惯是在跑结果之前先打印一份正样本和负样本的度分布直方图——如果正样本的度数显著高于负样本说明划分本身有偏差需要重新做层化抽样来校正。这一步经常能提前暴露数据泄露问题比事后查代码要快得多。进阶方向可以加一个 Katz 指标做基准。Katz 不是只看共同邻居而是计算所有路径长度的加权和长度越长的路径权重越低。它在 NetworkX 里没有现成函数需要自己写sum(beta**k * num_paths_k)其中num_paths_k可以通过邻接矩阵的 k 次方获得。对这个标题里的源码项目来说把 Katz 作为第五个指标放进对比表能体现你对算法谱系的完整理解。再往前走一步可以用 Node2Vec 嵌入节点向量后计算余弦相似度作为“图嵌入基线”与相似性指标对比。但要注意Node2Vec 在小数据上少于 500 节点效果往往不如简单的 AA跑出来的结果可能反而拉低论文说服力所以用之前先想清楚数据规模是否支持。验证方法上建议固定随机种子后至少跑三组不同 seed把 AUC 的均值和标准差写进报告。标准差超过 0.02 就说明数据量太小或实验设计不稳需要加大测试集比例或者换更稳定的划分策略。最后提一个贯穿所有实验的习惯每跑完一组都把预测分数最高和最低的 10 条边打印成可读的“用户 A — 用户 B分数 0.832”格式。这不仅能帮你在文档里放一张“预测结果示例”表增强答辩时的直观感还能在早期揪出异常样本——比如曾经有个项目里分数最高的几条边全是同一个人在不同子图里的重复 ID过滤时拼写不一致导致脏数据一打印就现出原形了。做算法项目代码能跑只是开始能解释清楚“为什么是这个分数”才是毕设的加分项。链路预测这套从数据划分、指标计算到评估对比的流程希望帮到你。本文还有配套的精品资源点击获取