简介面向社交网络分析与数据挖掘场景的MATLAB链路预测代码包解决网络中未知连接或未来关系的预测问题适合具备一定MATLAB基础、希望从代码层面掌握链路预测典型算法的研究者与学生也可作为课程实验或毕业设计的参考实现。压缩包总共37个文件包含34个.m主程序与函数脚本、2个.asv自动备份文件以及1个txt说明文档整体仅22KB体积小巧、结构集中便于逐行阅读和二次修改。已有2420人浏览学习。程序实现了Common Neighbors、Jaccard、Adamic-Adar、Resource Allocation、Katz、RWR等经典链路预测算法并配有数据划分示例、相似度计算核心代码与AUC评价函数。从网络数据读取、训练/测试划分到打分预测、结果验证构成完整流程读者可以直接运行Main.m体验默认数据也可以替换成自己的社交网络数据开展实验。代码量精简但覆盖关键环节是快速上手链路预测和社交网络分析的高质量参考。1. 从 Code.rar 与 PRED-163 说起MATLAB 链路预测到底在预测什么社交网络里的链路预测本质是在回答一个反事实问题给定当前时刻的网络快照哪些节点之间还没连边但未来最可能连上无论是电商推荐“你可能认识的人”、生物网络里预测蛋白质相互作用还是舆情网络中判断信息扩散路径底层都是同一套数学工具。PRED-163 这类以编号命名的 MATLAB 工程包通常对应某一次具体的预测任务数据集编号 163跑的是 predprediction流程输入是社交网络邻接矩阵输出是候选边的得分排序。这类包一般压缩成 Code.rar 分发解压后能看到的无非是数据文件、若干 .m 脚本和一组结果矩阵。难点从来不在“跑通某个包”而在于你自己拿到一个网络时能不能用 MATLAB 把这套流程从头搭起来矩阵怎么构造、相似性指标怎么算、结果怎么评估。这篇文章就从这三个层面展开顺带把 PRED-163 这类工程里最常见的参数设置和踩坑点讲清楚。整个过程不依赖任何第三方工具箱纯 MATLAB 原生函数即可复现。2. 读懂社交网络分析在 MATLAB 里的数据底盘邻接矩阵与 PRED-163 的输入结构2.1 为什么邻接矩阵是链路预测的唯一入口链路预测的所有算法不管基于相似性、基于最大似然还是基于嵌入第一步都是把网络转成矩阵。MATLAB 里没有内置的“图对象”作为算法输入惯例工程上最常见的数据格式就是 n×n 的稀疏邻接矩阵 A其中 A(i,j)1 表示节点 i 到 j 有一条有向边无向网络则让 A 对称。PRED-163 这类项目包的数据文件通常是 .mat 或 .csv.mat 里一般存一个名为 A 或 net 的变量。拿到 Code.rar 后第一步不是急着跑脚本而是先验证这个矩阵的尺寸和稀疏度因为后续所有指标的复杂度都直接由 n 和边数 m 决定。% 解压 Code.rar 后进入项目目录 load(PRED_163_data.mat); % 常见变量名是 A、net、adj先用 whos 确认 whos; % 如果变量名不叫 A做一次重命名 if exist(net, var), A net; end % 输出矩阵规模与边数n 到几千是常见规模 [n, ~] size(A); m nnz(A); fprintf(节点数: %d, 边数: %d\n, n, m); % 检查是否对称这决定你要不要套用无向算法 if isequal(A, A), fprintf(网络是无向的\n); else fprintf(网络是有向的注意指标转换\n); end这段代码里nnz是计算非零元数量的关键函数稀疏矩阵用nnz而不是sum(sum(A))因为后者会把稀疏矩阵先稠密化n 到几千时就能感到明显卡顿。isequal(A, A)用来判断对称性这直接影响后续选 CN 还是选有向版本的指标。2.2 稀疏矩阵的三条铁律第一永远用sparse存储。MATLAB 对稠密矩阵的索引和运算在 n 超 3000 后会明显吃力而真实社交网络的边密度通常不到 1%稀疏矩阵在内存和速度上都是压倒性优势。常见做法是在读入数据那一行就做一次类型转换A sparse(A);第二把对角线清零。自环在社交网络里几乎没有预测意义却会干扰sum(A, 2)算度时的结果。第三确认节点编号从 1 开始且连续。很多原始数据集的节点 ID 有跳号或从 0 开始这会让矩阵第 0 行或空行列出现导致sum和索引结果错位。处理方式是一次性重编号% 假设原始边列表存在 edges 里第一列是源节点第二列是目标节点 [uid, ~, ic] unique(edges(:, 1:2)); n numel(uid); A sparse(ic(:, 1), ic(:, 2), 1, n, n); % 顺便去重并转逻辑矩阵 A A 0;这段代码的关键在unique的第三个返回值ic它把任意编号映射到 1 到 n 的连续整数上配合sparse构造函数直接生成稀疏矩阵。A A 0这一步非常容易被忽略原始数据里如果有重复边导致非零元是 2 或 3不转逻辑矩阵后面算 Jaccard 时会出现大于 1 的奇怪数值。下面是三种常见输入格式的对比输入格式典型场景推荐读取方式注意事项.mat 文件PRED-163 内部标准load先whos确认变量名两列/三列 CSV从 SNAP 或手工采集readmatrix或csvread检查是否含表头稠密邻接矩阵小规模演示数据sparse转换先查对角线元素2.3 数据划分验证集和训练集的三种切法链路预测的实验规范和一般机器学习不同它不是随机抽行而是抽边。PRED-163 这类项目里最常见的划分方式是从现有边集合里随机隐藏 10% 的边作为正例测试集保证网络连通性的前提下把剩余 90% 作为训练集。三种常见做法各有适用范围rng(163); % 固定随机种子保证可复现 % 方式一按边编号随机抽取 [u, v] find(triu(A, 1)); % 只取上三角避免正反对重复 edges_all [u, v]; n_e size(edges_all, 1); test_idx randperm(n_e, round(0.1 * n_e)); test_edges edges_all(test_idx, :); train_A A; train_A(sub2ind([n, n], test_edges(:, 1), test_edges(:, 2))) 0; train_A(sub2ind([n, n], test_edges(:, 2), test_edges(:, 1))) 0;注意方式一里triu(A, 1)取上三角的作用是避免把同一条无向边当成两条样本否则随机划分时正例集会包含重复的节点对。randperm的第二个参数指定抽取数量这里用了 163 这个种子方便复现 PRED-163 的实验设置。3. 社交网络分析链路预测的核心算子从 CN 到 RA 的 MATLAB 实现与参数选择3.1 Common Neighbors 的三行代码与复杂度陷阱Common Neighbors 是链路预测里最基础的指标它的直觉是两个节点共享的邻居越多越可能产生连边。在 MATLAB 里这个指标的计算可以只用三行矩阵运算完成% 计算 CN 矩阵 CN train_A * train_A; % 只保留没有直接边且不是自身的节点对 candidate (CN 0) (train_A 0) ~eye(n);第一行train_A * train_A中结果矩阵的第 (i, j) 个元素恰好是 节点 i 和 j 之间长度为 2 的路径数也就是共同邻居数。这背后是矩阵乘法的定义元素值等于 i 的邻居集合与 j 的邻居集合的交集大小。第二行的~eye(n)用逻辑非和对角矩阵消除自环这是 MATLAB 里处理“排除节点自身”最简洁的写法。三行代码虽然简洁但复杂度是 O(n³)n 在 5000 以上时会有明显等待时间。优化思路是把大矩阵拆成块% 分块计算避免一次性申请全矩阵 block_size 500; CN sparse(n, n); for idx 1:block_size:n range idx:min(idx block_size - 1, n); CN(:, range) train_A * train_A(:, range); end分块的本质是用时间换内存。CN(:, range)每次只申请 500 列的空间对 n 一万左右的中型网络内存占用可以降到原来的 1/20。真实社交网络分析里这个操作比直接全量乘要稳得多。3.2 RA 和 AA带权重指标的 MATLAB 实现Common Neighbors 的一个明显缺陷是它对所有共同邻居一视同仁但度很大的节点比如微博大 V提供的连接信息量其实很低。Resource Allocation 指标给每个公共邻居的贡献加了权重——度越大权重越小% RA 指标1/度 加权 d sum(train_A, 2); % 计算每个节点的度 d(d 0) 1; % 隔离节点度设为 1避免除零 d_inv 1 ./ d; % 构造对角矩阵然后做矩阵乘法 D_inv spdiags(d_inv, 0, n, n); RA train_A * D_inv * train_A; RA (RA 0) (train_A 0) ~eye(n);这里spdiags把度倒数向量放到对角线上构造对角矩阵。train_A * D_inv * train_A展开来看相当于每条长度为 2 的路径 i-k-j 都贡献了 1/d(k) 的值给 (i, j)和 RA 的定义完全一致。AA 指标的区别在于权重从 1/d 变成 1/log(d)% AA 指标1/log(度) 加权 D_log_inv spdiags(1 ./ log(d 1), 0, n, n); AA train_A * D_log_inv * train_A;两个指标在代码层面的差别只是对角矩阵取倒数还是取对数倒数但这背后对应着不同的网络假设RA 认为资源分配量随度线性衰减AA 认为衰减速度更慢。在真实社交网络中如果大 V 节点的信息扩散能力确实很强AA 往往表现更好如果网络相对均质RA 更稳。指标的参数对比可以总结为这张表指标权重公式适用场景计算复杂度CN1基线对照、稀疏网络O(n³)Jaccard1/(|N(i)|∪|N(j)|)度分布差异大的网络O(n³)RA1/d(k)均匀度分布、信息扩散O(n³) 稀疏对角乘AA1/log(d(k))存在高影响力节点O(n³) 稀疏对角乘3.3 Katz 指标把全局路径纳进来的矩阵求逆以上指标都只看长度为 2 的路径Katz 指标把更长的路径也纳入考量路径越长贡献指数衰减% Katz 指标sum(beta^k * A^k)等价于 (I - beta*A)^(-1) - I beta 0.1; % 衰减因子必须小于 1/谱半径 I speye(n); K inv(I - beta * train_A) - I;inv函数在这里对稀疏矩阵会返回稠密矩阵n 超过 2000 时内存会爆炸。工程替代方案是用线性迭代求解% 用迭代法避免稠密化max_iter 一般 5 到 10 次就够 K sparse(n, n); Ak speye(n); for iter 1:5 Ak Ak * train_A * beta; K K Ak; end展开Ak Ak * train_A * beta的逻辑第一次循环 Ak 是 betaA第二次是 beta²A²每次往 K 里累加。这个迭代等价于矩阵幂级数求和5 次迭代意味着考虑最高 5 跳路径。beta的取值是 Katz 指标唯一的超参数理论约束是小于邻接矩阵谱半径的倒数MATLAB 里可以用eigs(train_A, 1)估算谱半径。实际工程中 beta 取 0.01 到 0.05 之间比较安全太大容易导致高估长路径的作用太小则退化成 CN。4. 跑通 PRED-163 的预测流程脚本结构、AUC 评估与排序输出4.1 一个典型 MATLAB 链路预测文件包的脚本划分解开 Code.rar 之后常见做法是把任务拆成四个脚本数据加载load_data.m、相似性计算compute_similarity.m、评估evaluate.m和主流程main.m。这个划分方式的意义在于把数据预处理、算法核心和结果验证解耦方便换数据或换指标时只改一个模块。主流程脚本的骨架逻辑如下% main.m 的主干逻辑 % 第一步加载数据 A load_data(PRED_163_data.mat); % 第二步划分训练集和测试集 [train_A, test_edges] split_edges(A, 0.1, 163); % 第三步计算相似性矩阵 S compute_similarity(train_A, RA); % 第四步在测试集上评估 auc evaluate_auc(S, test_edges, A, 1000); fprintf(AUC %.4f\n, auc);split_edges返回的训练矩阵是隐藏了 10% 边之后的网络test_edges是被隐藏的边作为正例。注意compute_similarity里的第三个参数用字符串传给 MATLAB 的switch或strcmpi分支这样可以在不改主流程的情况下切换指标。4.2 AUC链路预测最常用的评估指标及其 MATLAB 实现AUC 在链路预测里的含义是随机从正例集合被隐藏的测试边取一条边它的得分高于随机取一条负例不存在的边的概率。工程上无法枚举所有不存在的边所以用随机采样的方式近似。这个指标比 Precision 更稳健因为它不受预测阈值影响。function auc evaluate_auc(S, test_edges, A, n_neg) n_pos size(test_edges, 1); score_pos S(sub2ind(size(S), test_edges(:, 1), test_edges(:, 2))); n size(A, 1); % 随机抽取不存在的边作为负例 n_neg min(n_neg, n * (n - 1) / 2 - nnz(A)); neg_edges zeros(n_neg, 2); cnt 0; while cnt n_neg i randi(n); j randi(n); if i ~ j A(i, j) 0 S(i, j) 0 cnt cnt 1; neg_edges(cnt, :) [i, j]; end end score_neg S(sub2ind(size(S), neg_edges(:, 1), neg_edges(:, 2))); % AUC P(score_pos score_neg) 0.5 * P(score_pos score_neg) cmp (score_pos score_neg) 0.5 * (score_pos score_neg); auc mean(cmp(:)); endsub2ind把行列坐标转成线性索引效率远超for循环逐个访问。负例采样用 while 循环是为了保证抽到的节点对确实不存在连边S(i, j) 0条件把根本没被算法纳入考虑的节点对过滤掉这会轻微高估 AUC但工程上可以接受。如果要更严格可以去掉这个条件代价是负例里会有大量零得分样本使得 AUC 数值偏高但区分度下降。4.3 输出可解释的预测列表PRED-163 的最终交付物通常是一个按得分降序排列的候选边列表。MATLAB 里用sortrows可以一次搞定% 把相似性矩阵转成 节点对 得分 的三列格式 [u, v] find(triu(S, 1)); % 上三角避免重复 score S(sub2ind([n, n], u, v)); % 过滤掉训练集已有的边 existing train_A(sub2ind([n, n], u, v)); keep existing 0; u u(keep); v v(keep); score score(keep); % 按得分降序输出 Top K K 100; [~, idx] sort(score, descend); top_list [u(idx(1:K)), v(idx(1:K)), score(idx(1:K))]; % 如果节点有原始 ID 映射在这里做一次映射 top_list(:, 1) uid(top_list(:, 1)); top_list(:, 2) uid(top_list(:, 2)); writematrix(top_list, PRED_163_top100.csv);这段代码最后两行是工程中常被忽略的环节前面重编号过节点输出预测结果前必须映射回原始 ID否则业务方拿到的是一串无意义数字。writematrix是 MATLAB R2019a 之后推荐的表写函数老版本可以换成csvwrite。下表汇总了跑通一次完整链路预测各阶段的时间分布阶段常用函数耗时占比性能瓶颈数据加载与清洗readmatrix,unique,sparse5%I/O 与大矩阵生成相似性计算矩阵乘法,spdiags80%矩阵乘的 |O(n³)|负例采样randi, 循环5%随机数质量与 collisionAUC 计算sub2ind,mean10%比较矩阵内存5. 指标失效的边界从 PRED-163 的编号看数据规模对算法选择的影响PRED-163 里的数字“163”在不同工程包里含义不同但最常见的约定是数据集编号——具体数据是社交网络还是生物网络直接决定算法选择。社交网络分析的链路预测在 MATLAB 里存在几处容易看走眼的边界这里逐一拆解。第一处边界是网络规模和算法复杂度之间的硬约束。CN、RA、AA 这三个指标本质都是矩阵自乘n 超过 2 万以后即便用稀疏矩阵一次乘法也要消耗数十秒到分钟级。常见做法是先用min(n, 5000)做一次规模判断超过阈值的网络降级用局部采样指标。业界通行方案是“只对目标节点的二阶邻居范围计算相似性”把全局矩阵乘法变成局部枚举% 局部化计算只算某些候选节点对的相似性 function [u, v, s] local_ra(A, u_list, v_list) s zeros(length(u_list), 1); for k 1:length(u_list) neu setdiff(find(A(u_list(k), :)), v_list(k)); nv setdiff(find(A(v_list(k), :)), u_list(k)); common intersect(neu, nv); if isempty(common), s(k) 0; continue; end s(k) sum(1 ./ full(sum(A(common, :), 2))); end endsetdiff和intersect是 MATLAB 集合运算三件套这里用它们把共同邻居的查找限定在两个节点的邻居集合上避免全矩阵操作。sum(A(common, :), 2)输出度向量full把稀疏行向量转稠密以兼容索引。这段代码的效率依赖find的返回次数稀疏度越高越有利。第二处边界是“无向假设”。PRED-163 这类包经常默认网络是对称的但很多真实社交网络如微博关注关系、邮件通信网是有向的。如果矩阵不对称需要把有向指标转换成无向指标再做预测或者直接用有向版本的 CN 公式共同邻居的定义改成“同时指向目标节点的节点集合”。% 有向 CN 的前向版本关注同一人 CN_directed train_A * train_A; % 反向版本被同一人关注 CN_rev train_A * train_A;第三处边界是孤立节点的影响。社交网络里有大量度为零或度为 1 的节点这些节点参与的任何指标计算都倾向于给出不可靠的低分。评估时常见做法是单独统计孤立测试边的 AUC避免它们拉低整体指标。MATLAB 里可以用sum(train_A, 2) 0直接取孤立节点索引然后在evaluate_auc里做一次过滤这种细粒度评估往往比只看整体 AUC 更能定位算法失效的具体模式。6. 用 5 行代码验证预测结果是否可信随机化与分层检查链路预测工程的末尾需要验证结果不是偶然得到的。最实用的技巧是“随机化基线对比”保持训练网络的度序列不变随机改写节点标签生成若干随机网络计算随机基线下的 AUC 分布。如果真实网络的 AUC 落在这个分布的 95% 置信区间内说明预测没有真正捕捉到网络结构信息。% 随机化基线随机打乱节点标签 20 次 rand_aucs zeros(20, 1); for r 1:20 perm randperm(n); Ar train_A(perm, perm); % 节点标签随机重排 Sr compute_similarity(Ar, RA); rand_aucs(r) evaluate_auc(Sr, test_edges, A, 1000); end % 置信区间 ci prctile(rand_aucs, [2.5, 97.5]); fprintf(随机基线 AUC: %.3f [%.3f, %.3f]\n, mean(rand_aucs), ci(1), ci(2));train_A(perm, perm)同时重排行和列等价于随机重排节点身份但不改变网络结构特征这样基线保留了度分布信息却破坏了具体连接关系。prctile输出置信区间的上下界真实 AUC 如果高于上界才说明预测效果显著。另一层验证是分层检查。把测试边按两端节点的度乘积分组分别看每组的预测准确率通常会出现“低度节点对的预测率远高于高度节点对”的现象。这类检查的工程价值在于暴露算法的偏好而不是简单地报告一个 AUC 数字。可以用discretize函数把度乘积切成分箱然后逐箱计算 AUC最后画柱状图。度数最高的那箱 AUC 接近 0.5 是常态因为大 V 之间连边随机性太强。MATLAB 里这些检查做完预测流程才算真正闭环。PRED-163 这类工程包的价值在于给了你一套可以逐段替换的模板数据换了改load_data指标换了改compute_similarity评估粒度要变改evaluate_auc。链路预测在工程上从来不缺算法缺的是把算法结果翻译成决策信号的那一层校验。本文还有配套的精品资源点击获取