Abstract: The resistance distances, a robust alternative to geodesic distances on a network G(V,E), play a key role in exploratory network analysis across numerous application domains [Klein and Randić, 1993]. However, making the distance matrix Q(G) available and reusable for a large sparse network faced a scaling challenge: memory space for Q scales quadratically with n=|V|, and exact arithmetic computation scales cubically with n in the worst case. We present compressive representations of the distance matrix Q that are provably accurate and efficient. These include particularly the inverse Cholesky factor of the Laplacian matrix, and its submatrices. We provide experimental results on synthetic graphs and real-world networks. Our approach significantly reduces archival memory space compared to existing methods and enables fast elementwise decompression.

Hosts: Dr. Dimosthenis Pasadakis, Prof. Olaf Schenk