【论文导读】- Link Weight Prediction Using Supervised Learning Methods

举报
1+1=王 发表于 2022/12/28 09:35:49 2022/12/28
【摘要】 【论文导读】- Link Weight Prediction Using Supervised Learning Methods(使用监督学习方法的链路权重预测及其在Yelp网络中的应用)

@[TOC]

论文信息

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)

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

图模型和评价指标

一个无向且加权的网络建模为图在这里插入图片描述,其中V、E和W分别为节点、边和权值的集合。对于每个链接( i , j)2 E,的权重表示为w~i,j~,且w~i,j~=w~j,i~,即不考虑链接的方向。
将权重集W随机分为两部分:训练集W~T~和测试集W~V~,其中在这里插入图片描述
在本文中,使用该领域的两个传统度量来衡量拟合优度,即Pearson Correlation Coefficient( PCC )和均方根误差( RMSE ),定义如下:

  • Pearson Correlation Coefficient( 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~。此外,还计算了边介数作为补充。特别地,原始图中的特征包括:

  1. Common Neighbors (CN)
    在这里插入图片描述
    在这里插入图片描述表示节点i的邻居集合。

  2. Salton Index (SA)
    在这里插入图片描述

其中,k~i~和k~j~分别表示节点i和节点j的度。

  1. Jaccard Index (JAC)
    在这里插入图片描述
    Jaccard 是一个经典的统计参数,用于比较样本集的相似性或多样性。

  2. Hub Promoted Index (HPI)
    在这里插入图片描述
    在这种度量下,由于分母只由较低的度决定,与枢纽节点相邻的链接很可能被赋予高分数。

  3. Hub Depressed Index (HDI)
    在这里插入图片描述

  4. Srensen Index (SI)
    在这里插入图片描述

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

  1. Leicht-Holme-Newman Index (LHN)
    在这里插入图片描述

  2. Adamic-Adar Index (AA)
    在这里插入图片描述
    该指标的主要假设是度数较小的共同邻居对相似度的贡献较大。例如,在一个社交网络中,许多人可能认识一个名人,但他们自己可能不认识对方。

  3. Resource Allocation Index
    在这里插入图片描述
    RA指数接近AA,但对度数较高的共同邻居惩罚较多。在某些情况下,RA在链路预测中的表现优于AA。

  4. Preferential Attachment Index (PA)
    在这里插入图片描述

  5. Friends-Measure (FM)
    在这里插入图片描述
    当节点u和v是同一个节点或者它们之间存在链路时,在这里插入图片描述=1,否则等于0。

  6. Local Path Index (LP)
    在这里插入图片描述
    A是邻接矩阵。

  7. Local Random Walk (LRW)
    在这里插入图片描述

  8. Edge Betweenness (EB)
    在这里插入图片描述

原始图转线图

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

在这里插入图片描述

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

线图特征指标

  1. Degree Centrality (DC)
    在这里插入图片描述
    其中k~i~是节点i的度,N是图中节点的总数。

  2. Closeness Centrality (CC)
    在这里插入图片描述
    其中di~j~表示线图中节点i和j之间的最短路径长度。

  3. Betweenness Centrality (BC)
    在这里插入图片描述
    其中,g~st~是线图中节点s和t之间最短路径的总数,ni~st~表示通过节点i的节点s和t之间最短路径的数目。

  4. Eigenvector Centrality (EC)
    在这里插入图片描述
    其中a~ij~是线图的邻接矩阵的元素,如果节点i和j相连,a~ij~=1,否则a~ij~=0。

  5. PageRank (PR)
    在这里插入图片描述式中:c为介于0和1之间的自由参数。

  6. Clustering Coefficient ©
    在这里插入图片描述
    式中:L~i~为节点i的k~i~个邻居之间的链接数。

  7. H-index (H)
    在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。