论文部分内容阅读
随着信息技术的快速进步,各种复杂系统大量涌现,以复杂网络理论为基础的网络科学研究也随之得到加速发展。作为网络科学领域的重要问题之一,链路预测主要研究网络中尚未形成连边的节点之间产生链接的可能性,该问题的解决具有重要的理论和现实意义。一方面,链路预测的研究有助于揭示网络的内部结构特征,促进理解复杂网络的演化机制;另一方面,链路预测技术已被广泛应用于各类真实系统,间接推动了经济的发展和社会治理水平的提高。 本文以复杂网络为对象,试图从不同视角探索网络拓扑结构对链路预测性能的影响。首先,分别从路径的权重和路径间的相互作用关系两个角度,研究了无向无权网络中链路预测的路径异质性问题;然后,基于无向无权网络中链接度拓扑结构与预测性能之间的内在关系,进一步分析了加权网络中链接的拓扑权重和自然权重对预测性能的影响;最后,以无向无权网络中的经典预测方法为基础,综合分析了多层网络的层间结构对预测性能的影响。此研究从简单类型的无向无权网络到复杂类型的加权、多层网络,分别提出了新的链路预测方法,并对其有效性进行了验证,具体内容包括以下四个方面: (1)针对无向无权网络,利用节点间不同路径的连通强度差异性,提出了新的基于半局部路径的结构相似性预测方法。传统基于路径的预测方法,通常仅关注路径的数量和长度贡献,忽略了相同长度路径的异质贡献问题。本文从路径的中间链接和中间节点角度出发,分别考虑已存在连边的链接度和中间节点周围邻居的连通性影响,得到节点间路径的加权衡量方法,并提出基于局部加权路径的LWP(Local Weighted Paths)预测方法。实验结果表明,相比其他7个代表性方法,LWP方法具有良好的预测性能,且验证了链接度拓扑结构与预测性能成反比关系。 (2)针对无向无权网络的路径异质性问题,利用不同路径节点间相互作用的强弱关系,提出了基于路径相互作用关系的结构相似性预测方法。当前链路预测方法仅孤立地看待各条路径贡献,忽略了路径间节点的相互作用关系对预测性能的影响。在链路预测研究中,通常短路径被认为较长路径具有更大的贡献。因此,利用网络资源分配机制来模拟不同路径之间的相互作用关系,如果长路径的中间节点能够从短路径节点集合中获取的资源越多,代表该路径的贡献越大,并提出了基于短路径资源接收过程的RSP(Resource receiving process from Short Paths)预测方法。实验结果表明,相比其他9个代表性方法,RSP方法具有良好的预测性能。 (3)在加权网络中,考虑到链接的拓扑结构某种程度也能够反映链接的强弱关系,提出了基于链接耦合权重的含权预测方法。传统加权网络中的含权预测方法,通常突出链接的自然权重对预测性能的贡献,忽略了链接的拓扑结构对预测性能的影响。本文从链接的自然权重出发,将链接度函数看作链接的拓扑权重,定义了融合自然权重和拓扑权重的链接耦合权重概念,并提出基于链接耦合权重的含权预测方法。实验结果表明,相比仅依赖链接自然权重或拓扑权重的方法,基于链接耦合权重的含权预测方法具有更优的性能。 (4)从多层网络角度,利用层间结构的相互依赖性,提出了基于多层网络层间相关性的链路预测方法。相较单层网络而言,多层网络表征了节点间更为丰富的结构关系。但目前链路预测研究大多集中在单层网络,很少关注层间结构对链路预测性能的影响。借助层间相关性的不同衡量方法,本文分析了多层网络的层间结构信息对预测层预测性能的贡献。结合层间全局重叠率和皮尔逊相关性,提出融合层内和层间结构信息的NSILR(NodeSimilarity Index based on Layer Relevance)预测方法。实验结果表明,相比单层网络,层间结构信息对预测性能提升的贡献更为显著,且有利于解决链路预测的冷启动问题。由于不同的层间相关性衡量方法对预测性能具有影响,我们提出了层相关熵的概念,来预判层间结构信息对预测性能的贡献。