Editions ENI Livres | Vidéos | e-Formations
Graphes et réseaux
Introduction
L’étude des graphes porte sur des aspects variés. Les principales différences ou similarités sont étudiées soit entre des graphes ou des parties de graphe, soit entre des nœuds de graphe (typiquement dans un graphe ou une partie de graphe).
Le chapitre Introduction a présenté la notion de degré, qui est une feature simple mais malheureusement insuffisante pour qualifier les graphes et les nœuds.
Des noyaux (kernels) appliqués aux graphes permettent de capturer puis de manipuler diverses caractéristiques de la structure des graphes au travers de nos techniques de machine learning habituelles, ce n’est donc pas l’objet ici. Ce chapitre se focalise sur des aspects vraiment spécifiques des graphes.
Premiers pas
La théorie des graphes comprend de nombreux concepts, théorèmes et notations très précis, mais un peu troublants car ces définitions varient à la marge suivant les auteurs. Nous ne définirons pas mathématiquement tous les concepts sous-jacents à notre utilisation des graphes, car un chapitre n’y suffirait pas. Vous trouverez ici une sélection de termes clés et de définitions "en français" assez fiables pour permettre de manipuler les graphes dans un contexte opérationnel. En cas de doute, référez-vous aux sources citées dans l’introduction de l’ouvrage.
1. Quelques notions et notations complémentaires basiques
Il faut s’imprégner des notions suivantes et chercher à les reconnaître dans les graphes que vous croiserez.
Un graphe fini non orienté sans boucle (loop), c’est-à-dire un graphe simple (undirected simple) s’écrit G(V, E). Attention, parfois on note de la même façon des graphes d’autre nature (non simples, orientés, hypergraphes...).
Ses nœuds ou vertices s’écrivent V(G) = {v1,,..., vn}.
Point de vocabulaire : en anglais vertices est le pluriel de vertex.
Ses arêtes ou edges s’écrivent E(G) = {e1,,...,en}.
Quand il n’y a pas d’ambiguïté, il est inutile d’écrire le (G).
Les arêtes sont des éléments du produit cartésien V x V.
Deux nœuds distincts sont adjacents quand ils partagent la même arête.
Deux arêtes distinctes sont adjacentes quand elles partagent un même nœud.
Une chaîne (walk) entre deux nœuds distincts, ses extrémités, est un graphe de nœuds adjacents tels que seules les extrémités ont un degré égal à 1 au sein de ce graphe. Parfois on parle de chaîne ouverte ou open walk.
Une chaîne élémentaire (trail) est une chaîne dont le degré maximum d’un nœud est 2 : elle ne repasse jamais par le même nœud (attention, dans certains textes le terme chaîne désigne une chaîne élémentaire).
Un cycle (closed walk, cycle) est un graphe de nœuds adjacents de degrés...
Graphes et réseaux (sociaux)
Les notions que nous allons mettre en œuvre ici ne sont pas spécifiques de l’étude des réseaux sociaux, mais elles sont largement employées dans ce cadre.
Un réseau social est composé d’acteurs (des humains, des groupes d’humains, des personnes morales) qui sont reliés par des liens que l’on qualifie comme liens sociaux, typiquement des interactions, synchrones ou non.
Évidemment, il est d’usage de représenter les acteurs par des nœuds et les relations par des arêtes ou des arcs, ce que l’on nomme parfois sociogramme quand les relations portent directement ou indirectement des concepts d’affinité entre les acteurs (qui est choisi par qui, qui est meneur...).
Les relations peuvent être structurelles (employé par…, collègue de...), factuelles (dialogue avec, participe à ... avec ...), ou déclaratives (like..., aime...). Souvent ces relations s’étendent aux objets entourant les acteurs : "untel aime tel film".
Quand les relations sont symétriques, comme le fait d’être relié sur LinkedIn, on obtient des graphes non orientés. Quand les graphes représentent l’expression d’opinions (sur quelqu’un ou quelque chose) ou quand ils représentent les abonnements à des services ou les envois de tweets ou de mails, cela donne des graphes orientés.
Si la relation est quantifiée, comme le nombre de tweets envoyés à quelqu’un, le nombre d’étoiles signifiant que l’on apprécie quelque chose, le nombre de liens communs, de smileys... on a affaire à un graphe valué (qui comporte des poids, weights en anglais).
Les types de relations sont étiquetés sur les arcs ou les arêtes (collègue, follower...).
1. Analyse des réseaux sociaux : concepts de base
Les notions les plus couramment utilisées dans l’analyse des réseaux sociaux sont la densité des liens du réseau (density of links) et la centralité (centrality).
La densité de liens représente tout simplement le nombre de liens réels versus le nombre de liens possibles. Elle transparaît quand certaines parties du graphe comportent...
