浅议多层网络层间结构信息对链路预测的影响

Analysis of the Influence of Interlayer Structure Information of Multi-Layer Networks on Link Prediction

摘要: 文章讨论了多层网络的链路预测问题，提出了结合多层网络层间拓扑结构信息的链路预测方法，分析了层间结构信息对多层网络链路预测精度的影响。

Abstract: This paper discusses the link prediction problem of multi-layer networks and proposes a link prediction method that combines the information of the topological structure of the multi-layer network. We further analyze the influence of the information of the inter-layer structure on the prediction accuracy of the multilayer network link.

1. 引言

近年来，网络在很多领域应用广泛，包括社交网络、计算机网络、人类疾病基因网等。链路预测是网络统计分析的一个基本问题 [1]。链路预测旨在基于观测到的网络的拓扑结构或者节点的特征信息预测网络中丢失的或者将会发生的链接。链路预测结果在许多学科中具有非常重要的作用，比如精准的预测结果可以指导生物学的实验—因为大部分观察到的生物网络，只是真实网络中很小的一部分，需要通过大量实验来确定其他的部分，又如社交网络的预测结果还可以用来进行好友预测—如果能够猜到用户未来交友的趋势，这种网络推荐就会变得非常精准。好的预测算法本身，还给出了很多网络演化可能机制的暗示。

鉴于现实网络的复杂多样性，单层网络已经不能满足人们对复杂系统的精确描述，近年来，人们对网络的研究逐渐从单层网络过渡到多层网络 [2]。在多层网络中，利用网络层间信息对目标层网络进行链路预测是热点问题之一，文献 [3] 提出了一类基于Adamic相似度的多层网络的链路预测方法，该方法有效地解决稀疏网络的预测问题；文献 [4] 提出了基于概率模型的多层网络的链路预测方法；文献 [5] 提出了基于节点相似度的多层网络链路预测方法，该相似度均融合了层间和层内的结构信息。从上述文献的工作可见，合理地利用多层网络中的层间结构信息可以有效地提高链路预测的精度。基于此，本文进一步探讨多层网络的层间信息对目标层网络的链路预测的影响，提出了一类新的融合节点间相似度的多层网络的链路预测方法，给出基于节点对的相似度，即两对节点对间越相似，那么它们潜在的链接概率越相近。

2. 方法

首先给出本文中用到的记号。假设多层网络为 $G=\left(G^{\left(1\right)},\cdots ,G^{\left(M\right)}\right)$，其中M代表层数，N代表节点个数， $G^{\left(m\right)}=\left(V^{\left(m\right)},E^{\left(m\right)}\right)$ 代表第m层网络，该层网络的节点集合和边集合分别为 $V^{\left(m\right)}$ 和 $E^{\left(m\right)}$。本文假设所有网络层都是无向网络且它们的节点集合相同，即 $\left|V^{\left(1\right)}\right|=\cdots =\left|V^{\left(M\right)}\right|=N$。令 $A^{\left(m\right)}$ 表示 $G^{\left(m\right)}$ 层网络对应的邻接矩阵，令 $S_{ij}^{\left(k\right)}$ 表示第k层网络节点 $i,j$ 间的相似度，本文拟用Jaccard指标计算 $S_{ij}^{\left(k\right)}$，即 $S_{ij}^{\left(k\right)}=\frac{\left|N^{\left(k\right)}\left(i\right)\cap N^{\left(k\right)}\left(j\right)\right|}{\left|N^{\left(k\right)}\left(i\right)\cup N^{\left(k\right)}\left(j\right)\right|}$，其中 $N^{\left(k\right)}\left(i\right)$ 是第k层网络节点i的邻居节点的集合。

下面给出第k层网络的链路预测准则(LPIMN)：

$\begin{array}{c}{Q}^{\left(k\right)}=\underset{P^{\left(k\right)}}{\arg \min }\frac{1}{N^2}{{\displaystyle \underset{ij}{\sum }\left(A_{ij}^{\left(k\right)}-P_{ij}^{\left(k\right)}\right)}}^2+\frac{1}{N^4}{\displaystyle \underset{ij{i}^{\prime }{j}^{\prime }}{\sum }{S}_{i{i}^{\prime }}^{\left(k\right)}{S}_{j{j}^{\prime }}^{\left(k\right)}{\left(P_{ij}^{\left(k\right)}-P_{i^{\prime }{j}^{\prime }}^{\left(k\right)}\right)}^2}\\ +\frac{1}{N^2}{\displaystyle \underset{kl}{\sum }{{\displaystyle \underset{ij{i}^{\prime }{j}^{\prime }}{\sum }{\theta }_{kl}\left(A_{ij}^{\left(k\right)}-A_{ij}^{\left(l\right)}\right)}}^2}\end{array}$ (1)

其中 $P_{ij}^{\left(k\right)}$ 是待估的网络层k中节点 $i,j$ 间的潜在的链接概率， ${\theta }_{kl}$ 表示层间信息的权重， 本文中令 ${\theta }_{kl}=\frac{1}{N}{\displaystyle \underset{i}{\sum }\frac{{\displaystyle \underset{j}{\sum }{A}_{ij}^{\left(l\right)}{A}_{ij}^{\left(k\right)}}}{{\displaystyle \underset{j}{\sum }{A}_{ij}^{\left(l\right)}+{\displaystyle \underset{j}{\sum }{A}_{ij}^{\left(l\right)}-{\displaystyle \underset{j}{\sum }{A}_{ij}^{\left(l\right)}{A}_{ij}^{\left(k\right)}}}}}}$。

本文利用分块梯度下降法求解式(1)，首先对式(1)关于 $P^{\left(k\right)}$ 求导得：

$\begin{array}{c}\frac{\partial Q^{\left(k\right)}}{\partial P_{i\cdot }^{\left(k\right)}}=\frac{2}{N^2}\left(P_{i\cdot }^{\left(k\right)}-A_{i\cdot }^{\left(k\right)}\right)+\frac{1}{N^4}\left(S_{ii}^{\left(k\right)}\left(W^{\left(k\right)}{P}_{i\cdot }^{\left(k\right)}-S^{\left(k\right)}{P}_{i\cdot }^{\left(k\right)}\right)\right)\\ +{\displaystyle \underset{i^{\prime }\ne i}{\sum }{S}_{i{i}^{\prime }}^{\left(k\right)}\left(W^{\left(k\right)}{P}_{i\cdot }^{\left(k\right)}-S^{\left(k\right)}{P}_{i\cdot }^{\left(k\right)}\right)}+\frac{1}{N^2}\left({\displaystyle \underset{l\ne k}{\sum }{\theta }_{kl}}\left(P_{i\cdot }^{\left(k\right)}-A_{i\cdot }^{\left(l\right)}\right)\right)\end{array}$

其中 $W^{\left(k\right)}$ 是一个n阶方阵， $W_{ii}^{\left(k\right)}={\displaystyle \underset{j}{\sum }{S}_{ij}^{\left(k\right)}}$， $P_{i\cdot }^{\left(k\right)}$ 是行向量。那么令 $\frac{\partial Q^{\left(k\right)}}{\partial P_{i\cdot }^{\left(k\right)}}=0$，可得第 $\left(k+1\right)$ 次迭代中 $P_{i\cdot }^{\left(k\right)}$ 的估计值为

$\begin{array}{l}{P}_{i\cdot }^{\left(k\right)\left(t+1\right)}\leftarrow {\left[N^{2}I+2{\lambda }_1{S}_{ii}^{\left(k\right)}\left(W^{\left(k\right)}-S^{\left(k\right)}+{\displaystyle \underset{i^{\prime }\ne i}{\sum }{S}_{i{i}^{\prime }}^{\left(k\right)}}{W}^{\left(k\right)}\right)+{\lambda }_1{N}^2{\displaystyle \underset{l\ne k}{\sum }{\theta }_{kl}}\right]}^{-1}\\ {\left[N^2{A}_{i\cdot }^{\left(k\right)}+2{\lambda }_1{\displaystyle \underset{i^{\prime }\ne i}{\sum }{S}_{i{i}^{\prime }}^{\left(k\right)}}S{P}_{i\cdot }^{\left(k\right)\left(t\right)}+{\lambda }_1{N}^2{\displaystyle \underset{l\ne k}{\sum }{\theta }_{kl}{A}_{i\cdot }^{\left(l\right)}}\right]}^{-1}\end{array}$

3. 实证

本节通过两个实际多层网络数据分析所提方法LPIMN和现有的部分链路预测方法在预测多层网络链接时的有效性。用于对比的算法有Najari等 [5] 提出的LPIS算法，Yao等 [6] 提出的NSILR算法，Zhao等 [7] 提出的LPPN算法和Zhang等 [8] 提出的ENNS算法，其中LPPN和ENNS针对单层网络的链路预测，而NSILR和LPIS针对多层网络链路预测。用于实证分析的两个实际数据为：1) 律师多层网络数据 [6]，包含71个节点，3个网络层(Advice, Work, Friend)；2) AU-CS数据 [5]，包含61个节点，5个网络层(Work, Lunch, Facebook, Leisure, Coauthor)。实验结果评价指标为AUC [5]，AUC是公认的评价链路预测算法精度的指标， $\text{AUC}\in \left[0,1\right]$，其值越大，说明算法的精度越高。具体的实验结果如表1和表2所示，AUC数值显示LPIMN算法在处理多层网络链接预测问题时更为有效，虽然NSILR和LPIS两个算法均综合考虑了多层网络的层间信息，但是它们在处理有向网络图和连边较少即稀疏网络图时不及LPIMN算法的优势明显，LPIMN算法很好地结合了网络的层间信息并根据其他层与目标层的相关性有针对性地获取信息，实质性地改进了算法的精度。

Table 1. The AUC values obtained by five different methods on lawyers network

表1. 五种不同方法作用于律师三层网络数据得到的AUC值

Table 2. The AUC values obtained by five different methods on AU-CS data

表2. 五种不同方法作用AU-CS数据得到的AUC值

4. 结论

多层网络在实际中应用广泛，在诸多领域中均涉及到网络，比如计算机通讯系统，金融管理系统，新冠病毒传播网络等，但是多层网络的统计研究尚处于成长阶段，这就要求我们平时在课程学习中要在理论推导方面多下功夫，逐步丰富多层网络的统计研究，其中多层网络的链路预测又属热门课题之一，合理地利用多层网络层间信息和层内信息有效地预测节点间潜在的链接概率将是我们继续的研究方向。

基金项目

安徽省高校自然科学研究重点项目(KJ2020A0023)，淮北师范大学重点教研项目(JY19009)。