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).