How to Calculate the Barycenter of a Weighted Graph

Sébastien Gadat (), Ioana Gavra () and Laurent Risser ()
Additional contact information
Ioana Gavra: Institut de Mathématiques de Toulouse, Université Toulouse 3 Paul Sabatier, 31400 Toulouse, France
Laurent Risser: Institut de Mathématiques de Toulouse, CNRS, 31400 Toulouse, France

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1085-1118

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

Keywords: metric graphs; Markov process; simulated annealing; homogenization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0896 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1085-1118

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().