How to calculate the barycenter of a weighted graph

Discrete structures like graphs make it possible to naturally and flexibly model complex phenomena. Since graphs that represent various types of information are increasingly available today, their analysis has become a popular subject of research. Yet, even an algorithm for locating the average position in graphs is lacking although this knowledge would be of primary interest for statistical analysis or representation problems. In this work, we develop a stochastic algorithm for finding the Fréchet mean of weighted undirected metric graphs. This method relies on a noisy simulated annealing algorithm dealt with using homogenization. We then illustrate our algorithm with three examples (subgraphs of a social network, subgraph of a collaboration and citation network, and a transport network).