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 - delta) computes a multiplicative (1 +/- epsilon)-approximation of its score by examining only (O) over tilde (min(m(2/3)Delta(1/3)d(-2/3), m(4/5) d(-3/5))) nodes/arcs, where Delta and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(epsilon(-1)) and polylog(delta(-1)) factors). A similar bound holds for computational cost. We also prove a lower bound of Omega(min(m(1/2)Delta(1/2)d(-1/2), m(2/3)d(-1/3))) for both query complexity and computational complexity. Moreover, our technique yields a (O) over tilde (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 / Bressan, Marco; Peserico, Enoch; Pretto, Luca. - (2018), pp. 709-718. (Intervento presentato al convegno 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) tenutosi a Paris) [10.1109/FOCS.2018.00073].

Sublinear Algorithms for Local Graph Centrality Estimation

Bressan, Marco;
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 - delta) computes a multiplicative (1 +/- epsilon)-approximation of its score by examining only (O) over tilde (min(m(2/3)Delta(1/3)d(-2/3), m(4/5) d(-3/5))) nodes/arcs, where Delta and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(epsilon(-1)) and polylog(delta(-1)) factors). A similar bound holds for computational cost. We also prove a lower bound of Omega(min(m(1/2)Delta(1/2)d(-1/2), m(2/3)d(-1/3))) for both query complexity and computational complexity. Moreover, our technique yields a (O) over tilde (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.
2018
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
graph centrality; sublinear algorithms; local algorithms; query and computational complexity; random walks; PageRank; heat kernel
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Sublinear Algorithms for Local Graph Centrality Estimation / Bressan, Marco; Peserico, Enoch; Pretto, Luca. - (2018), pp. 709-718. (Intervento presentato al convegno 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) tenutosi a Paris) [10.1109/FOCS.2018.00073].
File allegati a questo prodotto
File Dimensione Formato  
Bressan_Sublinear_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 241.41 kB
Formato Adobe PDF
241.41 kB Adobe PDF   Contatta l'autore
Bressan_sublinear_2018 (2).pdf

accesso aperto

Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 392.53 kB
Formato Adobe PDF
392.53 kB Adobe PDF

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/11573/1279738
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact