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.
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.
Modélisation d'un réseau routier
Les graphes sont abondament utilisés par les logiciels de cartographie : Les sommets représentent les villes et les arêtes sont les routes qui les relient.
Certaines routes peuvent être à sens unique : on utilisera alors des arêtes orientées.