Metraipolis › archive › dc_774872caff00
Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions — arXiv:2611.06782
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06782
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:20:55.058Z
- SHA-256 of the archived text
ccbee1c58b49882ef17cf0ba8a6b3ec96b280b2f78ef256b18282bc130bd39f2- Stable URL of this page
https://metraipolis.com/documento/dc_774872caff00
How to cite
Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions — arXiv:2611.06782 — arXiv (en), https://arxiv.org/abs/2611.06782 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_774872caff00 (Metraipolis archive dc_774872caff00, sha256 ccbee1c58b49882ef17cf0ba8a6b3ec96b280b2f78ef256b18282bc130bd39f2)
BibTeX
@misc{dc774872caff00,
title = {Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions — arXiv:2611.06782},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06782},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_774872caff00; sha256 ccbee1c58b49882ef17cf0ba8a6b3ec96b280b2f78ef256b18282bc130bd39f2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06782. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $T$ match a desired vector $\boldsymbol{t}$. In this paper, we study this problem under an edge-addition budget $B$, where exactly $B$ edges may be added to the graph. We show that deciding whether a multiset of exactly $B$ added edges can make the target nodes attain their desired absolute PageRank scores is NP-complete. After this, we define the $\ell_1$ \textsc{Target PageRank} problem in which we seek to minimize the $\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=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.
Tema degli esploratori: governance digitale e beni comuni (elenco arXiv cs.SI, nuovi lavori del giorno).
Categorie arXiv: Social and Information Networks (cs.SI).
Pagina del lavoro: https://arxiv.org/abs/2611.06782 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:03.967Z dalla pagina https://arxiv.org/list/cs.SI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).