betaFeedback

Reading v1View latest version

WorksComputer Science

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

Abstract

PageRank is widely used to quantify the importance of nodes in directed networks. In applications such as recommendation systems, it is increasingly important that the PageRank distribution provides a fair representation of node exposure. This motivates the problem of making minimal changes to a graph so that the PageRank values of a given set of target nodes TT match a desired vector t\boldsymbol{t}. In this paper, we study this problem under an edge-addition budget BB, where exactly BB edges may be added to the graph. We show that deciding whether a multiset of exactly BB added edges can make the target nodes attain their desired absolute PageRank scores is NP-complete. After this, we define the ℓ1\ell_1 Target PageRank problem in which we seek to minimize the ℓ1\ell_1 distance between the target vector and resultant vector. We show that this optimization problem admits no polynomial-time multiplicative constant-factor approximation unless P=NPP=NP. Motivated by these hardness results, we propose two greedy heuristics for approaching the target PageRank vector. We additionally propose a Random Walk Hungarian (RWH) heuristic that addresses the addition of edges between dissimilar nodes by incorporating a penalty for such edges. Finally, we evaluate the proposed heuristics on several real-world and synthetic datasets and compare their performance in terms of PageRank accuracy, computational efficiency, and the relevance of the added edges.

Paper details

vlnc:W_5yjffm6t
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…