Abstract
The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large smallworld graphs G = (V, E)  i. e., graphs with diameter in O(log V), which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian’s pseudoinverse, L^+. Computing diag(L^+) exactly by pseudoinversion, however, is as expensive as dense matrix multiplication  and the standard tools in practice even require cubic time. Moreover, the pseudoinverse requires quadratic space  hardly feasible for large graphs. Resorting to approximation by, e. g., using the JohnsonLindenstrauss transform, requires the solution of O(log V / ε²) Laplacian linear systems to guarantee a relative error, which is still very expensive for large inputs.
In this paper, we present a novel approximation algorithm that requires the solution of only one Laplacian linear system. The remaining parts are purely combinatorial  mainly sampling uniform spanning trees, which we relate to diag(L^+) via effective resistances. For smallworld networks, our algorithm obtains a ± εapproximation with high probability, in a time that is nearlylinear in E and quadratic in 1 / ε. Another positive aspect of our algorithm is its parallel nature due to independent sampling. We thus provide two parallel implementations of our algorithm: one using OpenMP, one MPI + OpenMP. In our experiments against the state of the art, our algorithm (i) yields more accurate approximation results for diag(L^+), (ii) is much faster and more memoryefficient, and (iii) obtains good parallel speedups, in particular in the distributed setting.
BibTeX  Entry
@InProceedings{angriman_et_al:LIPIcs:2020:12872,
author = {Eugenio Angriman and Maria Predari and Alexander van der Grinten and Henning Meyerhenke},
title = {{Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {6:16:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12872},
URN = {urn:nbn:de:0030drops128723},
doi = {10.4230/LIPIcs.ESA.2020.6},
annote = {Keywords: Laplacian pseudoinverse, electrical centrality measures, uniform spanning tree, effective resistance, parallel sampling}
}
Keywords: 

Laplacian pseudoinverse, electrical centrality measures, uniform spanning tree, effective resistance, parallel sampling 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 