论文信息

Link Weight Prediction Using Supervised Learning Methods and Its Applicationto Yelp Layered Network

原文地址：https://ieeexplore.ieee.org/abstract/document/8281007/

摘要

Real-world networks feature weights of interactions, where link weights often represent some physical attributes. In many situations, to recover the missing data or predict the network evolution, we need to predict link weights in a network. In this paper, we first proposed a series of new centrality indices for links in line graph. Then, utilizing these line graph indices, as well as a number of original graph indices, we designed three supervised learning methods to realize link weight prediction both in the networks of single layer and multiple layers, which perform much better than several recently proposed baseline methods. We found that the resource allocation index (RA) plays a more important role in the weight prediction than other topological properties, and the line graph indices are at least as important as the original graph indices in link weight prediction. In particular, the success application of our methods on Yelp layered network suggests that we can indeed predict the offline co-foraging behaviors of users just based on their online social interactions, which may open a new direction for link weight prediction algorithms, and meanwhile provide insights to design better restaurant recommendation systems.

真实世界的网络具有交互的权重，其中链接权重往往代表一些物理属性。在许多情况下，为了恢复丢失的数据或预测网络的演变，我们需要预测网络中的链接权重。本文首先针对线图中的链接提出了一系列新的中心性指标。然后，利用这些线图指标，以及一些原始的图指标，我们设计了三种监督学习方法来实现单层和多层网络中的链接权重预测，其性能远远优于最近提出的几种基线方法。我们发现资源分配指标( RA )比其他拓扑属性在权重预测中发挥着更重要的作用，而线图指标在链路权重预测中至少与原始图指标同等重要。特别地，我们的方法在Yelp分层网络上的成功应用表明我们确实可以进行离线预测，这可能为链接权重预测算法开辟一个新的方向，同时也为设计更好的推荐系统提供启示。

主要内容（contributions）

首先，将原始的无权网络转化为线图。线图中的节点表示原始图中的链接，如果对应的链接在原始图中共享相同的终端节点，则两个节点在线图中连接。然后我们利用线图中的节点中心性指标来定义原始图中链接的重要性。
其次，提取了两组特征，包括原图特征和线图特征。原始的图特征包含大多数相似性特征，这些特征可以被看作是与链接相关联的成对节点的特征。线图特征包含中心性特征，可以直接看作边特征。然后利用它们来建立监督学习算法，结果显示这些算法优于基线方法。实验表明，原图特征和线图特征互为补充。此外，还考察了特征提取的时间复杂度。
第三，建立了一个Yelp分层网络，同时捕获了线上的朋友关系和线下的觅食行为，其中链接表示朋友关系，权重表示两个顾客访问同一餐馆的次数。我们进一步使用从在线社交链接获得的拓扑信息来估计链接权重。这个数据集可以作为一个基准来测试跨层网络的链路权重预测。

图模型和评价指标

一个无向且加权的网络建模为图，其中V、E和W分别为节点、边和权值的集合。对于每个链接的权重表示为w_i,j，且w_i,j=w_j,i，即不考虑链接的方向。
将权重集W随机分为两部分：训练集W_T和测试集W_V，其中。
在本文中，使用该领域的两个传统度量来衡量拟合优度，即Pearson Correlation Coefﬁcient( PCC )和均方根误差( RMSE )，定义如下：

Pearson Correlation Coefﬁcient( PCC )

其中，n为样本容量，x和s_x分别为变量x的n个样本的均值和标准差，y和s_y分别为变量y的n个样本的均值和标准差。PCC是两个变量x和y之间线性相关程度的度量，PCC ∈ [-1,1]。如果PCC > 0，则认为x, y为正相关；PCC < 0，则认为x, y为负相关; PCC=0, 则认为x, y不相关。

Root Mean Squared Error（RMSE）

特征指标

在这项工作中，提取了两组特征：原图特征和线图特征。在原始图中，相似性指标通常用于链接预测，试图估计链接存在的可能性。似然性通常与成对节点的相似性相关联。然而，在许多现实世界的网络中，链接的权重可能具有自己的物理意义，而这些物理意义可能无法通过关联节点之间的相似性来捕捉。因此，在本研究中，首先将原始图转换为线图，然后利用线图中的中心性指标直接提取原始图中的边特征。

原图特征指标

在原始图中，相似性指标是直接定义的，显示了两个节点共享的许多共同特征。考虑一对节点，即i和j，为它们之间的相似性指标分配一个分数s_ij。此外，还计算了边介数作为补充。特别地，原始图中的特征包括：

Common Neighbors (CN)

表示节点i的邻居集合。
Salton Index (SA)

其中，k_i和k_j分别表示节点i和节点j的度。

Jaccard Index (JAC)

Jaccard 是一个经典的统计参数，用于比较样本集的相似性或多样性。
Hub Promoted Index (HPI)

在这种度量下，由于分母只由较低的度决定，与枢纽节点相邻的链接很可能被赋予高分数。
Hub Depressed Index (HDI)
Srensen Index (SI)

这个指标是上述两者的折中，并考虑了节点i和j的平均度，这通常用于生态社区数据

Leicht-Holme-Newman Index (LHN)
Adamic-Adar Index (AA)

该指标的主要假设是度数较小的共同邻居对相似度的贡献较大。例如，在一个社交网络中，许多人可能认识一个名人，但他们自己可能不认识对方。
Resource Allocation Index

RA指数接近AA，但对度数较高的共同邻居惩罚较多。在某些情况下，RA在链路预测中的表现优于AA。
Preferential Attachment Index (PA)
Friends-Measure (FM)

当节点u和v是同一个节点或者它们之间存在链路时，=1，否则等于0。
Local Path Index (LP)

A是邻接矩阵。
Local Random Walk (LRW)
Edge Betweenness (EB)

原始图转线图

在网络科学中，节点中心性经常被用来识别重要的节点为了研究链接的重要性，在这里，我们转换原始的无权网络到线图，然后利用节点中心性内联图来定义原始图中链接的重要性。在这个表示中，线图中的节点是原始图中的链接，如果对应的链接在原始图中共享同一个终端节点，则两个节点之间存在连接。

基于这种变换，通过线图中的节点中心性指标来定义线图特征，利用这些特征直接捕获原始图中链接的重要性。

线图特征指标

Degree Centrality (DC)

其中k_i是节点i的度，N是图中节点的总数。
Closeness Centrality (CC)

其中di_j表示线图中节点i和j之间的最短路径长度。
Betweenness Centrality (BC)

其中，g_st是线图中节点s和t之间最短路径的总数，ni_st表示通过节点i的节点s和t之间最短路径的数目。
Eigenvector Centrality (EC)

其中a_ij是线图的邻接矩阵的元素，如果节点i和j相连，a_ij=1，否则a_ij=0。
PageRank (PR)
式中：c为介于0和1之间的自由参数。
H-index (H)