Chapitre 1 Introduction aux graphes

Tout au long de ce cours nous nous intéressons à l’analyse de données avec une structure de graphes. Dans de nombreuses applications, un graphe ou un réseau décrit les interactions entre des individus, ou, plus généralement, entre des entités. Les entités qui interagissent ou communiquent entre eux ainsi que ce qui est considéré comme une interaction varient beaucoup et dépendent du contexte d’application. Par exemple, sur facebook les entités sont les membres du site et on peut considérer comme une interaction le fait que deux membres sont amis sur facebook. Quant au trafic aérien, les entités sont les aéroports et une interaction est un vol direct d’un aéroport vers l’autre. L’ensemble d’entités en interaction est dit réseau. Sa représentation mathématique est dite graphe.

L’importance grandissante de l’analyse des graphes vient aussi du fait qu’il y a de plus en plus de contextes où les données de départ n’ont rien avoir avec des graphes, mais il existe des représentations qui permettent une interprétation par un graphe et donc l’application des outils d’analyse des graphes pour étudier et comprendre ces données. Par exemple, pour décrire les réactions biochimiques du métabolisme d’un organismes ou d’une cellule, on peut les décrire comme des interactions entre des enzymes et des métabolites, connu sous le nom de réseau métabolique. Un autre exemple consiste en un jeu de données classiques, i.e. des observations \(x_i\in\mathbb R^p\), \(1\le i\le n\), et une notion de similarité entre deux vecteurs dans \(\mathbb R^p\). Alors, chaque observation représente le sommet dans un graphe et le poids d’une arête est la similarité entre les deux observations. De cette façon, on peut par exemple utiliser des méthodes de détection de communautés dans un graphe pour faire du clustering non supervisé des données \((x_i, 1\le i\le n)\).

Dans ce premier chapitre, nous verrons différents exemples de graphes dans de champs d’application divers. En plus, nous introduisons les notions de base des graphes.