基于局部随机游走的时序链路预测算法

发布时间：2020-10-31 04:51

　　 链路预测是复杂网络研究中的一个重要内容,传统的静态链路预测方法忽略了网络演化的时间特性,而时序链路预测可以利用历史网络的一些信息,更好地做出预测。首先,本文基于局部随机游走的静态链路预测方法,针对无权无向网络中的时序链路预测问题,提出一种时序随机游走方法,主要思想是利用时间和网络拓扑信息,将每一时刻下网络的马尔科夫概率转移矩阵组合到一个变换矩阵,然后应用局部随机游走方法获得最终的预测结果。本文在两个真实网络数据集上进行实验验证,结果表明本文算法能有效提高链路预测精度。其次,本文介绍了一些加权相似度指标,将提出的时序随机游走方法修改成加权形式的,并应用到加权网络中。本文通过实验对比静态链路预测算法在加权网络与无权网络中的性能,发现有小部分算法在加权网络中的性能还不如在无权网络中的性能好,由此本文联想到弱链接理论,并对这个理论加以分析。另外,本文通过实验分析了修改后的时序随机游走算法在加权网络中的表现。实验结果表明,修改后的算法在加权网络中的预测精度有所提高。
【学位单位】：暨南大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：

(a) (b)(c) (d)图2-1 四种类型的图如图2-1所示，根据图中的边是否有权、是否有向，分为四种类型：(1) 无权无向图：如图2-1(a)所示，图中的边是无权的、无向的。无权意味着图中的边的权值均相等(通常可以假设每条边的权值为1)。所谓无向意味着任意点对 与 对应于相同的边，节点 和 是无向边 的两个端点。比如，

历史拓扑图，是用来检测链路预测算法性能的数据依据， 代表连边概率矩阵，是一种对未来时刻网络拓扑结构的猜测。图2-2 无权无向网络链路预测图2.2 随机过程与马尔科夫链定义1(随机过程) 设给定概率空间 和参数集 ，若对每一，都有定义在 上的一个随机变量 与之对应，则称依赖于参数 的随机变量族 为一随机过程，记为，简记为 或 。其中 是参数，在实际问题中参数 常表示时间， 称为参数空间

若所有分数全是随机产生的，那么 。因此，AUC值大于0.5的程度可以衡量算法精确的程度。移动窗口切片方法(如图2-3所示)是计算时序链路预测方法AUC值时选取训练集、测试集的一种方法，针对每个时间窗口 的取值，首先选取时序网络图中前 个时刻网络快照作为训练集，以 时刻网络快照为测试集，计算一次AUC值，然后将时间窗口后移一个单位，计算下一个AUC值，这样就可以得到每一次独立实验的AUC值，然后对这些值取平均作为对应时间窗口 取值时链路预测方法的AUC值[1]。图2-3 训练集和测试集的选取…训练集测试集…训练集测试集
【参考文献】

相关期刊论文 前2条

1 邓志宏;老松杨;白亮;;基于预测误差修正的时序链路预测方法[J];电子与信息学报;2014年02期

2 吕琳媛;;复杂网络链路预测[J];电子科技大学学报;2010年05期

本文编号：2863470