Department of Physics, Biology and Computer Science, Center for Complex Network Research, Northeastern University, Boston, Massachusetts 02115, USA.
Nat Commun. 2011 Jul 19;2:394. doi: 10.1038/ncomms1396.
Pagerank, a network-based diffusion algorithm, has emerged as the leading method to rank web content, ecological species and even scientists. Despite its wide use, it remains unknown how the structure of the network on which it operates affects its performance. Here we show that for random networks the ranking provided by pagerank is sensitive to perturbations in the network topology, making it unreliable for incomplete or noisy systems. In contrast, in scale-free networks we predict analytically the emergence of super-stable nodes whose ranking is exceptionally stable to perturbations. We calculate the dependence of the number of super-stable nodes on network characteristics and demonstrate their presence in real networks, in agreement with the analytical predictions. These results not only deepen our understanding of the interplay between network topology and dynamical processes but also have implications in all areas where ranking has a role, from science to marketing.
网页排名算法（Pagerank）作为一种基于网络的扩散算法，已成为对网络内容、生态物种，甚至是科学家进行排名的主要方法。尽管该算法应用广泛，但人们仍不清楚其运行所依赖的网络结构如何影响其性能。在这里，我们表明对于随机网络，Pagerank 提供的排名对网络拓扑结构的干扰非常敏感，因此对于不完整或嘈杂的系统来说，它是不可靠的。相比之下，我们在无标度网络中分析预测了超级稳定节点的出现，这些节点的排名对干扰具有异常的稳定性。我们计算了超级稳定节点的数量对网络特征的依赖性，并在真实网络中证明了它们的存在，与分析预测一致。这些结果不仅加深了我们对网络拓扑和动态过程之间相互作用的理解，而且在排名发挥作用的所有领域都具有重要意义，从科学到市场营销。
