一种基于博弈论的时序网络链路预测方法  

A Link Prediction Approach in Temporal Networks Based on Game Theory

作　　者：刘留 王煜尧 倪琦瑄 曹杰[2] 卜湛 Liu Liu;Wang Yuyao;Ni Qixuan;Cao Jie;Bu Zhan(College of Information Engineering,Nanjing University of Finance and Economics,Nanjing 210013;School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094)

机构地区：[1]南京财经大学信息工程学院,南京210013 [2]南京理工大学计算机科学与工程学院,南京210094

出　　处：《计算机研究与发展》2019年第9期1953-1964,共12页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(71871109,91646204,71801123,71871233)~~

摘　　要：链路预测是复杂网络分析领域的一项重要研究课题,可被应用于许多实际应用场景,如推荐系统、信息检索和市场分析等.不同于传统的链路预测问题,针对有时间窗口的时序链路集合,需预测未来任意时刻链路的存在情况,即探究时序网络的演化机制.为解决这一问题,结合生存分析和博弈论,提出一种有效的半监督学习框架.首先,定义一个ε-邻接网络序列模型,并利用每条链路的时间戳信息生成真实的网络演化序列.为捕捉网络演化规律,为每条链路定义一组基于邻居相似性的特征向量,并采用Cox比例风险模型来估计该特征向量的协变量系数.为缩小搜索空间,提出一种基于博弈的双向选择机制来预测未来的网络拓扑结构.最后,提出一种基于多智能体自治计算的网络演化预测算法,并在多个真实时序网络数据集上验证了算法的有效性和高效性.Link prediction is an important task in complex network analysis, which can be applied to many real-world practical scenarios such as recommender systems, information retrieval, and marketing analysis. Different from the traditional link prediction problem, this paper predicts the existence of the link at any time in the future based on the set of temporal links in a given time window, that is, the evolution mechanism of the temporal network. To explore this question, we propose a novel semi-supervised learning framework, which integrates both survival analysis and game theory. First, we carefully define the ε-adjacent network sequence, and make use of time stamp on each link to generate the ground-truth network evolution sequence. Next, to capture the law of network evolution, we employ the Cox proportional hazard model to study the relative hazard associated with each temporal link, so as to estimate the covariate s coefficient associated with a set of neighborhood-based proximity features. To compress the searching space, we further propose a game theory based two-way selection mechanism to inference the future network topology. We finally propose a network evolution prediction algorithm based on autonomy-oriented computing, and demonstrate both the effectiveness and the efficiency of the proposed algorithm on real-world temporal networks.

关 键 词：链路预测 时序网络 生存分析 博弈论 自治计算 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]