Brief Announcement: On Approximating PageRank Locally with Sublinear Query Complexity
Brief Announcement: On Approximating PageRank Locally with Sublinear Query Complexity
复制标题
简短公告：关于使用次线性查询复杂度在本地近似 PageRank
DOI：
10.1145/3210377.3210664
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Luca Pretto
中科院分区：
文献类型：
--
作者：
M. Bressan;E. Peserico;Luca Pretto
一个人可以在图中计算单个任意节点的Pagerank分数，探索该图的消失分数吗？ ，返回一个乘以$（1 \pmε）$ - 任何给定节点的分数均具有概率$（1-δ）$，最多使用$ o \ big（n^2/3 ol（n^2/3）（n）^1/ 3（1/δ）^2/3ε^-2/3 \ big）= \ tildeo（n^2/3）$ QUERIES $ QUERIES，它们均匀地返回一个随机选择的节点，或给定的邻居列表节点。我们表明，可以通过获取最多$ o \ big（e^4/5 d^-3/5 d^-3/5）（n）^1/5 oln（1/δ）^3/来附加相同的保证。 5ε^-6/5 \ big）= \ tildeo（e^4/5）$弧，其中e是图中的弧的总数，d是其平均程度。
Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative $(1\pmε)$-approximation of the score of any given node with probability $(1-δ)$, using at most $O\big(n^2/3 łn(n)^1/3 łn(1/δ)^2/3 ε^-2/3 \big) = \tildeO (n^2/3 )$ queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most $O\big( E^4/5 d^-3/5 łn(n)^1/5 łn(1/δ)^3/5 ε^-6/5 \big) = \tildeO (E^4/5 )$ arcs, where E is the total number of arcs in the graph and d is its average degree.