链路预测作为数据挖掘的一个领域,在复杂网络中有着广泛的研究。随着在线社交网络的蓬勃发展,潜在好友的推荐成为社交网络服务中的基础功能。链路预测是基于当前的网络结构和节点的属性去预测现在尚未结交的用户“倾向于成为朋友”,并将此结果作为“朋友推荐”发送给用户。因此,社交网络上的链路预测具有较好的实际应用价值,而且相比传统的复杂网络,社交网络有更多的信息可以利用,比如社团特征、文本信息等。一个好的链路预测方法往往需要一些好的网络特征或生长机制来支持,如网络的社团结构、偏好连接和弱连接效应等都可以很好的指导链路预测。在本文中,首先,我们根据社交网络的特点提出了一种基于关系强度的机制,并基于此机制改进了传统的链路预测算法。其次,考虑到用户的已有链路关系和兴趣偏好都是影响链路的重要因素,并通过结合社区发现算法做了进一步改进,该方法同时利用了用户的关系信息和兴趣偏好特征。最后,如何利用好这些网络信息与机制是影响链路预测准确率的关键。为此,本文设计了一个结合链路预测与标签传播社区划分算法的好友推荐系统。具体的研究内容如下:(1)针对传统链路预测只利用节点和网络的结构信息,忽略了社交网络上关系形成的原因,提出了一种改进的链路预测算法(Combining Node degree and Relationship Strength,简称CNRS)。首先发现了社交网络相对于复杂网络的独有特点,社交网络链路的产生基于各种各样的关系,本文通过共同邻居紧密度来间接度量关系强度这一概念;其次根据关系强度改进了局部链路指标,并详细说明了计算方法。实验证明,考虑关系强度越高的节点对之间未来产生链接的可能性确实更大,且社交属于越明显、平均度越高的网络,性能提升越显著。(2)偏好连接已经被证明是可以提高链路预测准确率的一种思想,在此基础上本文提出了结合标签传播和链路预测的算法。首先,收集用户的属性特征和文本信息发掘其潜在偏好并提取标签,以此构建用户特征向量模型计算用户间相似度;然后基于改进的多标签传播社区发现算法(Multi-Label Propagation Algorithm,简称MLPA)挖掘出相似社区;最后,在社区基础上利用链路预测找出关系强度最密切的节点对,选择Top-K潜在好友列表推荐给用户。该方法综合考虑了网络结构和节点属性信息,不仅进一步提高了准确率,也减小了链路预测计算规模,并在真实数据集上进行了评估。实验结果表明我们的算法要优于现有的局部指标方法。(3)应用结合算法做朋友推荐,设计实现了一个集成CNRS算法和MPLA算法的社交网络推荐系统。针对实际应用中的问题,本文充分考虑了数据采集与预处理,然后集成推荐模块。考虑到大数据技术已经应用于海量的社交数据处理,本文的推荐算法实现采用了分布式计算,因此具有一定的实际应用价值。