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±ϵ)-approximation of the score of any given node with probability (1−δ), using at most On2/3ln(n)1/3ln(1/δ)2/3ϵ−2/3= Õ(n2/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 OE4/5d−3/5ln(n)1/5ln(1/δ)3/5ϵ−6/5= Õ(E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree.
Brief announcement: On approximating pageRank locally with sublinear query complexity / Bressan, Marco; Peserico, Enoch; Pretto, Luca. - (2018), pp. 87-89. (Intervento presentato al convegno 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 tenutosi a Vienna; Austria) [10.1145/3210377.3210664].
Brief announcement: On approximating pageRank locally with sublinear query complexity
Marco Bressan;
2018
Abstract
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±ϵ)-approximation of the score of any given node with probability (1−δ), using at most On2/3ln(n)1/3ln(1/δ)2/3ϵ−2/3= Õ(n2/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 OE4/5d−3/5ln(n)1/5ln(1/δ)3/5ϵ−6/5= Õ(E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
