School of Informatics, Computing and Engineering, Indiana University, Bloomington, IN, USA.
Department of Computing and Mathematics, University of São Paulo, Ribeirão Preto, SP, Brazil.
Sci Rep. 2019 Jul 25;9(1):10833. doi: 10.1038/s41598-019-47271-9.
Link prediction (LP) permits to infer missing or future connections in a network. The network organization defines how information spreads through the nodes. In turn, the spreading may induce changes in the connections and speed up the network evolution. Although many LP methods have been reported in the literature, as well some methodologies to evaluate them as a classification task or ranking problem, none have systematically investigated the effects on spreading and the structural network evolution. Here, we systematic analyze LP algorithms in a framework concerning: (1) different diffusion process - Epidemics, Information, and Rumor models; (2) which LP method most improve the spreading on the network by the addition of new links; (3) the structural properties of the LP-evolved networks. From extensive numerical simulations with representative existing LP methods on different datasets, we show that spreading improve in evolved scale-free networks with lower shortest-path and structural holes. We also find that properties like triangles, modularity, assortativity, or coreness may not increase the propagation. This work contributes as an overview of LP methods and network evolution and can be used as a practical guide of LP methods selection and evaluation in terms of computational cost, spreading capacity and network structure.
链接预测（Link Prediction，LP）允许推断网络中缺失或未来的连接。网络组织定义了信息如何在节点之间传播。反过来，这种传播可能会导致连接的变化，并加速网络的演化。尽管文献中已经报道了许多 LP 方法，以及一些将其评估为分类任务或排序问题的方法，但没有一种方法系统地研究了对传播和结构网络演化的影响。在这里，我们在一个框架中系统地分析 LP 算法，该框架涉及：（1）不同的扩散过程——流行病、信息和谣言模型；（2）哪种 LP 方法通过添加新的链接最能改善网络上的传播；（3）LP 演化网络的结构特性。通过在不同数据集上使用具有代表性的现有 LP 方法进行广泛的数值模拟，我们表明，在具有较低最短路径和结构空洞的演化无标度网络中，传播得到了改善。我们还发现，像三角形、模块性、 assortativity 或核心等属性可能不会增加传播。这项工作是对 LP 方法和网络演化的概述，可以作为 LP 方法选择和评估的实用指南，考虑到计算成本、传播能力和网络结构。
