English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The pseudo-inverse of a graph Laplacian matrix, denoted as $L^\dagger$, findsextensive application in various graph analysis tasks. Notable examples includethe calculation of electrical closeness centrality, determination of Kemeny'sconstant, and evaluation of resistance distance. However, existing algorithmsfor computing $L^\dagger$ are often computationally expensive when dealing withlarge graphs. To overcome this challenge, we propose novel solutions forapproximating $L^\dagger$ by establishing a connection with the inverse of aLaplacian submatrix $L_v$. This submatrix is obtained by removing the $v$-throw and column from the original Laplacian matrix $L$. The key advantage ofthis connection is that $L_v^{-1}$ exhibits various interesting combinatorialinterpretations. We present two innovative interpretations of $L_v^{-1}$ basedon spanning trees and loop-erased random walks, which allow us to developefficient sampling algorithms. Building upon these new theoretical insights, wepropose two novel algorithms for efficiently approximating both electricalcloseness centrality and Kemeny's constant. We extensively evaluate theperformance of our algorithms on five real-life datasets. The resultsdemonstrate that our novel approaches significantly outperform thestate-of-the-art methods by several orders of magnitude in terms of bothrunning time and estimation errors for these two graph analysis tasks. Tofurther illustrate the effectiveness of electrical closeness centrality andKemeny's constant, we present two case studies that showcase the practicalapplications of these metrics.

Scalable Algorithms for Laplacian Pseudo-inverse Computation