复杂动态网络的链接预测

发布时间：2018-11-23 14:47

【摘要】：复杂网络的链接预测问题已经引起各个领域的越来越多的关注,如社会学、人类学、信息科学和计算机科学。至今为止,链路预测研究的工作大部分是基于静态网络上的。在静态的网络中,部分网络结构是已知的,其目标是预测其他的潜在的链接。在这样的静态网络中,链路的产生通常建模为一次性事件,我们的主要关注点是某些未知或未来的事件发生的可能性。在动态复杂的网络中,时序的拓扑信息是设计实体之间的相似度函数的主要依据之一。但现有的动态网络链路预测的算法往往不能充分应用时序的拓扑信息。一般来说,基于静态图表示的链接预测方法不能处理在动态网络中重复出现的链接,也无法识别动态网络中的时间序列模式,而这两者是动态网络链接预测中所用到的主要信息。因此,有必要研究适用于预测动态网络链接的有效方法。据我们所知,以前很少有文献研究以链接发生频率的时间序列作为输入的链接预测工作。在本文中,我们研究设计整合时间和拓扑信息的有效方法来预测具有一定的不确定性、顶点具有属性等动态链接的网络的未来链接的有效方法。本文的主要贡献如下：(1)我们提出了通过整合网络中的时序信息、社区结构和节点中心度的动态网络链路预测的方法。该方法所使用的这些拓扑特征对于预测复杂网络的潜在链接是非常重要的。时序信息有助于分析动态网络中的节点出现链接的规律。而社区结构则使我们可以根据两个顶点是否共位于同一个社区,来分析他们之间的连接的紧密程度。一个节点的中心度是度量它在网络内相对重要性的指标,和它在复杂网络中是否会有未来的链接具有高度的相关性。我们通过节点的特征向量中心度预测它未来的重要性,并作为链接预测的重要信息。我们整合网络中包括社区结构和中心度等各种拓扑信息,结合时序信息生成更加接近网络实际的模型,在此基础上进行动态网络链接预测。(2)我们提出了一种在不确定动态网络中进行链接预测的方法。由于观察数据的不精确性、不完全性以及噪声数据的干扰,在现实世界的网络中,不确定性是一个自然的特征。在这样的网络中,每条边与一个指示其在网络中的存在的概率值相关联。因此,在不确定网络进行链接预测的问题和在确定性网络的链接预测有本质的不同,它更具有挑战性。我们提出了在不确定链接的动态网络中的链接预测的方法。在该方法中,预测问题被形式化为一个设计在不确定时序网络中的随机游走。该算法首先将在不确定的网络链路预测问题转换成在确定性的网络随机游走问题。然后对每一个节点建立一个子图,这个节点和它的邻居之间的相似性得分可以在围绕这个节点的子图内计算,以减少计算时间。(3)我们提出了一种解决顶点带属性的动态网络链接预测问题的方法。在很多实际网络中,顶点所代表的对象具有各种属性,这些属性值对链接预测有很高的参考价值。为此,我们提出了一种基于非负矩阵分解(NMF)的方法的对顶点带属性的动态网络进行链接预测。该方法从网络中的动态拓扑结构以及顶点属性信息中获取隐特征,以获得更高的预测结果。我们提出了进行非负矩阵分解的迭代算法,并证明了这些算法的收敛性和正确性。通过非负矩阵分解可得到反映网络重要的动态隐拓扑特征的低阶矩阵,集成了动态网络中的时序信息和全局拓扑信息,并能获得更准确的结果。我们在真实社交网络上的实验结果表明,该方法能够有效预测顶点带属性社交网络中未来的链接,并取得比其他类似的方法更高质量的预测效果。(4)我们提出了一种基于抽样的方法,对动态网络中某些感兴趣的顶点进行链接预测。在许多动态网络的实际应用中,我们仅需要预测与某些感兴趣的顶点相关的链接,即只需计算与用户感兴趣的顶点之间的相似性得分,而不是预测网络中所有顶点对之间的相似性。显然在这种情况下,我们并不需要使用传统的方法对整个网络进行链接预测。为此,我们提出了一种基于抽样的快速方法来预测在动态网络中相关的感兴趣的节点的链接。在该方法中,我们使用一个适当的衰减因子来对较近的网络拓扑信息赋予较高的权重。然后,我们用随机游走的方法以网络中所关注的节点为中心构造一个加权子图。我们选择这个子图的一个适当的大小,从而使得所估计的相似度误差限定在一个给定的阈值范围内。由于相似性得分可以在一个很小的子图内计算得到,该算法可以大大减少计算时间。该方法也扩展到预测整个网络的潜在链接,以达到较高的处理速度和准确性。由于所提出的方法能够集成网络时序信息和全局拓扑信息,因而能获得更准确的预测结果。上述本文所提出的所有方法都已经在不同的实际网络上进行了测试。我们通过实验来验证所提出方法的性能,并通过设置不同的参数值来分析他们的结果,同时还与其他类似的方法比较他们的性能。大量的实验结果表明,我们的方法可在较少的时间内获得比其他方法质量较高的预测结果。
[Abstract]:......
【学位授予单位】：扬州大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5
，

本文编号：2351852