A Dynamical System for PageRank with Time-Dependent Teleportation

DOI10.1080/15427951.2013.814092MaRDI QIDQ4985354zbMATH OpenOpenAlexFDO

Authors David F. Gleich, Ryan Anthony Rossi

Publication date 23 April 2021

Published in Internet Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.4266

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Internet topics (68M11)

Abstract: We propose a dynamical system that captures changes to the network centrality of nodes as external interest in those nodes vary. We derive this system by adding time-dependent teleportation to the PageRank score. The result is not a single set of importance scores, but rather a time-dependent set. These can be converted into ranked lists in a variety of ways, for instance, by taking the largest change in the importance score. For an interesting class of the dynamic teleportation functions, we derive closed form solutions for the dynamic PageRank vector. The magnitude of the deviation from a static PageRank vector is given by a PageRank problem with complex-valued teleportation parameters. Moreover, these dynamical systems are easy to evaluate. We demonstrate the utility of dynamic teleportation on both the article graph of Wikipedia, where the external interest information is given by the number of hourly visitors to each page, and the Twitter social network, where external interest is the number of tweets per month. For these problems, we show that using information from the dynamical system helps improve a prediction task and identify trends in the data.

Recommendations

• Dynamic PageRank using evolving teleportation
• PageRank centrality with non-local random walk-based teleportation
• Applications of Page Ranking in P Systems
• Generalized PageRank on directed configuration networks
• PageRank for networks, graphs, and Markov chains
• PageRank in Undirected Random Graphs
• Distributed Randomized Algorithms for the PageRank Computation
• PageRank in Scale-Free Random Graphs
• A continuum limit for the PageRank algorithm
• Ranking paths in stochastic time-dependent networks

Cites work

• A General Setting for the Parametric Google Matrix
• Dynamic PageRank using evolving teleportation
• Dynamical systems and non-Hermitian iterative eigensolvers
• Google's PageRank and beyond. The science of search engine rankings
• scientific article; zbMATH DE number 45862 (Why is no real title available?)
• Investigating Causal Relations by Econometric Models and Cross-spectral Methods
• Link Evolution: Analysis and Algorithms
• Local partitioning for directed graphs using pagerank
• Ordinal Ranking for Google's PageRank
• Paradoxical Effects in PageRank Incremental Computations
• Random alpha PageRank
• Random walk with restart: fast solutions and applications
• The MATLAB ODE Suite
• Time series analysis. Forecasting and control
• Traps and Pitfalls of Topic-Biased PageRank

Cited in

(5)

• TWPR model based on PageRank algorithm for measuring influence in network
• PageRank beyond the web
• Dynamic PageRank using evolving teleportation
• Random walk centrality for temporal networks
• Time-dependent personalized PageRank for temporal networks: discrete and continuous scales

Describes a project that uses

Uses Software

• ode45
• ode113
• Matlab
• ode23
• MATLAB ODE suite
• Ode15s
• ode23s

This page was built for publication: A Dynamical System for PageRank with Time-Dependent Teleportation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985354)