Temporal PageRank

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorRozenshtein, Polinaen_US
dc.contributor.authorGionis, Aristidesen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorAdj. Prof. Gionis Aris groupen
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.date.accessioned2018-09-06T10:15:55Z
dc.date.available2018-09-06T10:15:55Z
dc.date.issued2016en_US
dc.description| openaire: EC/H2020/654024/EU//SoBigData
dc.description.abstractPageRank 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.en
dc.description.versionPeer revieweden
dc.format.extent16
dc.format.extent674-689
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationRozenshtein, P & Gionis, A 2016, Temporal PageRank . in Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9852 LNAI, Springer, pp. 674-689, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Riva del Garda, Italy, 19/09/2016 . https://doi.org/10.1007/978-3-319-46227-1_42en
dc.identifier.doi10.1007/978-3-319-46227-1_42en_US
dc.identifier.isbn9783319462264
dc.identifier.issn03029743
dc.identifier.issn16113349
dc.identifier.otherPURE UUID: 28b00d4e-3237-434d-8644-6e927fab9526en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/28b00d4e-3237-434d-8644-6e927fab9526en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=84988564512&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/26626013/temporal_pagerank.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/33846
dc.identifier.urnURN:NBN:fi:aalto-201809064957
dc.language.isoenen
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/654024/EU//SoBigDataen_US
dc.relation.ispartofEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databasesen
dc.relation.ispartofseriesMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2016, Proceedingsen
dc.relation.ispartofseriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.relation.ispartofseriesVolume 9852 LNAIen
dc.rightsopenAccessen
dc.subject.keywordDynamic graphsen_US
dc.subject.keywordGraph miningen_US
dc.subject.keywordInteraction networksen_US
dc.subject.keywordPageRanken_US
dc.subject.keywordSocial-network analysisen_US
dc.subject.keywordTime-evolving networksen_US
dc.titleTemporal PageRanken
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionacceptedVersion

Files