Developments in the theory of randomized shortest paths
Résumé : There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into account the global structure of the graph. This talk presents developments in the theory of one family of graph node distances, known as the randomized shortest path (RSP) dissimilarity. We derive a new definition of a distance measure that we call the free energy distance. The free energy distance can be seen as an upgrade of the RSP dissimilarity as it satisfies several nice properties for a distance and is quite straightforward to compute. We also make a comparison between a set of generalized distances that interpolate between the shortest path distance and the commute time or resistance distance. In addition, we present a so called bag-of-paths model, which defines a probability distribution over paths on a graph. This model can furthermore be used to define distances on a graph as well as a new modularity measure.
Cet exposé se tiendra en salle C20-13, 20ème étage, Université Paris 1, Centre Pierre Mendès-France, 90 rue de Tolbiac, 75013 Paris (métro : Olympiades).