Lü Linyuan, Jin Ci-Hang, Zhou Tao
Department of Physics, University of Fribourg, Fribourg, Switzerland.
Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Oct;80(4 Pt 2):046122. doi: 10.1103/PhysRevE.80.046122. Epub 2009 Oct 26.
Predictions of missing links of incomplete networks, such as protein-protein interaction networks or very likely but not yet existent links in evolutionary networks like friendship networks in web society, can be considered as a guideline for further experiments or valuable information for web users. In this paper, we present a local path index to estimate the likelihood of the existence of a link between two nodes. We propose a network model with controllable density and noise strength in generating links, as well as collect data of six real networks. Extensive numerical simulations on both modeled networks and real networks demonstrated the high effectiveness and efficiency of the local path index compared with two well-known and widely used indices: the common neighbors and the Katz index. Indeed, the local path index provides competitively accurate predictions as the Katz index while requires much less CPU time and memory space than the Katz index, which is therefore a strong candidate for potential practical applications in data mining of huge-size networks.
对不完整网络中缺失链接的预测，例如蛋白质-蛋白质相互作用网络，或者像网络社会中的友谊网络这类进化网络中极有可能存在但尚未出现的链接，可以被视为进一步实验的指导方针，或者为网络用户提供有价值的信息。在本文中，我们提出了一种局部路径指数来估计两个节点之间存在链接的可能性。我们提出了一种在生成链接时具有可控密度和噪声强度的网络模型，并收集了六个真实网络的数据。对建模网络和真实网络进行的大量数值模拟表明，与两个著名且广泛使用的指数：共同邻居指数和卡茨指数相比，局部路径指数具有更高的有效性和效率。实际上，局部路径指数提供了与卡茨指数相当准确的预测，同时比卡茨指数需要更少的CPU时间和内存空间，因此它是在超大规模网络数据挖掘中潜在实际应用的有力候选者。
