论文部分内容阅读
近十年,复杂网络研究在许多科学领域内掀起了高潮。包括生物、物理、计算机等领域的科学家在内,相当一部分人都立足于揭示复杂网络进化的内在驱动因素。作为复杂网络研究中的一个重要分支,链路预测问题既可以在理论意义上帮助我们认识复杂网络的进化机制,又可以在实际应用上帮助我们揭示各学科内的许多重要问题。链路预测旨在推断复杂网络中节点之间存在连边的可能性,其中包括预测已经存在但尚未被发现的连边和将来出现的连边。近几年,基于结构相似性的链路预测算法受到了广泛地关注,研究者们陆续提出了各种基于局部网络结构和基于全局网络结构的方法。本文主要研究的是复杂网络中基于标签传播的链路预测算法,并将研究重点放在了如何提高链路预测精度的问题上。首先,本文系统地概述了复杂网络链路预测相关背景知识和基本内容,根据所依赖的网络结构差异,分类总结了基于结构相似性的链路预测指标。其次,提出了基于标签传播的链路预测算法和基于最大值的计算分数值方法,模拟了社交网络中人与人之间信息的动态交互过程。再次,通过实验,详细比较了基于标签传播的链路预测算法与几种经典的基于结构相似性指标的预测性能差异,证明了在现实网络数据上,基于标签传播的链路预测算法表现的更为优越。最后,提出了将链路预测算法应用于社区发现中的思想,使用基于标签传播的链路预测算法来优化Louvain社区发现算法。结果表明,经过改进后的Louvain算法能够产生比原始基本算法更好的效果,从而发现复杂网络中更加精确的社区结构。