Les réseaux sociaux peuvent être modélisés sous forme de graphes, qui illustrent ainsi l’état des relations sociales au sein d’un groupe.

 

Les graphes sont constitués :

• De sommets (aussi appelés nœuds) qui représentent les membres du réseau.
• D’arêtes (aussi appelées liens) qui relient les sommets entre eux et qui
représentent les relations entre les membres du réseau.

• Une chaîne est une suite de sommets reliés par des arêtes.
• La longueur d’une chaîne est le nombre d’arêtes qui la constituent.
• La distance entre deux sommets correspond à la longueur de la plus petite chaîne qui les relie.
• Le degré d’un sommet est le nombre d’arêtes qui partent de ce sommet.

Un graphe peut être orienté si les relations entre deux individus ne vont que dans un seul sens (par exemple pour Twitter), ou non orienté dans le cas contraire (par exemple pour Facebook).

L’excentricité d’un sommet du graphe est la distance maximale existant entre ce sommet et les autres sommets du
graphe.

Le diamètre d’un graphe est la plus grande distance qui sépare deux sommets (c’est donc la plus grande excentricité
qu’on puisse trouver parmi les sommets du graphe).

Pour le graphe ci-dessous , la distance de Karim à Aminata est de 2, et de Gaston à Jessica de 3 par exemple. Le degré du
sommet d’Aminata est de 4, d’Amaury de 3 et de Karim de 2. L’Excentricité de Aminata est de 2 et de Gaston de 4
(Gaston vers Karim). Le diamètre du graphe est donc de 4, la plus grande distance.