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, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of n nodes and m arcs, with probability (1 -delta) computes a multiplicative (1 +/-epsilon)-approximation of its score by examining only O(min(n(1/2)Delta(1/2),n(1/2)m(1/4))) nodes/arcs, where Delta is the maximum outdegree of the graph and poly(epsilon (-1)) and polylog(delta(-1)) factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of Omega (min(n(1/2)Delta(1/2), n(1/3)m(1/3))) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph -access model, our technique yields a O(min(n(1/2)Delta(1/2), n(2/3)))-queries algorithm; we show that this algorithm is optimal up to a logarithmic factor-in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case 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: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 52:4(2023), pp. 968-1008. [10.1137/19m1266976]

Sublinear Algorithms for Local Graph-Centrality Estimation

M. Bressan
Primo
;
2023

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, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of n nodes and m arcs, with probability (1 -delta) computes a multiplicative (1 +/-epsilon)-approximation of its score by examining only O(min(n(1/2)Delta(1/2),n(1/2)m(1/4))) nodes/arcs, where Delta is the maximum outdegree of the graph and poly(epsilon (-1)) and polylog(delta(-1)) factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of Omega (min(n(1/2)Delta(1/2), n(1/3)m(1/3))) for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph -access model, our technique yields a O(min(n(1/2)Delta(1/2), n(2/3)))-queries algorithm; we show that this algorithm is optimal up to a logarithmic factor-in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.
graph centrality; sublinear algorithms; local algorithms; query complexity; computational complexity; random walks; PageRank; Heat Kernel;
Settore INF/01 - Informatica
   European Learning and Intelligent Systems Excellence (ELISE)
   ELISE
   EUROPEAN COMMISSION
   H2020
   951847

   Data Mining Algorithms in Practice
   DMAP
   European Commission
   Horizon 2020 Framework Programme
   680153
2023
ago-2023
Article (author)
File in questo prodotto:
File Dimensione Formato  
19m1266976.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.29 MB
Formato Adobe PDF
1.29 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
1404.1864.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 392.53 kB
Formato Adobe PDF
392.53 kB Adobe PDF Visualizza/Apri
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/1033670
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact