企业官网建设流程全解析

简介：面向网络科学、数据挖掘研究者和 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", encoding="utf-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", encoding="utf-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(), key=lambda item: item[1], reverse=True) 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-Adar（AA）给公共邻居中的每个节点一个权重，权重是它度数的对数倒数，也就是说，一个连接了很多节点的枢纽节点，它对“这条候选边是否成立”的指示意义被压低。Preferential Attachment（PA）完全不看公共邻居，直接取两个节点度数的乘积，它假设“越大的节点越容易产生新边”。四个指标对应一个需求：你的网络是稠密还是稀疏，很大程度决定了该选哪个。

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)=0，python会抛 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 total

1.0 / (1.0 + math.log(deg_w))是一个典型的Hub惩罚函数，主要思路是：公共邻居的度数越大，它对这条候选边真实关联的指示意义越弱。这个改进在社交网络上是说得通的：你和一个人有几个共同好友，大概率是真的有关系；你和所有节点都有共同邻居，并不能说明更可能连边。对比原始CN，这个函数返回的是浮点数而不是整数，你换数据的时候要注意分数分布变了，阈值也得跟着变，不能再用整数阈值去卡。

3.3 improved_ra.py：资源分配算法的改进逻辑

Resource Allocation（RA）来源于物理学中的资源传递思想：节点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里浮点除零不会报错但会得到inf，inf进入排序会污染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 results

compute_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_ratio=0.8, seed=42): 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_list

train_ratio=0.8是推荐值，划分比例太高让测试集样本太少，AUC置信区间过大；比例太低则训练集缺结构，分数不稳定。seed=42是固定随机种子，这样你换机器跑也能复现同一组训练/测试划分。test.py在主流程里的定位是“把所有文件串起来”：读图、加载算法、跑分数、调用evaluate.py、把结果交给data_analysis.py。你在跑这个文件之前，记得先确认graph.py的图对象和算法模块的函数签名能对上，特别是节点ID类型是字符串还是整数，不一致会一路报错到评估阶段。

4.2 evaluate.py：AUC与排序精度的计算逻辑

evaluate.py做两件事：算AUC和算Precision@K。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.5

AUC这个朴素双层循环的复杂度是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)双层循环在样本量过万后就是慢。链路预测的负样本经常是正样本的十倍甚至百倍，这时m=50000、n=5000，比较次数两亿五千万，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、Precision@100三个指标输出成一张表：

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，说明结果是结构性的，不是靠几条大边撑起来的”，这比单给一个数字有说服力得多。从那以后，我每次跑链路预测，无论数据多大多小，都强制先走一遍这个稳定性检查，再决定要不要继续调参。希望这个习惯和经验总结帮到你，让你在链路预测上少走一些弯路。

本文还有配套的精品资源，点击获取