On the graph Laplacian and the rankability of data (Q2174433)

The paper further extends the concept of rankability proposed by \textit{P. E. Anderson, T. P. Chartier} and \textit{A. N. Langville} [``The rankability of data'', SIAM J. Math. Data Sci. 1, No. 1, 121--143 (2019; \url{doi:10.1137/18M1183595})]. Their rankability measure is based on how far a given directed graph is from a complete dominance graph, i.e., an acyclic tournament graph: let \(k\) denote the minimum number of edge additions or deletions needed to obtain a complete dominance graph. Next, allowing for \(k\) edge changes, let \(p\) represent the number of complete dominance graphs that can be obtained. Then, the rankability measure is defined by \[ \text{edgeR}=1-\frac{kp}{k_{\max}p_{\max}}, \] where \(k_{\max}=(n^2-n)/2\) and \(p_{\max}=n!\). The rankability measure edgeR is very expensive to compute (the calculation of \(p\) is of factorial complexity in the worst case). Hence, in this article, the authors propose a new cost-effective and more widely applicable measure of rankability and an algorithm that is based on a spectral-degree characterization of complete dominance graphs. In particular, given data that can be modeled as a digraph with weights between zero and one, the variation in the Laplacian spectrum and the out-degrees of the vertices from their known values for a complete dominance graph is measured. The authors support the algorithm with several results. First, for small perturbations, the variance in the Laplacian spectrum of a complete dominance graph is guaranteed to be small. Then, they show that a single edge change of a complete dominance graph changes one eigenvalue of the graph Laplacian by the weight of that edge. Finally, they prove a sharp upper bound on the Hausdorff distance between the Laplacian spectrum of a complete dominance graph and any other digraph with weights between zero and one.