计算机、互联网、物联网正逐渐走入人们的生活,人与机器之间的交互产生了复杂的关系,人、机器及其关系构成了复杂系统。复杂系统可以用数学语言抽象为复杂网络,用数学工具表示和研究复杂网络,是认识和理解复杂系统的有效手段。利用已观察到的网络结构信息,链路预测可以预测网络中尚未连接的节点未来发生连接的可能性,还可以识别网络中虚假的连边。链路预测是复杂网络研究的分支之一,理论上,研究链路预测能模拟复杂网络的演进过程、理解复杂网络的演化规律和机制、估计复杂网络建模的规模;实际应用中,利用链路预测可以在社交网络中进行朋友关系的预测、在交通网络中规划合理高效的路线、在电子商务网络中进行商品的精准推荐,在生物网络中预测蛋白质之间的交互关系等等。因而,复杂网络下的链路预测研究具有重要的理论意义和应用价值。本论文研究复杂网络下基于拓扑相似性的链路预测,基于节点相似性的链路预测认为,两个节点越相似,则两节点越可能发生连接。研究发现,网络中节点的影响力及节点影响力的有效传播对节点间的相似性具有一定的作用。本论文针对目前链路预测研究中存在的问题,从网络的局部和半局部结构信息入手,研究公共邻居节点与目标端点对之间的有效路径、节点的度、端点对之间的路径等结构属性作为影响力对节点相似性的作用;讨论节点的度、节点的H-指数及节点的核数等属性作为影响力资源对链路预测性能的影响,构建能准确描述端点相似性的链路预测模型。论文的主要工作和创新点如下:1)考虑网络的局部结构信息,从端点对之间的公共邻居出发,提出基于公共邻居连接力量(Tie Connection Strength:TCS)的链路预测模型。传统的链路预测研究以目标端点对为对象,认为目标端点之间的大度公共邻居不利于端点影响力的传播,忽略了公共邻居与目标端点对之间的路径对于影响力传播的积极作用。本论文从公共邻居的角度出发,将公共邻居上对端点相似性有贡献的路径定义为有效路径,在有效路径的基础上研究公共邻居节点的影响力。同时将公共邻居上的有效路径数量定义为公共邻居的连接力量,提出基于公共邻居连接力量的链路预测算法(TCS)。TCS算法考虑了网络的局部结构特性,将传播端点影响力的有效路径加入到节点相似性模型中。在12个网络中与8种传统的链路预测算法进行性能比较,实验结果显示,综合常用的精确度(Precision)和召回率(Recall)两种准确性指标,在不增加算法复杂度的基础上,TCS算法能有效提高链路预测的准确性,具有可行性和适用性。2)考虑网络的半局部结构信息,发现网络中端点间的相互影响与端点间的路径有关,提出基于显著影响力(Significant Influence:SI)的链路预测算法。传统的链路预测算法仅仅考虑端点的度,将端点度建模成端点影响力,认为具有大度的目标端点更倾向于连接。研究发现,网络中的端点通过路径建立连接,从而进行影响力的传输。目标端点间不同长度的路径起到不同的作用:两个端点经过短路径,尤其是两跳路径,产生强关系,带来强影响力;相反的,通过三跳及三跳以上的长路径产生弱关系,带来弱影响力。端点之间的强关系多而弱关系少,构成显著影响力,能有效传递端点的影响力资源。在此基础上提出基于显著影响力的SI算法,SI算法利用网络的半局部特征信息,有效区别端点间强弱关系和影响力的不同。将SI算法与5种传统的链路预测算法在12个真实网络中进行性能对比分析,实验结果显示,综合AUC(Area Under the Receiver Operating Characteristic Curve)和Precision两种性能评价指标,SI算法具有良好的预测性能,相比于传统的算法,明显地提高了链路预测的准确性。3)在SI算法的基础之上,综合考虑传播影响力的两个重要因素,端点的度和端点间的路径,区别端点间不同长度的路径对影响力传播的不同作用,提出惩罚冗余影响力(Punishing the Redundant Influence:PRI)的链路预测算法。传统的基于半局部信息的链路预测研究将端点的度构建为影响力资源,并没有考虑影响力的传播需要经过路径,忽略了端点影响力资源的有效传输也会影响端点相似性的问题。研究发现,仅仅靠端点的度值并不能保证影响力能有效传输到目标端点,影响力的有效传输还跟传输路径的长短有关。本论文将与公共邻居连接的端点度、端点之间的短路径作为端点影响力传播的高效因素;将与非公共邻居相连接的度、端点之间的长路径,作为端点影响力传播的低效因素;与目标端点对没有连接的度和路径,由于没有参与影响力的传播,被称为冗余因素。综合考虑影响端点间影响力传播的不同因素,提出惩罚冗余影响力(PRI)的链路预测算法。在12个真实网络中与5种传统算法进行对比分析,实验结果显示,结合AUC和Precision两种评价指标,PRI算法通过惩罚传递影响力的冗余影响因素,强调对相似性有贡献的高效因素,能有效提高端点的相似性和链路预测的准确性。4)以网络中最小的元素节点为对象,研究节点的基本属性对链路预测的影响。研究节点的度、节点的H-指数、节点的核数等基本属性对节点相似性的影响,分析节点的三种基本属性在链路预测中的作用。基于传统有迭代的随机游走(Super Random Walker:SRW)链路预测模型,提出基于节点H-指数(HSRW)、节点的核数(CSRW)的链路预测算法。研究和实验结果显示,HSRW和CSRW在没有增加复杂度的条件下有效地提高了链路预测的准确性。同时,HSRW算法中的H-指数作为节点影响力资源是一种很好的权衡。在具有极大连通子图的网络中,若两个节点具有较大的H-指数和较多的连接路径,则比较适合采用HSRW算法。若两个节点的H-指数较小,核数较大并且具有较大的中心性,则采用CSRW算法比较适合。同时,与节点的度一样,节点的H-指数和节点的核数同样能够作为节点的影响力资源,在不同的网络中采用不同的节点属性作为节点影响力,构建链路预测模型,能有效提高链路预测的准确性。