Analyse des graphiques de réseau : visualiser les personnages de Hamilton en tant que réseau social

Il y a quelques années, je lisais de façon excessive les livres de Game of Thrones et j'avais du mal à garder une trace de tous les personnages dans ma tête. (Ce n'est pas surprenant – il y a plus de 150 personnages nommés dans la série !) Je faisais des allers-retours entre les chapitres ou je cherchais constamment le wiki A Song of Ice and Fire pour me souvenir des intrigues. J'avais besoin d'une carte mentale – il y avait sûrement une meilleure façon de visualiser ces personnages ?

Les bases

L'image ci-dessous est un exemple de graphique de réseau de Wikipédia qui illustre les contributions des éditeurs de Wikipédia à différentes langues. À l'aide de cet exemple, voici quelques bases (ou un rappel rapide, si vous êtes déjà familier) des concepts de la théorie des graphes :

• Les cercles représentant les langues dans lesquelles les articles ont été rédigés sont les « sommets » du graphique (indifféremment les « nœuds »).

• Les « arêtes » sont les lignes reliant chaque paire de sommets. Chaque arête du graphique est déterminée via une fonction d'incidence qui mappe une paire de sommets à une arête.

  
  

Dans cet exemple, chaque bord représente (en épaisseur ou en épaisseur de trait) le nombre d'éditeurs qui ont contribué aux deux langues reliées par la ligne. C'est ce que nous appelons un graphe simple non orienté. "Non orienté" signifiant que {en--> fr} et {fr --> en} sont identiques, et "simple" signifie qu'il n'y a pas plus d'une arête reliant chaque paire de sommets. Le graphique est également « pondéré », ce qui signifie que l’épaisseur des arêtes est relative à la force de la relation entre les sommets. Dans cet exemple, la fonction d'incidence pondérée pourrait ressembler à ceci :

Bien que la représentation visuelle des graphiques de cette manière constitue une approche intuitive pour montrer rapidement les relations afin qu'elles soient faciles à comprendre, il existe des informations encore plus riches que nous pouvons tirer de la représentation d'un ensemble de données en tant qu'objet graphique.

Obtenir les données pour l'ensemble de données Hamilton

« En science des données, 80 % du temps est consacré à la préparation des données, et 20 % du temps est consacré à se plaindre de la nécessité de préparer les données. »

Les data scientists ne sont peut-être pas d'accord sur tout, mais nous convenons que la partie la plus difficile de tout projet consiste à obtenir les données. Heureusement pour nous, cette partie est derrière nous pour cet article. Il existe un bel ensemble de données claires de paroles de Hamilton facilement disponibles sur Kaggle que vous pouvez simplement télécharger et commencer à représenter graphiquement.

Analyse exploratoire

Voici à quoi ressemble l'ensemble de données Hamilton .

Il y a une ligne d'enregistrement par personnage/chanson/ligne de paroles.

• Titre – fait référence au nom de la chanson.
• Speaker - fait référence au personnage qui chante une ligne donnée.
• Lignes - fait référence à la ligne particulière des paroles de la chanson.

Construire une matrice de contiguïté

Pour construire un graphe de réseau de tous les locuteurs de Hamilton , les éléments suivants doivent être définis :

• Nœuds (liste des intervenants)

• Bords (pour connecter chaque paire d'enceintes)

• Fonction d'incidence pour mapper chaque paire de sommets à une arête (avec un poids optionnel)

  
  

La fonction d'incidence que j'ai choisie est le nombre de chansons dans lesquelles chaque paire d'enceintes apparaît ensemble . Mon hypothèse est que plus il y a de chansons dans lesquelles deux personnages apparaissent ensemble, plus leur relation est forte.

Weight {speaker,x, speaker,y} = #songs that feature both speaker,x and speaker,y

En utilisant le dplyr de R, je peux transformer mon ensemble de données d'origine en une entité **{src, dest, weight}** , puis le convertir en une matrice de contiguïté. Je peux ensuite utiliser graph.adjacency dans le package igraph de R pour créer un « objet graphique » à partir de cette matrice de contiguïté, que je peux ensuite utiliser pour le traçage et d'autres analyses.

Visualiser le tracé du réseau

Le graph_obj peut être visualisé à l'aide de la fonction plot.igraph . Étant donné que cette fonction propose de nombreuses mises en page personnalisées, je commence par restituer le même graphique en utilisant la mise en page « étoile ».

Le résultat est techniquement un tracé de réseau. Mais est-il possible de faire encore mieux ? Le graphique ci-dessus semble suggérer que tous les sommets et arêtes ont la même importance – mais cela mine l’intérêt même de la visualisation d’un réseau social. Certains personnages sont en effet plus « significatifs » et certains locuteurs entretiennent des relations plus fortes que d’autres.

Comment ce graphique peut-il refléter cela ?

C'est là que le poids des bords et le degré du sommet entrent en jeu. Je commence par jouer avec les paramètres de la fonction plot.igraph pour créer edge.width (c'est-à-dire l'épaisseur du bord dans le tracé) par rapport au poids, et vertex.label.cex (c'est-à-dire la taille de la police du tracé). sommets) par rapport au degré.

Beaucoup mieux ! Les personnages avec un degré plus élevé sont visuellement plus grands, et la distinction entre les relations fortes et faibles ressort également de l'obscurité des lignes. Cette itération est beaucoup plus intuitive et permet au spectateur de saisir immédiatement les relations entre les personnages. Il est également approprié que King George soit un nœud solitaire, étant donné que ses chansons sont toujours des monologues (très drôles).

Vous pouvez également utiliser la bibliothèque visNetwork dans R pour créer un graphique de réseau interactif . La bibliothèque permet de zoomer et dézoomer sur plusieurs parties du graphique (particulièrement utile avec un graphique particulièrement grand) et prend en charge Shiny.

Mesures de centralité

La centralité est un concept clé de la théorie des graphes pour identifier la signification des nœuds :

• Degré de centralité : Il s'agit d'une mesure du nombre d'arêtes connectées à chaque nœud.

• Centralité propre : cela représente une mesure du degré de « bien connecté » d'un nœud, du nombre de liens que les connexions partagent, et ainsi de suite à travers le réseau. Il identifie les nœuds ayant une influence sur l’ensemble du réseau, et pas seulement ceux qui y sont directement connectés.

• Centralité intermédiaire : il s'agit littéralement de la mesure dans laquelle un nœud donné se situe entre d'autres nœuds et agit comme un « pont » entre divers groupes de réseaux. C'est une mesure de « l'influence » de chacun des sommets sur le reste du réseau.

  
  

Je peux utiliser les fonctions Degree(), Betweenness() et eigen_centrality() d'igraph pour obtenir la centralité du graphe généré :

Il semble qu'Aaron Burr ait la centralité intermédiaire la plus élevée (le « pont ») dans notre graphique, tandis que Hamilton a la centralité de vecteur propre la plus élevée (l'« influenceur »). Faites-en ce que vous voulez.

Conclusion

Les applications métiers des graphes de réseau sont nombreuses :

• Les sites de réseaux sociaux utilisent des graphiques de réseau pour créer des communautés d'utilisateurs similaires et proposer des recommandations ciblées. Une implémentation rudimentaire de l'algorithme derrière une fonctionnalité « amis suggérés » pourrait ressembler à ceci : « Neuf amis immédiats d'Alice sur dix sont également amis avec Bob -> recommandez Bob comme ami potentiel pour Alice. »

  
  

• Les applications qui cartographient la distance la plus courte d'un endroit X à un endroit Y (telles que les cartes, les services de covoiturage, la chaîne d'approvisionnement et la logistique des camions de livraison, etc.) utilisent probablement des variantes des algorithmes du « chemin le plus court », communément appelés en informatique le problème du voyageur de commerce .

  
  

• La théorie des réseaux est un élément crucial du traitement lexical et sémantique au sein du traitement du langage naturel (NLP), à son tour utilisé par les chatbots et les assistants virtuels comme Alexa, Cortana, Siri et même Jeopardy ! , un jeu de mots et de jeux de mots qui est loin d’être simple.

  
  

• Les jeux de société comme Six Degrees of Kevin Bacon utilisent des graphiques de réseau.

  
  

• En épidémiologie, les mesures de centralité peuvent être utilisées pour identifier les origines des pandémies ou des événements « super-propagateurs ».

  
  

• Si vous y réfléchissez bien, Internet n’est qu’un réseau gargantuesque de différents sites Web. Les moteurs de recherche utilisent des mesures de graphes de connaissances pour renvoyer les pages les plus pertinentes pour une requête de recherche particulière.

  
  

Aussi amusants soient-ils, il est important de noter que les graphes de réseau ne sont pas sans inconvénients lorsqu’ils sont utilisés en production. Par exemple, ils peuvent être gourmands en ressources. Comme c’est le cas pour toute opération matricielle, l’évolutivité et les performances en pâtissent parfois. Il existe également un problème de « démarrage à froid » : si votre ensemble de données est trop clairsemé ou s'il n'y a pas vraiment beaucoup de relations entre les entités, un graphe de réseau n'est pas une solution efficace. Cependant, utilisés correctement et dans le bon contexte, ils peuvent être précieux pour les entreprises.