0 概述

在复杂网络研究领域, 网络自身的结构特性与演化模式得到越来越多的关注。链路预测通过高度抽象的拓扑结构再现真实世界中的各种复杂关联关系, 以节点与连边形式对各类网络进行结构化建模^[1], 并开展后续的网络分析与测试。链路预测作为复杂网络演化预测的重要分析工具^[2], 可以通过已知的网络结构拓扑、节点属性、连边方向和权重等信息, 预测因观测手段有限或数据缺失导致未知而实际存在的连边, 或者预测随着时间演化后续在网络中将大概率产生连边关系的节点对^[3]。通过对链路预测的结果分析, 可以进一步深化对复杂网络的构造认知并搜寻网络中的特殊节点和特殊连边。

早期链路预测算法主要采集节点属性信息与拓扑结构信息, 通过马尔科夫链、机器学习^[4]等方法进行网络结构的链路预测, 但存在节点内部信息获取困难、节点标签计算加权模式复杂等问题。此外, 在基于似然分析模型的链路预测框架中, 可以通过分析现有链路构成和假设网络层次特性, 计算网络的链路似然, 也可以通过定义网络整体的哈密顿量及对应的网络系统, 在观察特定链路加入和删除过程中对网络自身似然影响进行计算连边概率^[5]。文献[5]采用似然分析在小规模网络中取得较好的预测结果, 但其过于庞大的计算开销, 使得该方法尚无法应用于大规模网络。

在节点属性信息缺失的前提下, 通过获取网络的拓扑结构信息进行链路预测, 是当前链路预测的主流方法。其中, 基于结构相似性的链路预测方法在拓扑信息获取难度上低于基于特定节点属性的链路预测方法。此外, 还可以从抽象角度分析拓扑结构特性, 减少在机器学习中针对特殊网络参数调优的工作量。

在基于路径的链路预测方法中, 基于二阶路径(共同邻居)的方法虽然计算复杂度低, 但是不能充分利用拓扑结构信息, 限制了其预测精度。尤其在以路由器网络^[6]为代表的实例中, 99.59%的路由器节点对二阶路径相似性得分为0, 在剩余的节点对中91.11%节点对得分为1, 4.48%节点对得分为2。文献[7]在二阶路径分析和全局路径分析的基础上, 提出综合考虑二阶路径与三阶路径的链路预测方法, 在实验网络的结果预测中, AUC与Precision都取得较好的验证结果。

本文从链路预测问题定义描述出发, 介绍用于链路预测的相似性指标, 结合当前主流相似性指标的优缺点, 提出一种基于资源分配与偏好连接的局部路径预测算法, 在综合加权网络结构中的度分布信息与局部路径结构的基础上进行链路预测。

1 链路预测问题描述与评价方法 1.1 问题描述

定义无向网络G=(V, E), 其中, V为网络G中所有节点集合, E为网络G中节点之间连边关系集合。网络中总的节点数为|V|, 则对于任意2个节点对之间产生连边的可能情况有|V|(|V|-1)/2种, 定义为节点对可能产生的链接关系全集U。对于任意未发生连边关系的节点对(u, v)∈(U-E), 结合特定链路预测相似性算法, 赋予一个相似性得分S_uv。根据S_uv大小进行判断, 其值越大, 相应的节点对产生连边关系的概率越大。

以一个具有6个节点, 存在8条连边的网络为例, 如果节点与节点全部互相连接, 最多会存在15条连边。因此全集|U|为15, 其中包括7条不存在连边。此时, 选出已存在的8条连边中的6条作为训练集, 剩余9条边构成测试集(包括2条已存在连边和7条不存在的连边)。按照不同链路预测算法给定的计算流程, 将9条未知边各赋予一个分数值, 然后按得分由大到小排序, 如果最终测试集中2条已存在边整体比7条不存在的边排序靠前, 那么表示该链路预测算法预测精度较高。

1.2 评价方法

在链路预测评价体系中, AUC^[8]、Precision^[9]、Ranking Score^[10]为常用评价指标。本文采用AUC和Precision指标, 并对Ranking Score作简要介绍。AUC是目前在链路预测中广泛采用的评价指标, 即ROC曲线下方面积。在链路预测背景下, AUC是在测试集中随机选取一条边的分数值比随机选取一条不存在边分数值高的概率, 其定义如下:

$ AUC = \frac{{n' + 0.5n''}}{n} $

(1)

其中, n为独立比较的次数, n′为测试集中边得分值优于不存在的边得分值的情况次数, n″表示测试集中边得分值等于不存在的边的得分值的情况次数。

Precision需要确定排序范围值L。L表示通过预测算法输出的前L个预测结果, 然后对比实际链路, 寻找预测正确的链路条数m, Precision值越大表明算法的准确度越高。

$ \mathit{Precision} = \frac{m}{L} $

(2)

Ranking Score关注测试集中边在最终排序结果中的位置, 令re为测试边在链路预测排序中的名次, 集合H为未知边总集合, 则单条特定边e的排序得分为RS_e=re/|H|。将所有测试边的RS_e求和再计算均值, 为此次测试算法的最终排序分, 排序分越小说明算法准确度越高。

2 链路预测指标 2.1 共同邻居指标及其衍生指标

CN指标^[11]是基于相似性链路预测指标中最基础、最简洁的指标。CN指标的核心观点是, 若任意两节点u、v共同连接的邻居节点个数越多, 则节点u、v越倾向于产生连边关系。在CN指标的基础上, 引入节点u、v各自在网络中的度信息, 还可以进一步构造其他衍生相似性指标。CN及其衍生的链路预测算法, 由于只计算局部的结构信息, 即可得到对应的相似性指标得分, 凭借其计算复杂度低的优势适合在大规模网络上进行预测, 但与三阶路径或更全面的全局指标相比, 其预测精度稍低。CN相似性指标计算如下:

$ {S_{uv}} = \left| {\mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} \right| $

(3)

Salton指标^[12]是在共同邻居的基础上, 结合节点度信息进行计算, 也称余弦相似性指标。Salton指标计算如下:

$ {S_{uv}} = \frac{{\left| {\mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} \right|}}{{\sqrt {{k_u}{k_v}} }} $

(4)

其中, k_u和k_v分别表示节点u和v的度。

Jaccard指标^[13]需要分别计算节点u、v邻居的交集、并集的势, 再计算相似性得分。Jaccard指标计算如下:

$ {S_{uv}} = \frac{{\left| {\mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} \right|}}{{\left| {\mathit{\Gamma }\left( u \right) \cup \mathit{\Gamma }\left( v \right)} \right|}} $

(5)

Sorensen指标^[14]主要取决于共同邻居的势和节点对(u, v)的度之和, 其最初被应用于生态植物群落研究中。Sorensen指标计算如下:

$ {S_{uv}} = \frac{{2 \times \left| {\mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} \right|}}{{{k_u} + {k_v}}} $

(6)

2.2 度分配权重指标

AA指标^[15]和RA指标^[16]基于假设:度数较小的节点对每一个邻居施加的影响力远大于度数较大的节点。

在AA指标中, 节点u、v所获得相似性分数来自于所有共同邻居度的对数分之一并累加求和。AA指标计算如下:

$ {S_{uv}} = \sum\limits_{z \in \mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} {\frac{1}{{\lg {k_z}}}} $

(7)

RA指标的计算思路更多源自网络资源分配过程。在RA指标中, 节点u、v所获得相似性分数变为所有共同邻居度的倒数并累加求和。RA指标计算如下:

$ {S_{uv}} = \sum\limits_{z \in \mathit{\Gamma }\left( u \right) \cap \mathit{\Gamma }\left( v \right)} {\frac{1}{{{k_z}}}} $

(8)

AA指标和RA指标在实际的网络计算中, 通过对节点度的考察, 能有效利用网络的度分布信息。在社区挖掘预测实验中^[17], RA和AA都能较好地刻画网络, 基于度分配权重指标的方法整体比共同邻居方法更优。

2.3 偏好连接指标

在PA指标^[18]中, 节点u、v之间产生连边的概率, 正比于节点u、v各自度相乘之积。因此在计算过程中, 大度节点互相之间的连边概率将大于小度节点。PA指标计算如下:

$ {S_{uv}} = {k_u} \times {k_v} $

(9)

PA指标在诠释复杂网络中“富者愈富”的节点连接偏好时较为显著。在实际网络预测中, 基于PA指标的算法针对稀疏路由网络预测准确度较好。同时, 该算法机制适用于恒定连边的非增长网络预测^[19]。

2.4 二阶与三阶路径信息指标

在传统的CN指标思想中, 式(3)的等式右侧为集合的势, 既是节点u、v的共同邻居数量, 同时其数量也等于节点u、v之间长度为2的路径数量, 即|Γ(u)∩Γ(v)|=(A²)_uv, A表示节点u、v所在网络的邻接矩阵。

由于CN指标在计算部分稀疏网络的过程中, 存在相似性分数分布过于集中、抽取的节点对之间区分程度过小的情况, 文献[7]在二阶路径(A²)_uv的基础上, 引入含参数的三阶路径指标, 即局部路径(Local Path, LP)指标, 进一步提高了网络结构信息利用率。LP指标计算如下:

$ \mathit{\boldsymbol{S}} = {\mathit{\boldsymbol{A}}^2} + \alpha {\mathit{\boldsymbol{A}}^3} $

(10)

其中, Aⁿ表示了节点u到节点v之间的路径长度, α为调节参数。一般将α设置为0.001^[5]。此外, 当α设为0时, LP指标即为CN指标。

3 本文算法 3.1 LRPA指标

常规LP指标通过调节参数α来调整最终的预测结果, 对网络中的度分布信息、共同邻居信息、局部或全局路径信息的利用较为孤立。且由于α较小, LP指标的计算结果的主要权重依然是CN指标, 因此, 本文定义一个新的评价指标LRPA, 引入RA指标计算过程中的相似度矩阵M_RA与PA指标计算过程中的相似度矩阵M_PA, 替换式(10)中第1项A²。LRPA指标计算如下:

$ {\mathit{\boldsymbol{S}}_{uv}} = {\mathit{\boldsymbol{M}}_{{\rm{RA}}}} \cdot {\mathit{\boldsymbol{M}}_{{\rm{PA}}}} + \alpha {\mathit{\boldsymbol{A}}^3} $

(11)

3.2 LRPA算法

本文用Matlab语言实现LRPA算法, 其中邻接矩阵处理函数FormNet、数据集划分函数DivideNet、AUC计算函数CalcAUC可参考文献[5]。

算法  LRPA算法

输入  预测网络的边列表linklist

输出  相似性矩阵S_uv, AUC得分

1.采用FormNet函数将网络的边列表转化成邻接矩阵的形式

2.采用DivideNet函数将网络的邻接矩阵进行训练集与测试集划分

3.构造向量获取节点度分布信息, 在邻接矩阵M中按行进行求和, 得到每个节点对应的度信息

4.将列向量deg_row与自身的转置向量deg_row’相乘, 得到基于偏好连接算法思想的相似性矩阵M_PA

5.计算邻接矩阵M按RA资源分配方法得到的相似性矩阵M_RA

6.计算最终的相似性矩阵S_uv

7.采用CalcAUC函数计算LRPA算法的AUC值

4 实验与结果分析

本文实验分2个阶段进行:

1) 在经典复杂网络数据集上进行LPRA算法测试, 观察式(11)中参数α对AUC值的影响。在选定较优α参数的基础上, 再与其他基于相似性指标的链路预测算法对比。

2) 通过选取斯坦福大学复杂网络分析计划(Stanford Network Analysis Project, SNAP)中的比特币OTC交易网络数据集, 进行LPRA算法的链路预测检验。

4.1 算法参数选取与预测性能比较

本文采用7个测试数据集^[5]:Router为Internet中路由器层次的网络, Power为美国西部电网, USAir为美国航空网络, Yeast为蛋白质相互作用网络, PB为美国某政治论坛博客网络, NS为发表过复杂网络为主题的科学家合作网络, C.elegans为线虫的神经网络。数据集的网络基本统计特征详见表 1。其中, N为网络的节点数量, C为网络聚类系数, M为网络的边数量, D为网络的直径, k为网络的平均度, L为平均最短路径。

文献[7]为LP算法采取的三阶路径参数为0.001。在此基础上, 本文对α选取的值范围设置为[-0.001, 0.002], 步长为0.000 2, 通过载入LPRA算法对7个经典复杂网络测试数据集进行计算, 观察较优的α取值特点, 测试结果如图 1所示。

根据图 1结果, 本文对α取值为0.000 1, 并与采用其他指标的算法进行预测对比。本文将已知的数据集划分90%作为训练集, 剩余10%作为测试集, 进行100次的10-折叠交叉验证, 计算LRPA与CN、Salton、Jaccard、Sorenson、AA、RA、PA、LP等经典链路预测算法的AUC对比, 结果如表 2所示。从表 2可以看出, 与CN、Salton、AA、RA以及LP算法相比, LRPA算法对网络结构信息的利用程度更全面。在充分利用共邻拓扑结构、节点度和三阶路径信息的基础上, LRPA算法在7个特征各异的复杂网络数据集中, 取得在Power、Yeast、PB、NS、C.elegans共计5个网络AUC值预测的优势。

4.2 比特币OTC网络预测

比特币OTC网络是斯坦福大学SNAP网收集的一个有向含权网络^[20]。由于比特币使用者保持匿名装填, 在比特币OTC网络中进行场外交易时, 有必要保持用户信誉的记录, 以防止欺诈和风险用户的交易, 因此该交易所对特定阶段的交易行为进行了匿名记录, 供研究机构后续研究。本文对该网络进行无权无向化处理, 处理后的网络含有节点5 881个, 边35 592条, 平均度为7.309, 网络直径为9, 平均路径长度3.571, 可视化图如图 2所示。

在对比分析比特币OTC网络时, 本文加入Precision评价指标辅助AUC指标进行分析。Precision中L取值为比特币OTC网络中的总边数, 实验结果如表 3所示。

比特币OTC网络结构较为复杂, 既有大群落聚集, 又存在大量无关联的零散节点, 相比4.1节中的网络, 其复杂程度更强, 它的直径居中, 度分布略接近于Yeast网络, 平均路径长度类似于USAir和C.elegans网络。通过表 3分析可知, LRPA算法在和其他8个算法的AUC比较中, 依然保持了AUC值最好的优势, 平均领先优势为7.33%, 各个算法之间的差距并不大。但在考虑到Precision指标后, 最佳的算法依次是LP、CN和LRPA。

实验结果表明, 在以AUC值为主要评价标准时, LRPA算法能够在各类不同特征的网络中都取得较好的预测优势。但在需要重点考虑前L个预测结果的Precision指标时, LRPA虽然仍能保持前列的Precision值, 但是和LP、CN、AA相比, 整体领先幅度要略低8.7%。结合2个阶段的实验结果, LRPA算法能够在各类复杂网络中较好地进行链路预测, 并在现实的比特币OTC网络中实现了较优的预测, 取得了AUC值第一, Precision值第三的整体表现。

5 结束语

本文介绍用于链路预测的相似性指标, 并结合预测算法的特性, 提出基于LRPA指标的链路预测算法, 充分利用节点度、路径结构等信息对网络链路进行预测。使用经典复杂网络数据集和比特币OTC网络数据进行实验, 并与其他链路预测算法的预测结果对比, 结果表明, LPRA算法具有良好的链路预测性能。下一步将从准确度出发优化LRPA, 并研究含权网络、有向网络条件下的LRPA应用问题。