Ranking nodes in growing networks: When PageRank fails

Abstract

PageRank is arguably the most popular ranking algorithm which is being applied in real systems ranging from information to biological and infrastructure networks. Despite its outstanding popularity and broad use in different areas of science, the relation between the algorithm's efficacy and properties of the network on which it acts has not yet been fully understood. We study here PageRank's performance on a network model supported by real data, and show that realistic temporal effects make PageRank fail in individuating the most valuable nodes for a broad range of model parameters. Results on real data are in qualitative agreement with our model-based findings. This failure of PageRank reveals that the static approach to information filtering is inappropriate for a broad class of growing systems, and suggest that time-dependent algorithms that are based on the temporal linking patterns of these systems are needed to better rank the nodes.

Article + Supplementary Information

References in corpus (14)

• Quantifying Long-Term Scientific Impact
• Leaders in Social Networks, the Delicious Case
• Activity driven modeling of time varying networks
• Finding Scientific Gems with Google
• Centrality in Interconnected Multilayer Networks
• Ranking Scientific Publications Using a Simple Model of Network Traffic
• Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation Networks
• Experience versus Talent Shapes the Structure of the Web
• Ranking species in mutualistic networks
• PageRank for ranking authors in co-citation networks
• Statistical validation of high-dimensional models of growing networks
• Are Friends Overrated? A Study for the Social News Aggregator Digg.com
• Identification and modeling of discoverers in online social systems
• The effect of the initial network configuration on preferential attachment

Cited by in corpus (14)

• Ranking in evolving complex networks
• Identification of milestone papers through time-balanced network centrality
• Early identification of important patents through network centrality
• Fast influencers in complex networks
• Random walks on activity-driven networks with attractiveness
• Quantifying and suppressing ranking bias in a large citation network
• Inequality and Inequity in Network-based Ranking and Recommendation Algorithms
• Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data
• Randomizing growing networks with a time-respecting null model
• The long-term impact of ranking algorithms in growing networks
• Network-based ranking in social systems: three challenges
• Decay of Relevance in Exponentially Growing Networks
• Who is the best coach of all time? A network-based assessment of the career performance of professional sports coaches
• Limits of PageRank-based ranking methods in sports data