链路预测(Link Prediction)是数据挖掘、复杂网络分析等领域的热点研究问题,利用链路预测技术可以预测出网络中尚未存在的链路或者识别出网络中的虚假链路,帮助认识复杂网络的演化机制。链接预测的应用非常广泛,例如:预测社会中人与人之间的朋友关系、电子邮件交互关系、电话通话关系以及合作关系等。随着互联网的日益兴起,网络数据呈爆炸式增长,如何使链路预测技术能够准确地应用于复杂的大规模数据环境中,是目前国内外数据挖掘、复杂网络分析等领域研究学者的研究热点。最初的链路预测方法是基于同构信息网进行的,它要求信息网络中的节点类型相同且节点之间具有单一的关联关系,因此具有一定局限性。基于异构信息网的链路预测方法虽然可支持具有多种节点类型及多种关联关系的信息网络上的链路预测,但已有工作所考虑的因素相对有限(或者是图的拓扑结构,或者是语义信息),且大多数工作仅适用于静态图上的链路预测,而忽略了信息网络的时序特征。为此,本文针对异构信息网中的链路预测进行研究,提出了一种语义结构和时序特征相结合的链路预测方法,该方法在链路预测时综合考虑了图的拓扑结构、语义信息以及时序特征等多种因素,有效地提高了链路预测的准确性。本文的主要工作及贡献点如下:(1)系统地介绍了链路预测的国内外研究现状,简要概括了代表性的相关工作,指出其优缺点,并芬析现存研究的不足之处。(2)针对已有问题,提出了两种链路预测模型:·首先,提出了一种基于语义结构图的链路预测模型(Semantic Structure Graph based Link Prediction Model,简称SLP模型),该模型将链路预测分为两个阶段:第一阶段是构建语义结构图,其目标是能够准确地反映出图的拓扑结构、节点间语义相关性和关联强度等。第二阶段是计算随机游走概率,并对参数进行优化。·另外,在SLP模型基础上,提出了一种语义结构和时序特征相结合的链路预测模型(Semantic Structure and Time Characteristics Combined Link Prediction Model,简称STLP模型)。与传统链路预测模型不同,STLP模型在链路预测时综合考虑了图的拓扑结构、语义信息以及时序特征等多种因素,有效地提高了链路预测的准确性。(3)基于SLP模型和STLP模型分别提出了基于语义结构图的链路预测算法和语义结构和时序特征相结合的链路预测算法,讨论了随机游走概率计算策略、参数优化策略、基于时序特征的相似性度量策略及主题关注度预测策略。另外,从语义结构图的特征选择和跳转概率的计算两个角度对链路预测算法进行了改进,进一步提高了链路预测算法的预测准确性。(4)通过实验验证了本文所采用的关键技术的可行性和有效性。同其他链路预测方法相比,本文提出的SLP模型的链路预测精度在整体上优于其他方法。另外,同SLP模型相比,本文提出的STLP模型及改进策略能够显著提高链路预测的精度。