Warshall algorithm for matrix-weighted graphs

Abstract

This paper proposes Warshall-type algorithms for determining connectedness and clustering in an undirected matrix-weighted graphs. While a path between two vertices guarantees their connectedness in a scalar-weighted graph, the existence of one or more paths between them does not necessarily guarantee that they belong to the same cluster in a matrix-weighted graph. First, a sufficient condition for pairwise connectedness is established via aggregating path kernels between them. Second, we introduce three block matrix logic operators that enables the connectedness condition to be compactly represented and manipulated with positive semidefinite matrices. The proposed Warshall algorithm simultaneously determines connectivity between every pair of vertices in the graph and provides an approximated graph partition. Third, a distributed version of the Warshall algorithm is developed. Proofs of correctness, together with computational complexity analysis and numerical examples, are provided to establish the validity of the proposed algorithms.

26 pages, 8 figures, preprint submitted to a journal