2022/01/26 by Knight, Philip A.
#Matrix balancing #PageRank #Sinkhorn-Knopp algorithm #doubly stochastic matrix
paper · doi:10.4230/dagsemproc.07071.16
As long as a square nonnegative matrix A contains sufficient nonzero elements, the Sinkhorn-Knopp algorithm can be used to balance the matrix, that is, to find a diagonal scaling of A that is doubly stochastic. We relate balancing to problems in traffic flow and describe how balancing algorithms can be used to give a two sided measure of nodes in a graph. We show that with an appropriate modification, the Sinkhorn-Knopp algorithm is a natural candidate for computing the measure on enormous data sets.