Toulouse 1 Capitole Publications

How to calculate the barycenter of a weighted graph

Gadat, Sébastien, Gavra, Ioana and Risser, Laurent (2017) How to calculate the barycenter of a weighted graph. Mathematics of Operations Research. (In Press)

This is the latest version of this item.

[img]
Preview
Text
Download (1MB) | Preview
Official URL: http://tse-fr.eu/pub/31777

Abstract

Discrete structures like graphs make it possible to naturally and exibly model complex phenomena. Since graphs that represent various types of information are increasingly available today, their analysis has become a popular subject of research. The graphs studied in the field of data science at this time generally have a large number of nodes that are not fairly weighted and connected to each other, translating a structural specification of the data. Yet, even an algorithm for locating the average position in graphs is lacking although this knowledge would be of primary interest for statistical 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 two examples (subgraphs of a social network and of a collaboration and citation network).

Item Type: Article
Language: English
Date: 2017
Refereed: Yes
Uncontrolled Keywords: metric graphs, Markov process, simulated annealing, homogeneization
Subjects: B- ECONOMIE ET FINANCE
Divisions: Toulouse School of Economics - TSE
Site: UT1
Date Deposited: 15 Jun 2017 07:57
Last Modified: 15 Jun 2017 07:57
OAI ID: oai:tse-fr.eu:31777
URI: http://publications.ut-capitole.fr/id/eprint/24155

Available Versions of this Item

Actions (login required)

View Item View Item