简介面向网络科学、数据挖掘研究者和 Python 开发者此压缩包聚焦链路预测中推测尚未发现连接的问题覆盖从数据清洗、算法实现到结果分析的全流程。包体共 23 个文件整体仅 86KB核心为 10 个 Python 脚本分别承担图结构定义、共同邻居CN与资源分配RA的改进算法、基于相似度的 Jaccard/Adamic-Adar 方法、测试评估及可视化等任务另有 2 张训练集分布图、若干 XML/IML 工程配置便于在 IDE 中直接加载调试。对于刚接触链路预测的读者可从测试脚本和通用工具模块入手快速理解算法评估与数据预处理流程对于有基础的研究者相似度算法和多个改进版本提供了方法对照与优化思路。整体相当于一套可运行的链路预测实验模板能减少从零搭建环境的时间。已有 973 人学习下载适合作为网络分析课程设计、论文复现或工程实践的参考资料。1. 链路预测这套Python源码包到底解决什么问题在社交App的“你可能认识的人”、电商的“猜你喜欢”、PubMed的文献推荐背后链路预测link prediction是那个被反复调用的基础算法你已经知道了图上的几乎全部结构现在要预测哪些边还没出现、哪些边在未来最可能被补上。这份LinkPrediction.rar是一套以Python写的链路预测完整工程里面不是单个脚本而是从图数据结构、相似度算法、改进模型到测试评估、可视化的一条龙代码。核心文件包括graph.py图结构、improved_cn.py和improved_ra.py两个改进算法、similarity_based.py多算法集成、test.py/evaluate.py训练与评估以及data_analysis.py结果可视化。它适合两类人一是刚把networkx玩熟、想深入看算法实现的python学习者二是需要在自有数据上快速跑出基线预测结果的数据分析从业者。2. 数据基座graph.py、utils.py与pre_m.py如何支撑所有算法链路预测的全部计算都建立在图结构之上。你要预测的不是向量不是文本是节点和边的关系。所以这套代码包把“图怎么存”“公共函数放哪”“数据怎么洗净”拆成了三个文件graph.py、utils.py和pre_m.py。压缩包里还带着.idea目录和*.iml那些是PyCharm的工程配置不影响代码运行拿到手之后可以先忽略直接看这三个核心模块。2.1 graph.py邻接表还是邻接矩阵决定后面所有算法跑多快graph.py是这套工程的数据基座。它定义了一个图类负责两件事存储节点和边的映射关系以及对外提供度、邻居、邻接关系等查询接口。链路预测里的大多数算法比如共同邻居、Adamic-Adar、资源分配本质上都在反复访问“某节点的一阶邻居集合”所以这边存储结构的选择直接决定算法的复杂度。常见实现是双字典一个存节点到邻居集合的映射一个存节点度避免每次都去遍历整张边表。class Graph: def __init__(self): self.nodes set() self.edges set() self.adj dict() # 节点 - set(邻居) self.degree dict() # 节点 - 度 def add_edge(self, u, v): self.nodes.add(u) self.nodes.add(v) self.edges.add((u, v)) self.edges.add((v, u)) # 无向图两边都记 self.adj.setdefault(u, set()).add(v) self.adj.setdefault(v, set()).add(u) self.degree[u] len(self.adj[u]) self.degree[v] len(self.adj[v]) def common_neighbors(self, u, v): if u not in self.adj or v not in self.adj: return set() return self.adj[u] self.adj[v]这段代码里add_edge是无向边写法edges 集合同时记录 (u,v) 和 (v,u) 是为后续构建邻接矩阵或画图时省一次判断。common_neighbors用集合交集实现在python里这一步是C层哈希运算比双层for循环快一个数量级这是整包代码里用得最频繁的函数improved_cn.py、similarity_based.py都会调它。你在看graph.py时重点确认三点边是不是无向、自环是否允许、节点ID是字符串还是整数。提示如果数据里带自环很多相似度算法会被一条自环边干扰因为自环会让节点度和邻居统计同时失真。这个工程的设计上我建议在 pre_m.py 阶段就把自环和重复边全清掉后面算法就不用分心去处理这些异常。2.2 utils.py公共函数是拿来复用不是拿来炫技utils.py 在这套包里承担“公共工具函数池”的角色它的代码不长但几乎每个算法脚本都要 import。内容通常包括三大类边列表读写、相似度分数输出、以及排序取TopK。数据格式约定非常关键。读入时把每行的两个节点ID拆出来写入时把节点对和分数拼回一行文本。def load_edges(filepath): edges [] with open(filepath, r, encodingutf-8) as f: for line in f: line line.strip() if not line or line.startswith(#): continue parts line.split() u, v parts[0], parts[1] edges.append((u, v)) return edges def save_scores(pairs, scores, filepath): with open(filepath, w, encodingutf-8) as f: for (u, v), s in zip(pairs, scores): f.write(f{u}\t{v}\t{s:.6f}\n)load_edges 参数 filepath 指向一个纯文本文件每行两列列间用空格或制表符分隔空行和#注释会被跳掉。save_scores 输出的三列分别是源节点、目标节点、相似度分数这个文件格式要和 evaluate.py 里读取的格式严格保持一致否则测试阶段会解析失败。如果你换自己的数据注意节点ID里不要带空格否则split()会把ID拆碎这是python里最常见的坑文件名或ID里带特殊字符读进来直接报错。utils里通常还会放一个top_k_indices函数给定分数字典返回前K个最大分数对应的节点对下标。链路预测最终评估看的不是全量分数而是排序后头部那些候选边所以这个函数要写对。def top_k_indices(scores, k): # scores 是 dict: (u,v) - score ranked sorted(scores.items(), keylambda item: item[1], reverseTrue) return [pair for pair, _ in ranked[:k]]top_k_indices 的时间复杂度是 O(n log n)因为sorted做的是全量排序。当候选节点对数量到几十万时这个函数会变成性能瓶颈你可以改用heapq.nlargest把复杂度降到 O(n log k)。在代码包里看到这个函数时先别急着改跑通流程再做优化毕竟整套链路预测里比它耗时的函数还有不少。2.3 pre_m.py所有的脏活累活都在这pre_m.py 是预处理模块负责原始边的清洗、重新编号和训练/测试集切分前的统计。拿到的原始数据往往有这些毛病重复边、自环、节点ID不连续、稀疏到每个节点平均度不到2。这些都不会让程序直接崩溃但会让相似度计算失真。pre_m.py 的常规做法是三步去重去自环、给节点重排ID、输出节点数和边数统计。def preprocess(edges): seen_edges set() clean_edges [] for u, v in edges: if u v: continue key tuple(sorted([u, v])) # 无向边去重 if key not in seen_edges: seen_edges.add(key) clean_edges.append(key) # 重编号 node_list sorted(set([n for e in clean_edges for n in e])) mapping {n: i for i, n in enumerate(node_list)} remapped [(mapping[u], mapping[v]) for u, v in clean_edges] return remapped, len(node_list), len(remapped)这里tuple(sorted([u, v]))是去重的关键保证 (1,2) 和 (2,1) 被当成同一条无向边。重编号的意义在于后续要构建邻接矩阵时连续的整数ID能和矩阵下标一一对应省去一次字典查找。实际项目中预处理往往占总工作量的六成链路预测也不例外。你拿到这份资源后先把 pre_m.py 跑一遍看看它输出的统计数字再判断要不要加大节点过滤阈值。如果节点数非常大但边数很小说明网络极度稀疏后续相似度算法很容易全是0分这时候要优先考虑要不要做连通分量分析。3. 相似度算法与改进模型CN、RA、AA、PA在代码里怎么落链路预测的主流算法分两类基于相似度的启发式方法和基于模型的学习方法。这套代码包的侧重点是前一类并且附带了两个改进版本。这一章把算法公式和代码对应关系拆开讲你照着similarity_based.py读一遍基本就把链路预测最经典的四类指标吃透了。要理解这几个算法先抓住一个共性它们都试图回答“两个节点之间有没有潜在边”只是各自从不同角度定义“相似”。3.1 四个经典指标的公式选型从CN到PA共同邻居CN是链路预测的入门算法两个节点的公共邻居越多越可能产生新的连边。Jaccard系数在CN的基础上除以并集大小做了归一化目的是让分母把节点自身的度考虑进去避免大度节点天然占便宜。Adamic-AdarAA给公共邻居中的每个节点一个权重权重是它度数的对数倒数也就是说一个连接了很多节点的枢纽节点它对“这条候选边是否成立”的指示意义被压低。Preferential AttachmentPA完全不看公共邻居直接取两个节点度数的乘积它假设“越大的节点越容易产生新边”。四个指标对应一个需求你的网络是稠密还是稀疏很大程度决定了该选哪个。import math def cn_score(graph, u, v): return len(graph.common_neighbors(u, v)) def jaccard_score(graph, u, v): cn graph.common_neighbors(u, v) union graph.adj[u] | graph.adj[v] return len(cn) / len(union) if union else 0.0 def aa_score(graph, u, v): cn graph.common_neighbors(u, v) return sum(1.0 / math.log(graph.degree[w]) for w in cn if graph.degree[w] 1) def pa_score(graph, u, v): return graph.degree[u] * graph.degree[v]这里aa_score里加了一个degree[w] 1的过滤因为当节点度等于1时log(1)0python会抛 ZeroDivisionError这一行过滤几乎每个跑链路预测的人都会遇到属于必踩的坑。pa_score没有对节点做存在性判断如果传入不存在的节点degree 字典会直接 KeyError更稳的写法是graph.degree.get(u, 0)这样分数不会因为某个节点没出现在训练集里而直接崩溃。这四个函数在similarity_based.py里通常会被统一到一个调度函数里通过名字参数选择算法。3.2 improved_cn.py共同邻居的度加权改进改进版CN的思路非常直观原始CN把每个公共邻居的贡献都当成1这对度很大的枢纽节点过于友好。一个连接了1000个节点的节点和一个只连了3个节点的节点在CN眼里贡献相同这不合理。improved_cn.py常见做法是给每个公共邻居的贡献做度惩罚让“连接越少、关系越私密”的节点拥有更高权重。def improved_cn_score(graph, u, v): cn graph.common_neighbors(u, v) if not cn: return 0.0 total 0.0 for w in cn: deg_w graph.degree.get(w, 1) total 1.0 / (1.0 math.log(deg_w)) return total1.0 / (1.0 math.log(deg_w))是一个典型的Hub惩罚函数主要思路是公共邻居的度数越大它对这条候选边真实关联的指示意义越弱。这个改进在社交网络上是说得通的你和一个人有几个共同好友大概率是真的有关系你和所有节点都有共同邻居并不能说明更可能连边。对比原始CN这个函数返回的是浮点数而不是整数你换数据的时候要注意分数分布变了阈值也得跟着变不能再用整数阈值去卡。3.3 improved_ra.py资源分配算法的改进逻辑Resource AllocationRA来源于物理学中的资源传递思想节点u通过中间节点w向节点v传递资源每个中间节点的资源传递效率是度(w)的倒数。改进版RA把“资源”概念进一步扩展常见做法是给传递效率加上一个基于节点自身重要性的调制因子而不是所有中间节点一视同仁。def improved_ra_score(graph, u, v): cn graph.common_neighbors(u, v) if not cn: return 0.0 total 0.0 for w in cn: deg_w graph.degree.get(w, 1) # 引入节点自身的度比作为调制因子 w_importance graph.degree.get(u, 1) / (deg_w graph.degree.get(v, 1) 1e-9) total w_importance / deg_w return total这个实现里w_importance把源节点和目标节点的度也考虑进来让改进版不再只是中间节点属性的函数。需要注意1e-9这个极小值是为了防止除零python里浮点除零不会报错但会得到infinf进入排序会污染TopK结果。对比AA和原始RA改进RA在异构网络节点度分布极不均匀上的表现通常更稳。你在跑自己的数据时建议把原始RA和改进RA同时输出看AUC的差异再决定用哪个版本不要只信“改进”这两个字。3.4 similarity_based.py多算法统一封装与批量对比similarity_based.py存在的意义不是把各个算法塞进一个文件而是提供一个统一入口方便你在同一份数据上批量对比多个指标。它的返回值一般是一个字典键是算法名字值是分数列表列表顺序与候选节点对一一对应然后调evaluate.py统一计算AUC。这个文件的头部通常会写一个ALGORITHMS字典把函数名映射到标签方便后面循环调用。ALGORITHMS { cn: cn_score, jaccard: jaccard_score, aa: aa_score, pa: pa_score, improved_cn: improved_cn_score, improved_ra: improved_ra_score, } def compute_all_scores(graph, candidate_pairs): results {} for name, func in ALGORITHMS.items(): scores [func(graph, u, v) for u, v in candidate_pairs] results[name] scores return resultscompute_all_scores 返回的results里每个算法对应一个分数列表列表顺序和candidate_pairs完全一致。这个顺序约定很重要evaluate.py在算AUC时要按同样顺序取正负样本。如果你在这个文件里加自己的算法记得保持“输入(graph, u, v)输出一个可排序数值”的函数签名不然批量评估会断。我一般会建议在candidate_pairs上提前过滤掉训练集里已经存在的边只保留“尚未出现”的候选对做预测这一步不做的话评估阶段正样本会和训练集重叠分数虚高到没法看。4. 从训练到评估test.py、create_test.py与evaluate.py怎么闭环算法写得再好没有评估体系就是纸上谈兵。这套资源里的test.py、create_test.py、evaluate.py和data_analysis.py组成了一个完整的闭环构造正负样本、跑算法、算指标、画图。链路预测的标准评测方式不是直接输出一个分数了事而是把已知边随机砍掉一部分充当测试正样本再随机生成不存在的边充当负样本然后看算法给这些样本的排序能力。4.1 create_test.py与test.py样本划分与主流程的执行顺序create_test.py的职责是生成训练集和测试集。常见策略是把原始边按比例分成两份比如80%进训练集20%进测试集。训练集喂给算法去学习结构测试集里藏着“被隐藏的真实边”看算法能不能把它们从负样本里捞出来。这一步的关键是随机种子固定否则每次跑结果都不一样无法复现对比。def split_edges(edges, train_ratio0.8, seed42): random.seed(seed) edges list(edges) random.shuffle(edges) split_point int(len(edges) * train_ratio) train_edges edges[:split_point] test_edges edges[split_point:] # 负样本随机生成不存在的边 node_list sorted(set([n for e in edges for n in e])) return train_edges, test_edges, node_listtrain_ratio0.8是推荐值划分比例太高让测试集样本太少AUC置信区间过大比例太低则训练集缺结构分数不稳定。seed42是固定随机种子这样你换机器跑也能复现同一组训练/测试划分。test.py在主流程里的定位是“把所有文件串起来”读图、加载算法、跑分数、调用evaluate.py、把结果交给data_analysis.py。你在跑这个文件之前记得先确认graph.py的图对象和算法模块的函数签名能对上特别是节点ID类型是字符串还是整数不一致会一路报错到评估阶段。4.2 evaluate.pyAUC与排序精度的计算逻辑evaluate.py做两件事算AUC和算PrecisionK。AUC的含义是随机取一个正样本真实存在的边和一个负样本不存在的边算法给正样本打更高分的概率。这个指标不依赖阈值只看排序能力所以是链路预测里最常用的评估指标。def compute_auc(positive_scores, negative_scores): count 0 total 0 for ps in positive_scores: for ns in negative_scores: if ps ns: count 1 elif ps ns: count 0.5 total 1 return count / total if total 0 else 0.5AUC这个朴素双层循环的复杂度是O(m*n)当正负样本各一万个时计算量到一亿次比较python裸跑可能要几十秒。常见的优化是把负样本分数排序后做二分查找或者直接用sklearn.metrics.roc_auc_score替代把两个分数序列直接传进去。但如果你是想理解原理这段朴素实现更直观。0.5是随机猜测的AUC下限如果你跑出来接近0.5说明算法在你这份数据上没有预测能力0.7以上算有信号0.8以上在大多数网络数据集里已经是很好的结果。提示用sklearn时要注意分数方向有些算法的分数是“越小越像正样本”此时要设置roc_auc_score(y_true, -scores)否则AUC会反过来接近0.5。4.3 data_analysis.py与train.png/train2.png把分数分布画出来再做决定data_analysis.py是这套资源里的可视化模块。压缩包里的train.png画的是网络结构本身节点位置通常按度或社区布局一眼能看出网络是稠密还是稀疏、有没有明显的枢纽节点train2.png画的是训练过程中AUC或者分数分布的演化曲线。这两张图是作者跑完整个流程后留下的成品说明代码包本身是能跑通的。这种可视化的价值在于你光看一个AUC数字不知道算法哪里出了问题。比如正样本分数和负样本分数完全重合AUC会差但如果你画出直方图会看到两条分布几乎完全叠在一起这时就要去检查测试集里是不是含有大量孤立节点——孤立节点的相似度分数天然是0会拉低整个分布。train2.png如果显示AUC曲线在中途突然下滑多半是训练集和测试集的数据泄露或者随机种子没有固定导致评估集被污染。数据可视化不是交作业用的装饰它是排查问题最快的手段。5. 链路预测避坑指南五个必然踩到的常见问题链路预测代码简单但实际跑起来各种隐蔽问题会让结果完全不可信。这里写五条我实际遇到过、或者在这个资源场景下一定会遇到的坑每一条都是现象、原因、解决三段式。5.1 现象AUC接近0.9换数据后骤降到0.55原因训练集和测试集划分时没有隔离“大度节点”。有些数据集里存在超级枢纽节点它们连接了大量节点其邻居几乎覆盖全图算法靠PA或AA直接给这些节点对所有候选边打出高分AUC虚高。换了数据没有这种节点分数自然崩掉。 解决划分训练/测试集时按节点而不是按边来划分保证同一个节点的边要么全在训练集要么全在测试集。用create_test.py里的seed参数复跑分别用edge-based和node-based两种划分对比一下AUC差距差距超过0.1就要警惕先排查数据里有没有超级节点。5.2 现象import时报错错误指向utils.cpython-35.pyc原因压缩包里带着编译过的.pyc文件而pyc是绑定Python具体小版本的。utils.cpython-35.pyc这个名字里的35表示Python 3.5你本机如果是3.8、3.10解释器不会正确加载旧pyc直接抛invalid magic number或干脆找不到模块。 解决把__pycache__目录整个删掉让python重新生成pyc。命令行执行rm -rf __pycache__Windows里是rd /s /q __pycache__。同时检查graph.py、utils.py的代码里有没有用到Python 3.5之后的语法比如f-string在3.5里是不支持的有的话需要手动改回format()写法。5.3 现象所有算法的分数全是0或同一个常数原因common_neighbors返回空集合。大概率是图构建时只加了节点没加边或者pre_m.py的去重逻辑把方向搞反了导致连通性完全丢失。另一个常见原因是加载数据时列顺序反了原始文件第一列是目标节点、第二列是源节点而graph.py按第一列源节点、第二列目标节点解析整个图会被解析成完全不同的结构。 解决打印len(graph.nodes)和len(graph.edges)和原始边表行数对齐。再随机抽三条边确认它的两个端点都出现在nodes里。这两步做下来能排除九成解析错误。5.4 现象evaluate.py算AUC极其慢几分钟跑不完原因朴素的O(n*m)双层循环在样本量过万后就是慢。链路预测的负样本经常是正样本的十倍甚至百倍这时m50000、n5000比较次数两亿五千万Python裸循环要跑很久。 解决把compute_auc里的双层循环改成对负样本分数列表排序后做二分查找或者直接调用sklearn.metrics.roc_auc_score。前者复杂度降到O(n log m)后者更快但要注意预测分数方向高分代表正样本时要设置好参数。5.5 现象改进算法跑不过原始算法AUC反而低0.05原因改进版算法常常是针对某种特定网络结构设计的。比如improved_cn里的Hub惩罚适合无标度网络但如果你的数据是规则网格或者树状结构惩罚大度节点反而伤害了真实信号。没有普适的改进算法只有特定场景下的改进。 解决不要只跑改进版就下结论。在similarity_based.py的ALGORITHMS字典里同时保留原始算法和改进算法跑完对比AUC差距。如果改进版没有提升直接用原始版结果不丢人改进版只在它确实带来提升的数据上使用才叫改进。6. 一个实用技巧用边删除法验证链路预测模型的稳定性整个代码包跑通、AUC也过得去后别急着上报告。先做一次简单的稳定性验证把测试集里的正样本边继续按比例删掉一部分比如分别删10%、30%、50%然后重新计算所有算法的AUC。如果AUC随删除比例平稳下降说明算法对这个网络结构是真正敏感的结果可信如果AUC在删除30%之后仍然基本不变说明结果可能被少数超级节点或者训练/测试重叠主导模型的预测能力值得怀疑。我一般会写一个对比脚本把边删除比例、AUC、Precision100三个指标输出成一张表def stability_check(graph, test_positive, test_negative, ratios[0.1, 0.3, 0.5]): for r in ratios: remain int(len(test_positive) * (1 - r)) sub_positive test_positive[:remain] scores algorithm_on_pairs(graph, sub_positive, test_negative) auc compute_auc([s for _, s in scores[:len(sub_positive)]], [s for _, s in scores[len(sub_positive):]]) print(f删除比例{r:.0%}, AUC{auc:.4f})在 ratios 里选0.1/0.3/0.5是经验值首次删10%是在消除边界波动30%看中期趋势50%看算法在数据量减半时的韧性。随着删除比例增加AUC下降是预期的但如果某项算法在50%删除时反而走高说明它本质上是在“记住”训练集中的例外节点不是在学习一般规律。这个脚本不需要新函数直接复用evaluate.py里的compute_auc就能组装出来。它的价值在于当你给同事或客户汇报“链路预测AUC是0.82”时能顺手附上“在删除30%真实边之后AUC降到0.76说明结果是结构性的不是靠几条大边撑起来的”这比单给一个数字有说服力得多。从那以后我每次跑链路预测无论数据多大多小都强制先走一遍这个稳定性检查再决定要不要继续调参。希望这个习惯和经验总结帮到你让你在链路预测上少走一些弯路。本文还有配套的精品资源点击获取