【作者】 钱唯；

【导师】 宋爱波；

【作者基本信息】 东南大学 ， 计算机科学与技术， 2016， 硕士

【摘要】 复杂网络中的链接预测一直以来都受到研究者们的关注,它通过分析已知网络的信息,建立复杂的模型来预测网络中未知的链接和未来可能产生的链接。链接预测对于探索以复杂网络为模型的应用背后的规律有着极为重要的作用。传统的链接预测主要针对于复杂网络的拓扑结构,试图通过已有的链接关系发现新的链接,从而探索网络中隐含的知识。然而,传统方法并未充分合理地利用复杂网络中蕴含的丰富属性信息,而属性信息对于网络中链接的形成具有重要的作用。基于以上考虑,本文将复杂网络中的多维属性信息与原有的链接预测模型进行结合,研究基于属性的链接预测问题。由于复杂网络中大多数点对之间未链接,而未链接的点对作为不可信反例无法有效用于传统预测模型中,因此本文利用PU学习思想(Positive and Unlabeled Learning),提出一种基于属性的链接模式挖掘算法,该算法将未链接的点对以合理的方式引入训练模型,从组合特征的角度挖掘链接模式,并设计D指标过滤具有区分力的链接模式,通过基于属性的链接模式从整体上刻画网络中链接形成的原因。同时针对链接预测问题,本文通过图的聚集计算求解基于属性的链接模式强度,并利用模式构造个性化概率转移矩阵,从而建立基于链接模式的局部随机游走模型(PBLRW).本文提出的预测方法区别于传统的随机游走预测方法,以属性特征作为依据,构建个性化的概率转移矩阵,使得关系紧密的节点之间获得更高的随机游走概率,从而最终产生更为精确的预测效果。本文分别在UCI数据集、政治博客(Political Blogs)数据集和新浪微博数据集上进行了多组实验,实验结果表明：(1)本文提出的链接模式挖掘方法能够挖掘并过滤出具有较强区分力的模式,这些模式对于类别具有明显的区分能力,因此能够很好地刻画链接是否产生的内在原因；(2)本文提出的基于模式的链接预测模型,能够充分利用属性知识构造个性化的概率转移矩阵,克服了传统随机游走模型中转移概率固定的缺陷；(3)对于政治博客数据集和新浪微博数据集的实验表明,本文提出的模型在各项综合指标上均优于传统的链接预测方法和基于分类的方法。更多还原

【Abstract】 Complex network, as the fundamental network model, has been widely adopted in various scenarios in everyday life and researches. Great amount of valuable information is under exploited through kinds of strategies, among which link prediction gains the most attention. Based on the analysis of observable network, link prediction aims to build complicated mathematical model to predict the existence of missing links and future links. Undoubtedly, the employment of link prediction plays an important role in exploring the underlying mechanism of complex networks. Conventional link prediction algorithms mainly focus on the analysis of topological structure of networks to uncover the hidden information. However, most of them ignore the multidimensional attributes knowledge related to nodes or edges, which matters a lot to the forming links in complex networks. So, we try to employ the multidimensional attributes to conventional link prediction model and propose the attributed-based link prediction problem.Due to the fact that most of node pairs in complex networks are unlinked, which can’t be employed by traditional learning method, we propose a link pattern mining algorithm, inspired by PU learning (Positive and Unlabeled Learning), and can extract and filter discriminative link patterns in complex networks. These link patterns present the overall factor that is closely related to the links of nodes. Then, the link pattern strength estimation algorithm is proposed based on graph aggregation and finally we present the pattern-based local random walk model for link prediction. Our proposed model differs from conventional random walk models mainly in the construction of transition matrix. We aims at personalize the matrix according to the link patterns of each edge and reallocate the closer node pairs with a generally higher transition probability.Experiments are conducted on UCI data sets, political blogs data set and Sina microblog dataset. The results demonstrate the following conclusions. (1) The proposed pattern mining algorithm can exactly extract and filter more discriminative patterns, and can undercover the hidden factors that contributes to the link formation. (2) Our proposed pattern-based link prediction model can fully take advantage of various attributes knowledge and personalize the transition matrix more accurately. (3) The results of real-world networks shows that pattern-based link prediction model performs significantly against conventional link prediction algorithms and classification-based strategies.更多还原