Définition et terminologie
On appelle graphe la donnée d'un ensemble de points appelés sommets et d'un ensemble de lignes appelées arêtes qui relient certains sommets entre eux.
Le nombre de sommets d'un graphe s'appelle l'ordre du graphe.
Deux sommets reliés entre eux par une arête sont dits adjacents.
C'est pour cela que l'utilisation de la théorie des graphes dans l'extraction des données des médias sociaux a un grand intérêt.
Son application permet par exemple de décrire chaque utilisateur sous forme de nœud, alors que les informations qu'ils s'échangent entre eux sont représentées sous forme de liens.
Un graphe est simple si au plus une arête relie deux sommets et s'il n'y a pas de boucle sur un sommet.
On peut imaginer des graphes avec une arête qui relie un sommet à lui-même (une boucle), ou plusieurs arêtes reliant les deux mêmes sommets.
On appelera ces graphes des multigraphes.