Birkhoff polytopes, heat kernels and graph complexity
Francisco Javier Escolano, Edwin R. Hancock, Miguel Ángel Lozano · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · 2008
In this paper we use doubly stochastic matrices to establish a link between Birkhoff polytopes and heat kernels on graphs. Based on this analysis we construct a multi-dimensional graph complexity measure characterized by the sequence of entropies associated to the Birkhoff-von Neumann decompositions (structural snapshots) of kernels with variable beta (range interaction factors). This construction is motivated by analogies with solving of traffic and transportation problems. We test the permutation invariance of the measure and demonstrate its application to graph embedding.