Cours : Les réseaux sociaux, l'expérience du petit monde et les graphes

Expérience du petit monde

Il nous est tous arrivé de rencontrer quelqu’un d’inconnu, qui, après discussion, se trouve lié à l’une de nos connaissances.
C’est le phénomène du petit monde ou le paradoxe de Milgram. Ce phénomène en effet répond à la question suivante : combien de liens, en moyenne, séparent une personne de n’importe quelle autre personne sur Terre ? Le résultat tourne autour de 6, on l’appelle d’ailleurs la théorie des 6 degrés de séparation.

Définition

Le petit monde :

Le concept de psycho-sociologie appelé « effet du petit monde » est apparu en 1929, il suppose que tous les individus étaient reliés par une faible chaîne de maillons sociaux. Il a été vérifié pour la première fois en 1967, par le psycho-sociologue Stanley Milgram (bien avant la création de Facebook et de Twitter).

Dès 1929, l’écrivain hongrois Frigyes Karinthy pose l’hypothèse selon laquelle toute personne est liée à toute autre par l’intermédiaire de cinq individus au plus, pour déduire que le monde rétrécit au fur et à mesure que la connexion entre les hommes grandit.

• Ce n’est qu’en 1967, avec Stanley Milgram et son expérience du petit monde, que l’hypothèse est vérifiée.

L’expérience consistait à désigner des participants habitant différentes villes des États-Unis, ils avaient pour mission de faire parvenir un document à un individu ciblé (nom, profession, ville…) par l’intermédiaire de personnes le connaissant ou connaissant une personne le connaissant. À l’issue de l’expérience, et dans le cas des documents parvenus à bon port, la moyenne du nombre d’intermédiaires constatée est de 5,2 personnes. Ce qui démontre l’hypothèse de Frigyes Karinthy, la théorie est alors appelée « les six degrés de séparation ».

Les réseaux sociaux numériques

Le succès des réseaux sociaux prend une dimension considérable à la lumière de ces théories. En effet le principe des six degrés de séparation laisse penser qu’il existe une méta-communauté à l’échelle de la planète.
La vérification des bases de données que constituent les médias sociaux confirme que le nombre d’intermédiaires entre deux individus pris au hasard sur les réseaux sociaux numériques publics se situe entre cinq et sept en moyenne.

Définition

Réseau social :

Un réseau social est un service de mise en relation entre des individus qui ont des intérêts communs. Au sein de cette communauté créée, il sera possible d’échanger et de partager le contenu généré par les membres.

Les types de réseaux sociaux

Il existe divers types de réseaux sociaux, toutefois, deux grandes catégories sont à distinguer : les réseaux sociaux professionnels et ceux à usage personnel.

Un réseau social professionnel met en avant l’expertise de l’utilisateur à travers sa formation académique, ses expériences ou ses réalisations. Les plus populaires sont LinkedIn et Viadeo.

Un réseau social « grand public » est destiné à un usage personnel. Chaque utilisateur crée un profil accessible à une liste d’amis avec qui il est possible de partager un contenu de divers formats (vidéo, lien, photo…). On trouve dans cette catégorie 3 réseaux populaires : Facebook, Youtube et Twitter.

Les réseaux sociaux en chiffres

Les réseaux sociaux ont changé nos modes de vie et leur utilisation ne cesse d’augmenter à travers le monde. Des statistiques affichent $3,2$ milliards d’utilisateurs de réseaux sociaux (source : Emarsys 2019), un chiffre qui équivaut à peu près à la moitié de la population mondiale. De plus, d’après un rapport de We Are Social et Hootsuite, un internaute passe en moyenne 2h16 par jour sur les réseaux sociaux.

Selon une étude faite par Hootsuite et We Are Social en octobre 2019, voici le classement des réseaux sociaux les plus populaires en termes de nombre d’utilisateurs actifs en 2019 :

• Facebook (créé en 2004)
• YouTube, qui appartient à Google
• WhatsApp
• Facebook Messenger
• WeChat (Weixin)
• Instagram
• La tête du classement est tenue par Facebook avec $2,45$ milliards d’utilisateurs actifs mensuels et $400$ utilisateurs qui s’inscrivent chaque minute.

Les graphes

Les réseaux sociaux sont modélisés par des graphes. Cette représentation permet de faire l’analyse des réseaux afin d’extraire des informations et de détecter des communautés d’intérêts.

Définition

Graphe :

Un graphe est une structure composée d’objets dans laquelle certaines paires d’objets sont en relation. Les objets correspondent à des sommets (ou nœuds ou points) et les relations entre les sommets sont des arêtes (ou liens ou lignes). On distingue : les graphes non orientés, et les graphes orientés.

• Graphes non orientés : les arêtes relient deux sommets de manière symétrique.
• Graphe orientés : les arêtes sont appelées flèches et relient deux sommets de manière asymétrique : la flèche qui va du sommet $a$ vers le sommet $b$ n’est pas la même que celle allant dans le sens contraire (de $b$ vers $a$).

Un graphe est représenté par un diagramme sous la forme d’un ensemble de sommets joints entre eux par des arêtes (munies de flèches pour les graphes orientés).

Exemple

Un graphe non orienté, un graphe orienté et un graphe mixte

Types de graphes

Graphe pondéré

Un réseau est un graphe pondéré, c’est-à-dire un graphe où chaque arête porte un nombre : son poids. Ce poids peut représenter par exemple un coût, une longueur ou une capacité, en fonction du problème traité.
Pour le problème du plus court chemin, le poids des arêtes est une longueur.

Exemple

Un graphe pondéré avec 10 sommets et 12 arêtes

• Les graphes pondérés sont utilisés dans les réseaux sociaux qui ont différents niveaux d’intensités dans les relations comme Facebook.

Graphe asymétrique

C’est un graphe orienté ou l’un des couples $(x,y)$ et $(y,x)$ est une flèche du graphe. Ce graphe est sans boucle.

Exemple

Si on prend le cas de Twitter, on peut représenter l’utilisateur par un sommet, lorsqu’un utilisateur « suit » un autre utilisateur on ajoute un arc orienté du premier sommet vers le deuxième, mais il n’y a pas de symétrie dans l’amitié.

• Avec Twitter ou Instagram, il n’y a pas de réciprocité dans les relations entre les sommets (les individus), les graphes sont donc asymétriques et orientés.

Dans le cas de Facebook, les graphes sont non orientés à cause de la symétrie entre les individus (amitié dans les deux sens).

Graphe connexe

Définition

Graphe connexe :

Un graphe non orienté est connexe si, quels que soient deux sommets $x$ et $y$, il existe une chaîne (une suite d’arêtes) reliant $x$ à $y$.

Exemple

Un graphe connexe et un graphe non connexe

Cycle

Définition

Cycle :

Dans un graphe non orienté, un cycle de longueur $n$ est une suite de $n$ arêtes dont les deux sommets aux extrémités sont identiques.

Exemple

Dans le graphe ci-dessous on a un cycle rouge et un cycle bleu. En revanche, la suite des arêtes noires n’est pas un cycle.

Arbre

Définition

Arbre :

Un arbre est un graphe connexe sans cycle.

Exemple

Par exemple le réseau social LinkedIn peut être représenté par un arbre où un utilisateur représente le sommet (ou nœud) et les membres de son réseau sont des sommets qui lui sont liés par des arcs.

Un arbre modélisant des relations sur LinkedIn

À retenir

Alors qu’un graphe peut contenir des cycles, un arbre n’en contient jamais.

Propriétés d’un graphe

• Deux arêtes d’un graphe sont adjacentes si elles ont un sommet en commun. De même deux sommets sont adjacents s’ils sont l’extrémité d’une même arête (arc). Alors qu’une arête et un sommet adjacent sont dits incidents l’un à l’autre.
• Deux arcs d’un graphe orienté sont consécutifs si la fin du premier arc est le début du deuxième.
• Un graphe est étiqueté aux arêtes si chaque arête porte une étiquette (mot, nombre, lettre…).
• Un graphe est appelé trivial s’il est formé d’un seul sommet et sans arêtes.

Exemple

Le graphe ci-dessous est étiqueté.

L’arête $a$ est adjacente à l’arête $b$ et ces deux arêtes sont consécutives.
Le sommet $A$ est incident à l’arête portant l’étiquette $a$.

Centre, diamètre et rayon d’un graphe

La centralité mesure la pertinence et l’importance d’un sommet. On distingue :

• la centralité de degré : c’est le nombre d’arêtes incidentes à un sommet ;
• la centralité de proximité : c’est l’inverse de la somme des distances à tous les autres sommets ;
• la centralité d’intermédiarité : est égale au nombre de fois où ce sommet apparaît sur le chemin le plus court reliant deux sommets du graphe. Remarque : un graphe peut avoir plusieurs centres.

Définition

Diamètre d’un graphe :

Le diamètre d’un graphe est le plus grand nombre d’arêtes qui peuvent relier deux sommets distincts de ce graphe. Ce nombre d’arêtes est appelé distance.

Exemple

Le diamètre de ce graphe est la distance entre les sommets $A$ et $E$, c’est la plus grande distance du graphe, elle est égale à $4$ et elle est donnée par la longueur de la chaine $A-B-C-D-E$.

Définition

Rayon d’un graphe :

Le rayon d’un graphe est l’écartement d’un centre du graphe, c’est donc la distance la plus courte entre deux sommets.

Exemple

Dans ce graphe, puisque tout sommet peut être relié à n’importe quel autre sommet par une chaîne de deux arêtes, ils sont tous des centres du graphe et leur écartement est de $2$. Le rayon de ce graphe est donc $2$.

Modélisation d’un réseau à l’aide d’un graphe

Prenons l’exemple d’un groupe d’adolescents : Pierre, Julie, Marie, Paul et Camille qui sont dans la même école.
Pierre et Julie sont dans la même classe, Julie et Marie sont voisines, tout comme Paul et Camille et Julie et Paul sont dans la même équipe de volley-ball.
Les relations entre ces individus peuvent être représentées par un graphe, en plaçant les noms des élèves dans des sommets et en illustrant les liens entre eux avec des arêtes.

L’élève qui a le plus de liens avec les autres est Julie.

• Julie est donc le centre du graphe.

La distance la plus longue entre deux sommets (le diamètre) est de $3$, c’est la relation entre Pierre et Camille ou entre Marie et Camille. Le rayon de ce graphe est la distance la plus courte entre 2 sommets, c’est donc $1$.