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

Expérience du petit monde

• Dès 1929, l’écrivain Frigyes Karinthy pose l’hypothèse que toute personne est liée à toute autre par l’intermédiaire de cinq individus au plus : 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é par l’intermédiaire d’autres personnes. À l’issue de l’expérience, la moyenne du nombre d’intermédiaires constatée est de 5,2 personnes.
• Le phénomène du petit monde ou le paradoxe de Milgram 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.

Les réseaux sociaux numériques

• 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.
• Le succès des réseaux sociaux prend une dimension considérable à la lumière de la théorie des 6 degrés de spéaration.
• En effet ce principe laisse penser qu’il existe une méta-communauté à l’échelle de la planète.
• Les bases de données confirment 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.
• 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.
• On trouve 3 réseaux populaires : Facebook, Youtube et Twitter.
• 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 des études, un internaute passe en moyenne 2h16 par jour sur les réseaux sociaux.

Les graphes

• Les réseaux sociaux sont modélisés par des graphes afin d’extraire des informations et de détecter des communautés d’intérêts.
• Un graphe est une structure composée d’objets dans laquelle certaines paires d’objets sont en relation : des sommets (ou nœuds ou points) et des arêtes (ou liens ou lignes).
• Dans les graphes non orientés : les arêtes relient deux sommets de manière symétrique.
• Les amitiés sur Facebook sont représentées par des graphes non orientés.
• Dans les 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 réseau est un graphe pondéré, c’est-à-dire un graphe où chaque arête porte un nombre : son poids (qui équivaut à un coût, une longueur ou une capacité).

• 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.
• Un graphe asymétrique 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.
• 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.
• 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$.
• 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.
• Un arbre est un graphe connexe sans cycle.
• Par exemple le réseau social LinkedIn peut être représenté par un arbre où un utilisateur représente le sommet et les membres de son réseau sont des sommets qui lui sont liés par des arcs.
• 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 ;
• 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.
• 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.
• Le diamètre d’un graphe est le plus grand nombre d’arêtes (distance) qui peuvent relier deux sommets distincts de ce 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.