跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文,不再错过。

覆盖计算机全学科,以 AI 为快捷入口。关注方向、作者和关键词,把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+1已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描:2026-11-09 05:07 · 全站最近入库:2026-11-08 06:02各信源进度 →

统计口径与数据新鲜度

统计 2026-11-08 05:32 — 2026-11-09 05:32(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-09 05:07最近发现新增版本:2026-11-08 06:02库内论文最新更新时间:2026-11-06 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

17,100 已收录论文14,661 AI 相关4,057 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-09 05:05(北京时间)
版本更新 · v2arXiv:2611.06782

目标PageRank:通过预算受限的加边匹配指定PageRank分数

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

Parth Gupta, Abhinav Jain, Avishek Mukhopadhyay, Amitabha Bagchi, Sayan Ranu, Abhijnan Chakraborty

AI 速读 基于摘要

研究在恰好添加B条边的预算下,如何通过加边使目标节点的PageRank逼近给定目标向量,并给出计算复杂性结果与启发式算法。

cs.SI

查看原文摘要

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.