2021/04/12 by José Devezas, Devezas, José, Sérgio Nunes +1
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Expert finding and Q&A systems #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2104.05369
openalex publication_date 2021/04/12 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Connections among entities are everywhere. From social media interactions to web page hyperlinks, networks are frequently used to represent such complex systems. Node ranking is a fundamental task that provides the strategy to identify central entities according to multiple criteria. Popular node ranking metrics include degree, closeness or betweenness centralities, as well as HITS authority or PageRank. In this work, we propose a novel node ranking metric, where we combine PageRank and the idea of node fatigue, in order to model a random explorer who wants to optimize coverage - it gets fatigued and avoids previously visited nodes. We formalize and exemplify the computation of Fatigued PageRank, evaluating it as a node ranking metric, as well as query-independent evidence in ad hoc document retrieval. Based on the Simple English Wikipedia link graph with clickstream transitions from the English Wikipedia, we find that Fatigued PageRank is able to surpass both indegree and HITS authority, but only for the top ranking nodes. On the other hand, based on the TREC Washington Post Corpus, we were unable to outperform the BM25 baseline, obtaining similar performance for all graph-based metrics, except for indegree, which lowered GMAP and MAP, but increased NDCG@10 and P@10.