Skip to Main content Skip to Navigation
Accreditation to supervise research

Capturing Binary Graphs

Gilles Trédan 1
1 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : This thesis regroups a set of algorithmical approaches related to the problem of graph metrology. Graphs are an abstraction representing a set of entities along with their interactions. As such, they are widely used as a tool to model real-life homogeneous systems. However, when using graphs to represent actual systems, a central question is "How to accurately represent these systems using graphs ?". Indeed, when using Graphs as an abstraction to represent a real interaction system, accurately obtaining the set of interactions is sometimes difficult. As a consequence, the captured graph is often an imperfect representation of the real system. But how useful are those imperfect representations ? We show in the first part of this manuscript that some theoretical analyses of graph capture approaches provide bad pessimistic answers. The second part of this manuscript focuses on modeling real graphs to provide an approach to this question in the context of human mobility. By extensively collecting data on interacting humans in a crowd, we showcase some uses for interaction graphs despite their imperfections. The last part of this manuscript takes a step back on these analyses by providing some tools to chart the space of possible graphs. The angle pursued is to provide useful distances on the space of graphs that more precisely allow to differentiate errors that matter and errors that don't.
Document type :
Accreditation to supervise research
Complete list of metadata

Cited literature [153 references]  Display  Hide  Download
Contributor : Laas Hal-Laas <>
Submitted on : Friday, September 27, 2019 - 9:25:36 AM
Last modification on : Thursday, June 10, 2021 - 3:07:01 AM
Long-term archiving on: : Monday, February 10, 2020 - 8:22:02 AM


TREDAN Gilles.pdf
Files produced by the author(s)


  • HAL Id : tel-02298644, version 1


Gilles Trédan. Capturing Binary Graphs. Computer Science [cs]. Institut National Polytechnique de Toulouse (INPT), 2019. ⟨tel-02298644⟩



Record views


Files downloads