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. [1], 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 / M. Bressan, E. Peserico, L. Pretto - In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)[s.l] : IEEE, 2018. - ISBN 978-1-5386-4230-6. - pp. 709-718 (( Intervento presentato al 59. convegno Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 tenutosi a Paris nel 2018 [10.1109/FOCS.2018.00073].

Sublinear algorithms for local graph centrality estimation

M. Bressan
Primo
;
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. [1], 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.
Graph centrality; Heat kernel; Local algorithms; PageRank; Query and computational complexity; Random walks; Sublinear algorithms
Settore INF/01 - Informatica
IEEE Computer Society Technical Committee on Mathematical Foundations of Computing
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Bressan&2018-FOCS.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 241.41 kB
Formato Adobe PDF
241.41 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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/2434/922313
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact