简介这是一份基于 Python 实现的社交网络链路预测算法项目包适用于毕业设计、课程设计及进阶项目开发。代码经过严格测试可安全参考并在此基础上继续扩展。项目围绕变分图自编码器VGAE展开同时提供 Node2Vec、谱聚类以及 Adamic-Adar、Jaccard 系数、优先连接等基线方法便于对比不同链路预测策略的效果。资源共 345 个文件压缩包约 33.94MB主要包含 Python 源码、Markdown 说明文档、PDF 文档、JSON/SVG 等配置与可视化文件以及实验所需的数据文件文档对环境依赖和安装方式也有明确交代。已有 51 人学习下载。下载后可获得完整可运行的实验源码、项目文档与使用教程既能支撑论文复现和算法对比也能为社交网络分析、图嵌入等相关课题提供直接参考。1. 社交网络中的链路预测算法为什么它是毕设和课设的“性价比之王”社交网络中的链路预测算法听起来像个纯研究课题但它在推荐系统、社群发现、风控反欺诈里都在高频使用把当前已知的好友关系当成一张图去预测哪些“还没有连起来”的用户之间最可能产生新连接。对做毕业设计或课程设计的同学来说这个题目的最大优势是“边界清楚、可复现性强”——Python 生态里有现成的图计算库做底座算法从简单到复杂能列出一整张对比表评估指标又直观论文和代码都能撑起来。这篇文章按我自己的落地习惯来写先讲链路预测怎么把社交关系变成数学问题再给出一套可以直接照跑的源码流程接着把评估和项目文档一起做完最后一章讲清楚五个最容易让结果翻车的坑。读者里如果是刚接触图计算的跟着命令能跑通如果已经跑过一些机器学习项目可以重点看第 5 章的边界条件和第 6 章的特征组合思路。2. 把社交网络变成可计算的图链路预测的问题建模与选型2.1 从好友关系到邻接矩阵你手上到底有什么数据做链路预测第一步不是写算法是搞清楚数据长什么样。常见的社交网络数据有两种形态一种是关系表每一行是一条边比如user_id, friend_id另一种是已经是图结构比如 NetworkX 里的 Graph 对象。无论哪种计算机里最终都会转成一张邻接矩阵 A如果用户 i 和用户 j 存在连接A[i][j]1否则为 0。无向社交关系下A 是对称矩阵有向的比如“关注”关系则不一定对称。这里有一个新手最容易忽略的点邻接矩阵的对角线永远是 0也就是不允许用户和自己相连。很多代码在构造训练集和测试集时把对角线也放进负样本里导致评估指标虚高因为“自己连自己”实在太容易分类了。我一般会先做一次清洗去掉自环、去掉重复边、确认节点编号从 0 开始连续否则后面构造矩阵时很容易出界报错。数据清洗完问题就变得很干净。把图中已有的边称为“观测边”把不存在的边称为“非边”。链路预测要做的是从所有“非边”里找出真正会在未来出现的那些。所以它本质上是一个极度不平衡的二分类问题正样本是真实存在但被我们“藏起来”的边负样本是从其余非边里采样出来的。这个视角决定了后面所有评估方式也决定了为什么不能全图一起算相似度——这个问题到第 5 章专门讲。2.2 三类主流算法结构相似性、路径传播与机器学习根据面对的数据规模和可解释性要求链路预测算法大体分成三派。第一派是结构相似性算法也叫启发式算法。它只看局部拓扑特征计算两个节点共同邻居的数量、或者邻居权重的某种聚合代表作是 Common Neighbors共同邻居、Jaccard 系数、Adamic-AdarAA和 Resource AllocationRA。这类算法的优点是好解释、计算快跑在千万级边的图里也没问题缺点是没法利用高阶结构比如两个节点之间间隔两步、三步的路径信息被丢掉了。第二派是路径传播算法以 Katz 指数和 PageRank 变体为代表会考虑路径长度的影响能捕捉到“朋友的朋友的朋友”这种多跳关系但计算复杂度高在稠密图上容易退化。第三派是机器学习方法把多个结构特征拼成特征向量喂给逻辑回归、随机森林或图神经网络效果上限最高但可解释性和计算成本都要打折扣。毕设和课设的常见做法是前两类做主体、第三类做加分项。理由很实际评估表格里需要横向对比 46 种算法结构相似性算法能一口气列出七八种路径算法能补上“全局视角”机器学习方法放在最后说明“还可以更进一步”。我见过不少拿图神经网络当主算法的论文最后卡在训练时间太长、超参数调不动反而丢了基本盘。先跑通三五个结构指标再逐步加复杂度是这条路上最稳的节奏。2.3 为什么推荐优先实现 Common Neighbors 与 Adamic-AdarCommon Neighbors 的定义一句话就能说完节点 u 和 v 的共同邻居越多越可能产生连接。它简单到让人怀疑是否有用但它在社交网络里恰恰很有效因为现实中“共同好友牵线”就是连接产生的主要动力。Adamic-Adar 是在共同邻居基础上做了一次加权度数越大的共同邻居贡献越小因为大 V 用户认识所有人它的中间人作用并不强。这个加权逻辑让 AA 在很多数据集上比 CN 高一截是论文对比表里最值得放的一组。选这两个作为切入点还有一个工程上的好处NetworkX 对它们有现成实现nx.common_neighbors、nx.adamic_adar_index直接返回边列表对应的分数不需要你从零写集合交集。这样你能把精力放在数据划分、评估、结果可视化这些真正容易出错的地方而不是重新实现一个已经被验证过无数次的公式。下面第 3 章给出完整的最小可运行流程全部代码加起来不到一百行跑完就能看到第一份预测结果。3. 最小可运行流水线从 Python 环境到第一份预测结果3.1 环境准备与数据加载用空手道俱乐部数据集先跑通这里不专门讲 python 安装的细节只提醒两个容易翻车的地方一是不要直接用系统自带的 Python 跑老项目依赖版本会互相打架二是用 vscode 配置 python 环境时记得给项目单独建虚拟环境而不是让全局环境越装越乱。下面这份是经过验证的依赖组合直接复制进requirements.txt就行networkx2.8 numpy1.23 pandas1.5 scikit-learn1.2 matplotlib3.6装完后用 NetworkX 内置的karate_club_graph()作为起点。它是一个 34 节点、78 条边的空手道俱乐部社交网络节点代表成员边代表俱乐部外的社交关系。这个数据集在很多论文里被反复使用但它规模太小、社区结构太清晰真实场景下得到的结果会弱不少——所以它只适合用来验证流程不适合作为最终实验的唯一数据集。import networkx as nx import random import numpy as np random.seed(42) np.random.seed(42) G nx.karate_club_graph() print(f节点数: {G.number_of_nodes()}, 边数: {G.number_of_edges()})这段代码把随机种子固定住保证后面每次删边、采样负样本的结果都能复现。图数据加载本身没什么难点重点是确认图是连通的、有没有孤立节点因为连通性直接影响后续所有算法的计算结果。打印出来的节点数和边数应该分别是 34 和 78如果对不上多半是 NetworkX 版本差异导致的默认属性不同不用太纠结。3.2 构造训练集与测试集删边、保连通、采负样本链路预测的标准实验范式叫“边删除法”把已有的边随机藏起来一部分当作测试集正样本剩余的图当作训练图算法只能在训练图上计算相似度然后去预测哪些被藏起来的边会被找出来。这一步里最容易出的问题是删完边后图变得不连通导致后面算最短路径时直接报错。def split_edges(G, test_ratio0.2, max_attempts200): edges list(G.edges()) test_edges set() attempt 0 while len(test_edges) int(len(edges) * test_ratio) and attempt max_attempts: candidate random.choice(edges) temp G.copy() temp.remove_edge(*candidate) if nx.is_connected(temp) and candidate not in test_edges: test_edges.add(candidate) attempt 1 train_edges set(edges) - test_edges train_G G.copy() train_G.remove_edges_from(test_edges) return train_G, list(test_edges) train_G, test_pos split_edges(G, test_ratio0.2) print(f训练边数: {len(train_G.edges())}, 测试正样本数: {len(test_pos)})这段代码的逻辑是每次随机选一条边先尝试从图的副本里删掉它再检查剩余图是否依然连通只有连通才真正把它放进测试集否则重新选。max_attempts200是一个保险丝防止图本身稀疏到无法删出足够边时陷入死循环。这个“删边前先检查连通性”的习惯能在后面省掉一大堆 inexplicable 的报错。测试集正样本的数量你当然希望尽量接近理论值的 15 条但实际会因为连通性检查略少一点这是正常的。负样本的构造同样重要。负样本是训练图上不存在的边数量一般取正样本的 1 到 10 倍。如果取 10 倍评估时可以看到不同算法在大负样本压力下的排序稳定性代价是计算时间上升。入门阶段建议先取 1 倍也就是正负样本各 15 条左右这样 AUC 曲线不会因为样本数量太小而剧烈抖动。non_edges list(nx.non_edges(G)) test_neg random.sample(non_edges, len(test_pos)) print(f测试负样本数: {len(test_neg)})nx.non_edges(G)返回的是完整图上所有不存在的边注意这里用的是完整图 G不是删边后的 train_G。如果误用了 train_G原本被删掉的那 15 条边会出现在非边列表里等于把测试集答案提前泄露给了负样本构造过程AUC 会高得离谱。这个细节在第 5 章会再强调一次。3.3 实现五个基础相似性指标从公式到 NetworkX 调用我一般会一次实现五个指标Common Neighbors、Jaccard、Adamic-Adar、Resource Allocation 和 Katz。前四个能覆盖局部结构视角Katz 补上全局路径视角放在一起对比才有说服力。NetworkX 对前四个有直接实现Katz 没有直接的边级函数我们用矩阵运算自己写一版适用于小网络的代码。def evaluate_method(method, train_G, test_pos, test_neg): pos_scores get_scores(method, train_G, test_pos) neg_scores get_scores(method, train_G, test_neg) return pos_scores, neg_scores def get_scores(method, G, edge_list): if method cn: return [len(list(nx.common_neighbors(G, u, v))) for u, v in edge_list] elif method jaccard: return [score for _, _, score in nx.jaccard_coefficient(G, ebunchedge_list)] elif method aa: return [score for _, _, score in nx.adamic_adar_index(G, ebunchedge_list)] elif method ra: return [score for _, _, score in nx.resource_allocation_index(G, ebunchedge_list)] elif method katz: return katz_scores(G, edge_list, beta0.005) def katz_scores(G, edge_list, beta0.005, max_path5): A nx.to_numpy_array(G) n A.shape[0] score_mat np.zeros((n, n)) path_mat np.eye(n) for _ in range(max_path): path_mat path_mat A score_mat beta ** (_ 1) * path_mat return [score_mat[u, v] for u, v in edge_list]逻辑说明get_scores把不同方法的计算统一封装对调用方只暴露方法和边列表两个参数。NetworkX 的jaccard_coefficient、adamic_adar_index、resource_allocation_index返回一个生成器每个元素是三元组(u, v, score)所以直接取第三项。Katz 的实现思路是累加所有长度为 1 到 max_path 的路径数量并乘以beta的幂次作为衰减因子路径越长贡献越低。beta0.005是一个小而保守的数值防止矩阵幂次累积后数值爆炸对于 34 节点的小图这个值很安全但如果换到大图上你需要把 beta 调得更小或者减少max_path。五个指标的参数差异集中在两点ebunch决定计算哪些边通常传入边列表beta只影响 Katz它控制多跳路径的衰减速度调大一点能增强全局结构的影响力但也更容易过拟合到噪声路径。运行完这段代码你就有了五组正负样本分数下一章直接用它算 AUC。4. 评估指标与项目文档AUC 怎么算报告怎么写才不扣分4.1 用采样法实现 AUC 与 PrecisionK链路预测的评估指标里AUC 和 PrecisionK 是最常用的两个。AUC 的含义是随机从正样本里取一条边、随机从负样本里取一条边正样本得分高于负样本得分的概率。这个定义不依赖具体分数阈值的设定所以比“算准确率”要稳定得多。实现上可以直接用刚才的正负样本分数列表做随机抽样比较不用去调 sklearn 的接口逻辑本来就不复杂。def calc_auc(pos_scores, neg_scores, iter_num10000): cnt 0 for _ in range(iter_num): p random.choice(pos_scores) n random.choice(neg_scores) if p n: cnt 1 elif p n: cnt 0.5 return cnt / iter_num for method in [cn, jaccard, aa, ra, katz]: pos, neg evaluate_method(method, train_G, test_pos, test_neg) print(f{method:8s} AUC {calc_auc(pos, neg):.4f})这里把iter_num设为 10000是采样次数不是样本数。每一轮都从所有正样本分数和负样本分数里各抽一个出来比大小最后返回的比例就是 AUC 估计值。随机种子的作用在这里体现得更明显如果你不固定随机种子同一个方法每次跑出来的 AUC 都会有零点几的波动放在论文里就说不清了。PrecisionK 衡量的是把边上分数排序后取前 K 条其中真实正样本占多少。实现上需要先把正负样本合在一起、记录标签、按分数降序排序再取前 K 个统计。def calc_precision_at_k(pos_scores, neg_scores, k10): pairs [(s, 1) for s in pos_scores] [(s, 0) for s in neg_scores] pairs.sort(keylambda x: x[0], reverseTrue) top_k pairs[:k] return sum(label for _, label in top_k) / k for method in [cn, jaccard, aa, ra, katz]: pos, neg evaluate_method(method, train_G, test_pos, test_neg) print(f{method:8s} P10 {calc_precision_at_k(pos, neg):.2f})P10 的合理取值范围在你这种 15 条正样本的设定下一般是 0.50.8如果出现 1.0 的满分成绩先别高兴大概率是泄露了。K 的取值由你的图大小决定小图设 10 到 20大图可以设 100 起步。PK 比 AUC 悲观得多也更加贴近真实使用场景——因为落地时系统只推送 Top K 个推荐关系而不是一次性评估全部候选。4.2 项目目录源码、文档、测试各归其位一个能交给老师或评审的 Python 项目目录结构不是随手建的它本身就在证明你的工程能力。常见的做法是分成data/、src/、docs/、tests/四块外加一个顶层的README.md。源码里再把数据集加载、算法实现、评估脚本、可视化分文件放避免一个两百行的大文件从头写到尾。social_link_prediction/ ├── data/ # 原始关系表CSV 格式 │ └── social_graph.csv ├── src/ │ ├── __init__.py │ ├── data_loader.py # 读取关系表、构造 NetworkX 图 │ ├── algorithms.py # 五个相似性指标的封装 │ ├── evaluate.py # AUC 与 PrecisionK │ ├── visualize.py # 渲染预测结果图 │ └── main.py # 一键运行入口 ├── docs/ │ ├── 项目报告.md │ └── 使用教程.md ├── tests/ │ ├── test_algorithms.py │ └── test_evaluate.py ├── requirements.txt └── README.md这样的层级有两个好处第一老师在检查时能一眼看出你区分了“数据、算法、评估、文档”四个维度第二你自己在调 bug 时不用来回滚一个巨大的文件改algorithms.py不影响evaluate.py。main.py的定位是“一键运行所有实验并输出对比表”里面不要写任何算法逻辑只做流程编排。4.3 使用教程怎么写才不像应付使用教程这部分很多同学直接贴一遍运行结果就交了这是比较吃亏的。使用教程的核心不是展示结果而是让一个从没看过你代码的人能在 10 分钟内在自己电脑上跑出同样的结果。最低限度要包含三件事环境安装命令、运行入口命令、每个参数的作用和默认值。下面是我通常会用的一种写法。## 运行步骤 1. 创建虚拟环境并安装依赖 bash python -m venv venv source venv/bin/activate # Windows 下用 venv\Scripts\activate pip install -r requirements.txt 2. 准备数据将 user_id, friend_id 格式的 CSV 放到 data/ 目录 默认列名是 source 和 target。 3. 启动实验 bash python src/main.py --data data/social_graph.csv --test-ratio 0.2 --method all 4. 查看输出程序会在控制台打印每个方法的 AUC 和 P10 同时在 output/ 目录下生成预测边列表与可视化图片。这里面的关键不是命令本身而是你把“数据格式”和“参数默认值”写明白了。参数说明部分要写成表格--test-ratio默认 0.2控制删边比例取值范围 0.1 到 0.3--method可选cn/jaccard/aa/ra/katz/all默认all。这样做最大的好处是答辩时不用临时翻代码回忆参数直接照着文档说。另外文档里一定要说明随机种子在哪设置否则别人复现不出你的 AUC 数值会怀疑你的结果真实性。5. 链路预测避坑5 个让结果翻车的常见问题5.1 用完整图算特征导致标签泄露现象AUC 高到不真实明明是很简单的 Common Neighbors随便跑跑都有 0.95 以上。原因计算相似度时用了删除边之前的完整图 G被删掉的测试边仍然参与共同邻居计数相当于考试前把答案夹在草稿纸里。负样本构造时也可能误用删边图导致正样本混进负样本集合。解决所有特征计算必须严格基于训练图train_G只有在采样负样本时才可以用完整图G获取真实非边集合。最稳妥的做法是在get_scores函数内部只接收train_G全项目禁止把G传给特征计算函数。5.2 Jaccard 和 RA 在稀疏区域出现 nan现象程序不报错但打印出来的 AUC 是 0.5 上下个别分数是nan。原因Jaccard 的分母是 u 和 v 的度数和减去共同邻居数当两个节点都出现在非边列表里、且各自只有一个邻居时分母可能变成 0Resource Allocation 也有类似情况。NetworkX 在遇到这种情况时会返回inf或nan而nan参与比较时永远返回 False直接把 AUC 拉低到随机水平。解决在get_scores返回前加一层清洗把nan和inf替换为 0。这个操作看起来很小但它是新手最容易忽略的细节。def clean_scores(scores): return [0.0 if (s is None or s ! s) else s for s in scores]5.3 删边后图变得不连通现象程序在计算 Katz 时抛出NetworkXError: Graph is not connected或者某些节点的分数永远是 0。原因随机删边不适合稀疏图。社交网络往往存在桥接节点删掉桥接边后图被切成两个连通分量路径类算法直接失去全局计算能力。解决在删边循环里加连通性检查第 3 章的做法或者退一步只在最大连通子图内做实验。如果你做的是大图上的实验跑一次全图连通性检查的成本不高但能避免后面一连串连锁报错。5.4 AUC 采样次数不够导致结论不稳定现象同一份代码、同一个数据集第一次跑 AA 是 0.82第二次变成 0.76第三次又回到 0.80。原因AUC 的采样估计有随机性尤其是测试集只有 15 条正样本时随机抽 10000 次比较也会有明显方差。另一个隐患是用了不同的随机种子。解决固定种子之外把采样次数提高到 50000 到 100000并且多次运行取平均值。论文里报告的数字应当是三次运行的平均值而不是某一次的运气值。5.5 测试集太薄导致 PrecisionK 没有区分度现象五种方法算出来 P10 几乎一样都是 0.6 或 0.7排不出优劣。原因30 个样本的规模太小而 P10 只取前 10 个随机波动完全压过了算法差异。小图上天然容易饱和这不是算法没用是评估粒度不够。解决换用更大规模的公开数据集比如从 SNAP 下载的 Facebook 或 Email-EU 网络或者降低 K 值比如在 30 样本场景下看 P5 而不是 P10。如果论文里只能用 Karate 数据集建议把实验重心放在 AUC 对比上PK 只作为补充。6. 更进一步把多指标特征喂给分类器并可视化预测结果跑完五个基础指标后你手里的正负样本已经有了五组分数。与其停在“哪个指标更高”的对比层不如往上走一步把这五个分数拼成特征向量交给逻辑回归或随机森林训练一个分类器。这种做法在很多公开数据集上能把 AUC 再往上拉 510 个点而且它刚好是论文里“基于机器学习方法的链路预测”那一节的内容属于不另起炉灶的进阶版。from sklearn.linear_model import LogisticRegression from sklearn.model_selection import cross_val_score def build_feature_matrix(train_G, pos_edges, neg_edges, methods): all_edges pos_edges neg_edges labels [1] * len(pos_edges) [0] * len(neg_edges) feats [] for method in methods: scores, _ evaluate_method(method, train_G, all_edges, []) feats.append(scores) X np.column_stack(feats) return X, labels X, y build_feature_matrix(train_G, test_pos, test_neg, [cn, jaccard, aa, ra, katz]) clf LogisticRegression(max_iter1000) auc_cv cross_val_score(clf, X, y, cv5, scoringroc_auc) print(f分类器 5 折交叉验证 AUC {auc_cv.mean():.4f})这里要注意的是训练分类器时同样必须用训练图算特征不能用完整图否则标签泄露问题会原封不动地带到机器学习阶段。交叉验证的cv5对小样本来说比较合适30 条样本分成 5 折还能保持每折有正负样本各 3 条如果你的数据量大可以调到 10。逻辑回归的正则化参数C默认 1.0在样本量很小的时候不用刻意调先看交叉验证结果稳不稳定。最后把预测结果画出来。用 NetworkX 的draw_networkx_edges分别用红色画真实测试边、用蓝色画预测的高分边旁边配一个热度图展示相似度矩阵整个项目报告立刻有了可视化支撑。这是我做毕设时养成的习惯任何图算法项目先跑通数字再画图因为图画完你才能真正看出算法在哪类节点上失灵——那些被预测为高连接但实际没有连边的节点对往往是下一步特征工程的关键线索。希望这些经验能帮你省下几个晚上的调试时间也希望你能在这个题目里找到自己真正感兴趣的那条技术线。本文还有配套的精品资源点击获取