Graphes et réseaux sociaux
La théorie des graphes est une branche des mathématiques, passionnante pour toute personne intéressée par les maths appliquées. Certes, elle permettait déjà certaines applications au vingtième siècle (essentiellement dans des problématiques visant à gagner du temps). Mais avec le développement d’Internet, elle s’est retrouvée sur le devant la scène.
Ainsi, l’étude des graphes n’a plus été réservée aux universités et a été enseignés dès le lycée. Après la disparition de la terminale ES spécialité maths, elle a trouvé sa place en cours de SNI après une première approche en seconde (en SNT). Considérez cette page d’initiation comme une ressource de SNT.
Réseaux numériques
Un graphe est un ensemble de sommets (ou nœuds) reliés par des arêtes.
Par exemple, un réseau social peut être représenté par un graphe. Les sommets sont les personnes et les arêtes indiquent les liens « d’amitié » entre elles.
Il est possible de déterminer un ou plusieurs centres du graphe. Un centre est un sommet dont l’écartement avec les autres sommets est minimal. Dans le cas d’un réseau social, un tel sommet représente un influenceur, susceptible de diffuser une information le plus vite possible auprès d’un maximum d’internautes. L’écartement entre le centre et le sommet le plus éloigné est appelé le rayon du graphe.
Le diamètre est la distance maximale qui peut exister entre deux sommets du graphe.
Il existe deux sortes de graphes : orientés et non orientés. Dans un graphe orienté, les arêtes (appelées arcs) sont des flèches parce que des relations à sens unique sont possibles.
Si dans un réseau social A est ami avec B implique que B est ami avec A, il s’agit d’un réseau non orienté. Si au contraire on représente un site web dont les pages sont les sommets du graphe, ce sont bien des arcs qui indiquent les liens hypertextes entre les pages. En effet, le fait qu’il existe en page A un lien qui pointe vers la page B n’implique pas qu’il existe un lien de B vers A. Un site web peut donc être représenté par un graphe orienté.
Exemple de représentation
Soit un très petit réseau social.
-
A est ami avec B, D et F
B est ami avec A et C
C est ami avec B, D, E, F et G.
D est ami avec A, C et G
E est ami avec C et F
F est ami avec A, C, E et G
G est ami avec C, D et F
Pour représenter ces liens avec un graphe, nous utiliserons le logiciel en ligne open source Graph Online.
Notez que la disposition des sommets n’a aucune importance, même s’il est préférable de présenter un graphe le moins embrouillé possible. Le graphe suivant est donc le même que celui ci-dessus mais la position centrale de C apparaît mieux.
Matrice d’adjacence
Un graphe est une représentation commode si le nombre de sommets est faible mais un peu confus pour représenter un réseau social d’un milliard d’abonnés. De toute façon, vous vous doutez bien que s’il y a des calculs derrière, il existe un outil mathématique plus opérationnel. C’est comme lorsque vous étudiez une fonction : vous ne le faites pas à partir de sa courbe.
En l’occurrence, il s’agit de la matrice d’adjacence. C’est un tableau composé de 1 et de 0, soit 1 si le lien existe et 0 sinon. Nous n’aborderons pas les autres types de matrices.
Ci-dessous, Graph Online a réalisé la matrice d’adjacence du graphe qui nous a servi d’exemple.
Un autre outil est la matrice des distances. Une distance est le nombre minimum d'arêtes entre deux sommets.
Remarquez la troisième ligne (ou la troisième colonne ; ce sont les mêmes puisque le graphe n’est pas orienté). Elle correspond à C. Si l’on additionnait les distances, il apparaîtrait qu’il est l’influenceur (distances minimales). Nous constatons par la même occasion que le rayon est 2.
Ce graphe n'a que sept sommets. Ces deux matrices peuvent donc être réalisées à la main (si vous voulez vous exercer...)
Maintenant, vous êtes fin prêts pour vous lancer dans des exercices sur les graphes.
Note : pour savoir réaliser des opérations avec des matrices, vous devrez attendre la terminale, sauf si vous souhaitez prendre de l’avance grâce à ce site…
