Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis

DOI10.4230/LIPIcs.ESA.2020.6OpenAlexW3082100445MaRDI QIDQ5874469

Alexander van der Grinten, Eugenio Angriman, Maria Predari, Henning Meyerhenke

Publication date: 7 February 2023

Full work available at URL: https://arxiv.org/abs/2006.13679

zbMATH Keywords

effective resistanceuniform spanning treeparallel samplingelectrical centrality measuresLaplacian pseudoinverse

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (max. 100)

Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Numerically efficient \(H_\infty\) analysis of cooperative multi-agent systems

Uses Software

• Eigen
• LAMG
• KONECT
• Pselinv

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effective resistance on graphs and the epidemic quasimetric
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Effective graph resistance
• Rational approximation to the Fermi-Dirac function with applications in density functional theory
• The electrical resistance of a graph captures its commute and cover times
• An estimator for the diagonal of a matrix
• Probability on Trees and Networks
• Incremental Computation of Pseudo-Inverse of Laplacian
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Extensions of Lipschitz mappings into a Hilbert space
• Ranking of Closeness Centrality for Large-Scale Social Networks
• Axioms for Centrality
• Graph Clustering using Effective Resistance
• An almost-linear time algorithm for uniform random spanning tree generation
• Computing Top-k Closeness Centrality Faster in Unweighted Graphs
• Parallel Computation of Entries of ${A}^{-1}$
• An efficient parallel solver for SDD linear systems
• Solving SDD linear systems in nearly m log ^1/2 n time
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Approaching Optimality for Solving SDD Linear Systems
• Minimizing Effective Resistance of a Graph
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• STACS 2005
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• Graph Sparsification by Effective Resistances

This page was built for publication: Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis