Temporal PageRank

Polina Rozenshtein*, Aristides Gionis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

38 Citations (Scopus)
566 Downloads (Pure)

Abstract

PageRank is one of the most popular measures for ranking the nodes of a network according to their importance. However, PageRank is defined as a steady state of a random walk, which implies that the underlying network needs to be fixed and static. Thus, to extend PageRank to networks with a temporal dimension, the available temporal information has to be judiciously incorporated into the model. Although numerous recent works study the problem of computing PageRank on dynamic graphs, most of them consider the case of updating static PageRank under node/edge insertions/deletions. In other words, PageRank is always defined as the static PageRank of the current instance of the graph. In this paper we introduce temporal PageRank, a generalization of PageRank for temporal networks, where activity is represented as a sequence of time-stamped edges. Our model uses the random-walk interpretation of static PageRank, generalized by the concept of temporal random walk. By highlighting the actual information flow in the network, temporal PageRank captures more accurately the network dynamics. A main feature of temporal PageRank is that it adapts to concept drifts: the importance of nodes may change during the lifetime of the network, according to changes in the distribution of edges. On the other hand, if the distribution of edges remains constant, temporal PageRank is equivalent to static PageRank. We present temporal PageRank along with an efficient algorithm, suitable for online streaming scenarios. We conduct experiments on various real and semi-real datasets, and provide empirical evidence that temporal PageRank is a flexible measure that adjusts to changes in the network dynamics. The data and software related to this paper are available at https://github.com/polinapolina/temporal-pagerank.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings
PublisherSpringer
Pages674-689
Number of pages16
ISBN (Print)9783319462264
DOIs
Publication statusPublished - 2016
MoE publication typeA4 Conference publication
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases - Riva del Garda, Italy
Duration: 19 Sept 201623 Sept 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9852 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Abbreviated titleECML PKDD
Country/TerritoryItaly
CityRiva del Garda
Period19/09/201623/09/2016

Keywords

  • Dynamic graphs
  • Graph mining
  • Interaction networks
  • PageRank
  • Social-network analysis
  • Time-evolving networks

Fingerprint

Dive into the research topics of 'Temporal PageRank'. Together they form a unique fingerprint.

Cite this