Data di Pubblicazione:
2023
Citazione:
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]
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
graph centrality; sublinear algorithms; local algorithms; query complexity; computational complexity; random walks; PageRank; Heat Kernel;
Elenco autori:
M. Bressan, E. Peserico, L. Pretto
Link alla scheda completa:
Link al Full Text: