Ranking in evolving complex networks

Abstract

Complex networks have emerged as a simple yet powerful framework to represent and analyze a wide range of complex systems. The problem of ranking the nodes and the edges in complex networks is critical for a broad range of real-world problems because it affects how we access online information and products, how success and talent are evaluated in human activities, and how scarce resources are allocated by companies and policymakers, among others. This calls for a deep understanding of how existing ranking algorithms perform, and which are their possible biases that may impair their effectiveness. Well-established ranking algorithms (such as the popular Google's PageRank) are static in nature and, as a consequence, they exhibit important shortcomings when applied to real networks that rapidly evolve in time. The recent advances in the understanding and modeling of evolving networks have enabled the development of a wide and diverse range of ranking algorithms that take the temporal dimension into account. The aim of this review is to survey the existing ranking algorithms, both static and time-aware, and their applications to evolving networks. We emphasize both the impact of network evolution on well-established static algorithms and the benefits from including the temporal dimension for tasks such as prediction of real network traffic, prediction of future links, and identification of highly-significant nodes.

54 pages, 16 figures

References in corpus (46)

• Cooperative Game Theory Approaches for Network Partitioning
• The Building Blocks of Economic Complexity
• The structure and dynamics of multilayer networks
• Community detection in networks: A user guide
• Vital nodes identification in complex networks
• Mitigation of Malicious Attacks on Networks
• Does the h-index have predictive power?
• Leaders in Social Networks, the Delicious Case
• Statistical physics of vaccination
• What's in a crowd? Analysis of face-to-face behavioral networks
• Universality of citation distributions: towards an objective measure of scientific impact
• New Model of Internet Topology Using k-shell Decomposition
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Finding Scientific Gems with Google
• Defining and identifying Sleeping Beauties in science
• Searching for superspreaders of information in real-world social media
• Path lengths, correlations, and centrality in temporal networks
• Diffusion of scientific credits and the ranking of scientists
• Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility
• Avoiding catastrophic failure in correlated networks of networks
• A k-shell decomposition method for weighted networks
• Ranking the spreading influence in complex networks
• Heat Conduction Process on Community Networks as a Recommendation Model
• Ranking Scientific Publications Using a Simple Model of Network Traffic
• Personalized Recommendation via Integrated Diffusion on User-Item-Tag Tripartite Graphs
• Random walks and search in time-varying networks
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Spectral centrality measures in complex networks
• Scale-free network growth by ranking
• Self-organized Natural Roads for Predicting Traffic Flow: A Sensitivity Study
• Effects of time window size and placement on the structure of aggregated networks
• Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation Networks
• Effective Distances for Epidemics Spreading on Complex Networks
• A network-based ranking system for American college football
• Information filtering via Iterative Refinement
• A reverse engineering approach to the suppression of citation biases reveals universal properties of citation distributions
• When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
• Two-dimensional ranking of Wikipedia articles
• Experience versus Talent Shapes the Structure of the Web
• Ranking species in mutualistic networks
• Identification of milestone papers through time-balanced network centrality
• Growing complex network of citations of scientific papers -- measurements and modeling
• A network-based dynamical ranking system for competitive sports
• Quantifying and suppressing ranking bias in a large citation network
• Decoding Information from noisy, redundant, and intentionally-distorted sources
• Data-driven modeling of collaboration networks: A cross-domain analysis

Cited by in corpus (28)

• Random walks and diffusion on networks
• Nestedness in complex networks: Observation, emergence, and implications
• Computational Socioeconomics
• Early identification of important patents through network centrality
• Centrality-based identification of important edges in complex networks
• Persistence in Complex Systems
• Fast influencers in complex networks
• Big Networks: A Survey
• Exploratory analysis of text duplication in peer-review reveals peer-review fraud and paper mills
• Emergence of Hierarchy in Networked Endorsement Dynamics
• Optimal interlayer structure for promoting spreading of SIS model in two-layer networks
• Identifying significant edges via neighborhood information
• Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data
• Recommending investors for new startups by integrating network diffusion and investors' domain preference
• Influencers identification in complex networks through reaction-diffusion dynamics
• A Network Science perspective of Graph Convolutional Networks: A survey
• The long-term impact of ranking algorithms in growing networks
• Forecasting countries' gross domestic product from patent data
• Network-based ranking in social systems: three challenges
• Quantifying the status of economies in international crop trade networks: An correlation structure analysis of various node-ranking metrics
• Accumulative time-based ranking method to reputation evaluation in information networks
• A perturbation-based approach to identifying potentially superfluous network constituents
• Equivalence between the Fitness-Complexity and the Sinkhorn-Knopp algorithms
• Who is the best coach of all time? A network-based assessment of the career performance of professional sports coaches
• Optimal timescale for community detection in growing networks
• Priority Attachment: a Comprehensive Mechanism for Generating Networks
• Identifying Central Nodes in Multiplex Networks by Embracing Layer-Specific Heterogeneity via DomiRank
• Quantum community detection via deterministic elimination