Seconde · Sciences numériques et technologie

Utiliser les liens d'un graphe pour analyser un réseau social

Exploiter les liens (arêtes) d'un graphe de réseau social pour déterminer les voisins d'un nœud, son degré, les chemins entre deux nœuds et la portée d'une information.

Aperçu gratuit
Illustration de la fiche « Utiliser les liens d'un graphe pour analyser un réseau social »

Les points essentiels

  • Dans le graphe d'un réseau social, les nœuds représentent les personnes ou les comptes, et les liens représentent les relations : amitié, abonnement, échange de messages.
  • Un lien peut être non orienté (amitié réciproque : A est ami avec B équivaut à B est ami avec A) ou orienté (abonnement : A suit B n'implique pas que B suive A).

Les mots à connaître

Lien (arête)
Relation entre deux nœuds d'un graphe. Dans un réseau social, il traduit un rapport entre deux comptes : amitié, abonnement, échange. Il peut être orienté ou non.
Degré d'un nœud
Nombre de liens attachés à ce nœud, donc nombre de ses voisins dans un graphe non orienté. Dans un graphe orienté, on sépare degré entrant et degré sortant.

Un exemple pour comprendre

Dans un réseau d'amitiés (liens non orientés), on connaît les liens : Léa-Tom, Léa-Inès, Tom-Inès, Inès-Karim, Karim-Zoé. Donner les voisins et le degré de Léa et d'Inès, puis la distance entre Léa et Zoé.

Voisins de Léa : Tom et Inès, donc degré 2. Voisins d'Inès : Léa, Tom et Karim, donc degré 3. Pour aller de Léa à Zoé, on peut passer par Léa-Inès, Inès-Karim, Karim-Zoé : chemin de longueur 3. Le chemin Léa-Tom-Inès-Karim-Zoé mesure 4, il est plus long. Le plus court chemin a donc 3 liens : la distance entre Léa et Zoé est 3. Une information postée par Léa atteint Zoé au plus tôt en 3 étapes.

Première page de l’Essentiel : Utiliser les liens d'un graphe pour analyser un réseau social
Ketty