A Feasible T emporal Links Prediction Framework Combining with Improved Gravity Model
摘要： 社会网络分析是一门涉及信息学、数学、社会学、管理学、心理学等多学科的研究。链接预测作为一项应用广泛的基础研究，越来越受到科学界的关注。传统的基于图论的研究已经取得了大量的成果，但存在着无法处理动态行为和预测精度低的问题。针对这一问题，本文采用对角对称超邻接矩阵表示动态社交网络，并结合改进的引力模型提出了时间链路预测框架。在几个真实数据集上的广泛实验证实了其优于竞争对手，这有利于在社交网络中推荐朋友。这对于揭示时间网络的演变，促进社会应用的商业利益具有重要意义。
关键词：社交网络;时间链接预测;引力模型;多层网络 （social network; temporal links prediction; gravity model; multilayer network）
1、介绍
社会网络的分析越来越受到社会学领域的关注。分析和探讨了社会客体之间的潜在关系。社交媒体的快速发展给我们带来了丰富的数据来源，同时也带来了数据不完整、动态变化等巨大挑战。一方面，研究人员面临着数据不完整的问题，社交平台上只能收集到一部分的社交信息。另一方面，动态变化可能导致节点和链接在未来的出现和消失，使底层图纵向。
链接预测作为社会网络分析的基础研究，提出从网络的现有部分中检测未观测到的链接，或者从当前网络结构[6]中预测未来的链接。前一种研究，也被称为缺失连接预测，在过去的十年中取得了丰硕的成果，而预测未来的连接，在有限的社会信息下估计未来的连接，更具挑战性。本研究具有重要意义，不仅揭示了社交网络的演变，而且有利于网络管理，比如推广有用的链接，禁止有害的互动。例如，一个推荐系统，作为时间链接预测的典型应用，它是为个人设计的，通过有效的预测结果来交朋友或购买商品，这给企业带来了可观的收益。
人们已经做了许多尝试来解决时间链路预测的问题，但这是一个真正困难的任务。首先，观察到的社会信息非常有限，这导致研究中经常采用光滑性假设，因此在网络发生严重变化时，方法可能会出现无能。其次，纵向偏差是不可避免的，动态变化必须转向未来。
最后，广泛网络的不同观察改变对称性随着时间的推移也会导致不同的社会结构，这可能会产生极其不同的预测结果。本文针对时间网络链路预测的问题，提出了一种动态相似度框架和改进的重力模型，用于估计时间网络的未来链路。
本文的其余部分组织如下。第2节介绍了链路预测的相关工作。第3节给出了数学模型、改进的重力模型和预测时间链路的框架。第4节给出了实验和分析，包括对不同层次分离的真实数据集的对比实验，验证了该方法的可行性和准确性。第5部分对全文进行了总结，并给出了结论。
2、相关工作
链路预测在2005年[4]首次在SIGKDD上提出。随后，Liben-Nowell和Kleinber回顾了社交网络中的链接预测，这吸引了越来越多的学者投身于这个领域[9]。2011年，Lu总结了现有的方法，将其分为三类:结构相似度指数、最大似然逼近和概率模型[10]。2017年，Pech等[11]将鲁棒主成分分析(robust principal component analysis, robust PCA)方法引入到链路预测中，估计邻接矩阵中缺失的链路。实验结果表明，当目标网络连通且足够密集时，该方法比现有的算法具有更高的精度。表1对经典谓词进行了简要总结。
未来链路预测[12,13]，即时间链路预测，是预测网络在下一个周期状态下会出现的链路。在时间网络方面，提出了时间图[14]、演化图[15]、时变图、动态网络[16]等一系列数学模型。有三种典型模型可用于描述动态行为:快照、接触序列和间隔图
3、模型和方法
3.1 模型
链路预测问题描述为用给定的网络模型G = (V,E)估计所有可能链路的可能性，其中V = {v1,v2，…，vn}为节点集，E = {(vi,vj)}， (vi,vj∈V)为边集，假设可以通过某种算法计算G中每两个节点之间的链接的似然度(或相似度)，然后升序排序;未来链路由top-k链路得到，其中k为目标链路数量。
在本文中，我们使用生成的多层网络模型[43]，它可以将时间网络转换为一个可观的快照集合。图1为欧洲大型研究机构[44]数据的多层网络模型的示意图，图2为对应的超邻接矩阵。
假设有一个时间网络GT，其中每个片被建模为一个单层网络(即单层网络)，T为层的总数，T = 1,2，…，T;模型表示为:
其中，∑Vt ∑Et是每片节点和边在每一个时间片的并集。为了简化研究问题，我们利用无向图来表示每个快照中的网络结构。因此，时间网络可以用对角对称的超邻接矩阵表示：
其中A1, A2，…的邻接矩阵的时间1,2，…， T，分别表示链接(即层内边)。N为节点总数，通过N =∑1≤l≤T|Vl|可计算出。I表示位于连续快照中的节点(即层间边)的关系。利用之前从时间1到T−1的时间信息，我们的目标是预测最后时刻T的链接，问题描述为
3.2 定义
重力是物体之间的力，它与物体的质量和两个物体之间的距离有关。本文中我们关注的重力被用来描述两个节点之间的相互作用的强度。网络[46]中的重力定义为
