How to Calculate the Barycenter of a Weighted Graph

• 成果类型: Article
• 署名作者: Gadat, Sebastien; Gavra, Ioana; Risser, Laurent
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0896
• 发表日期: 2018
• 页码: 1085-1118
• 关键词: frechet means; MANIFOLDS; algorithm; models; PCA

摘要

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