%0 Book Section %1 ranjan2014 %A Ranjan, Gyan %A Zhang, Zhi-Li %A Boley, Daniel %B Combinatorial Optimization and Applications: 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings %D 2014 %E Zhang, Zhao %E Wu, Lidong %E Xu, Wen %E Du, Ding-Zhu %I Springer International Publishing %K effective.resistance laplacian pseudoinverse %P 729--749 %R 10.1007/978-3-319-12691-3_54 %T Incremental Computation of Pseudo-Inverse of Laplacian %X 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 pseudo-inverse 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. %@ 978-3-319-12691-3

@inbook{ranjan2014, 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 pseudo-inverse 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.}, added-at = {2016-08-30T08:48:59.000+0200}, author = {Ranjan, Gyan and Zhang, Zhi-Li and Boley, Daniel}, biburl = {https://www.bibsonomy.org/bibtex/203e1e5d1f8368b82ad03f1f5737ac542/ytyoun}, booktitle = {Combinatorial Optimization and Applications: 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings}, doi = {10.1007/978-3-319-12691-3_54}, editor = {Zhang, Zhao and Wu, Lidong and Xu, Wen and Du, Ding-Zhu}, interhash = {1a8d683ef4d867c4dd0f4fd46efe9e0b}, intrahash = {03e1e5d1f8368b82ad03f1f5737ac542}, isbn = {978-3-319-12691-3}, keywords = {effective.resistance laplacian pseudoinverse}, pages = {729--749}, publisher = {Springer International Publishing}, timestamp = {2016-08-31T09:40:56.000+0200}, title = {Incremental Computation of Pseudo-Inverse of {Laplacian}}, year = 2014 }