2.5 Motifs

La topologie d’un graphe peut être capter par les occurences d’un motif donné. Un motif est un sous-graphe de structure particulière, comme des triangles, cliques, étoiles, cycles, arbres… La Figure 2.3 montre quelques exemple.

Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.

Figure 2.3: Quelques exemples de motifs comme des triangles, cliques, étoiles, cycles, arbres.

Plus formellement, on a les définitions mathématiques suivantes.

Definition 2.7 Soient \(G=(V,E)\) et \(G'=(V',E')\) deux graphes. On dit que

  • \(G'\) est un sous-graphe de \(G\) (et on note \(G'\subset G\)) si \(V'\subset V\) et \(E'\subset E\).
  • \(G'\) est un sous-graphe induit de \(G\) lorsque \(G'\subset G\) et \(E'\) contient toutes les arêtes \(\{i,j\}\in E\) telles que \(i,j\in V'\).
  • \(G\) et \(G'\) sont isomorphes s’il existe une bijection \(\phi: V\to V'\) telle que \(\{i,j\}\in E\) si et seulement si \(\{\phi(i),\phi(j)\} \in E'\).
  • Un motif \(m\) d’un graphe \(G\) est un sous-graphe induit de \(G\).

Chercher les occurrences de \(m\) dans un graphe \(G\), c’est chercher tous les sous-graphes induits de \(G\) qui sont isomorphes à \(m\). Souvent, on ne s’intéresse pas au nombre absolu de motifs dans un graphe, mais à sa densité, i.e. à la proportion de motifs réalisés dans \(G\) comparé au nombre de motifs dans un graphe complet.

On peut par exemple construire des tests statistiques basés sur l’occurence d’un motif ou sa densité pour décider si le graphe \(G\) observé correspond au nombre attendu dans un modèle de graphe de référence, i.e. un modèle sous une hypothèse nulle \(H_0\). Ce modèle de référence peut être un modèle défini analytiquement ou un autre graphe observé.