Incremental Computation of Pseudo-Inverse of Laplacian

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

A divide-and-conquer based approach for computing the Moore-Penrose pseudo-inverse of the combinatorial Laplacian matrix (L+) of a simple, undirected graph is proposed. The nature of the underlying sub-problems is studied in detail by means of an elegant interplay between L+ and the effective resistance distance (Ω). Closed forms are provided for a novel two-stage process that helps compute the pseudoinverse incrementally. Analogous scalar forms are obtained for the converse case, that of structural regress, which entails the breaking up of a graph into disjoint components through successive edge deletions. The scalar forms in both cases, show absolute element-wise independence at all stages, thus suggesting potential parallelizability. Analytical and experimental results are presented for dynamic (time-evolving) graphs as well as large graphs in general (representing real-world networks). An order of magnitude reduction in computational time is achieved for dynamic graphs; while in the general case, our approach performs better in practice than the standard methods, even though the worst case theoretical complexities may remain the same: an important contribution with consequences to the study of online social networks

Bibliographical note

Funding Information:
This research was supported in part by DTRA grant HDTRA1-09-1-0050, DoD ARO MURI Award W911NF-12-1-0385, and NSF grants IIS-0916750, CNS-10171647, CNS-1017092, CNS-1117536, IIS-1319749 and CRI-1305237.

Publisher Copyright:
© Springer International Publishing Switzerland 2014.

Fingerprint

Dive into the research topics of 'Incremental Computation of Pseudo-Inverse of Laplacian'. Together they form a unique fingerprint.

Cite this