We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only Õ(min(m^2/3 Δ^1/3 d^-2/3 , m 4/5 d -3/5 )) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε^ -1 ) and polylog(δ ^-1 ) factors). A similar bound holds for computational cost. We also prove a lower bound of Ω(min (m^1/2 Δ^1/2 d^-1/2 , m^2/3 d^-1/3 )) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n^2/3 )-queries algorithm for an n-node graph in the access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.

Sublinear algorithms for local graph centrality estimation

Peserico, Enoch;Pretto, Luca
2018

Abstract

We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only Õ(min(m^2/3 Δ^1/3 d^-2/3 , m 4/5 d -3/5 )) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε^ -1 ) and polylog(δ ^-1 ) factors). A similar bound holds for computational cost. We also prove a lower bound of Ω(min (m^1/2 Δ^1/2 d^-1/2 , m^2/3 d^-1/3 )) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n^2/3 )-queries algorithm for an n-node graph in the access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.
2018
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
9781538642306
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3299960
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact