Il y a quelques années, je lisais de façon excessive les livres 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 pour me souvenir des intrigues. J'avais besoin d'une carte mentale – il y avait sûrement une meilleure façon de ces personnages ? de Game of Thrones A Song of Ice and Fire visualiser Les bases L'image ci-dessous est 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 : un exemple de graphique de réseau de Wikipédia 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 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 de la relation entre les sommets. Dans cet exemple, la fonction d'incidence pondérée pourrait ressembler à ceci : deux force 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 paroles que vous pouvez simplement télécharger et commencer à représenter graphiquement. ensemble de données claires de de Hamilton facilement disponibles sur Kaggle Analyse exploratoire Voici à quoi ressemble l'ensemble de données . Hamilton Il y a une ligne d'enregistrement par personnage/chanson/ligne de paroles. – fait référence au nom de la chanson. Titre - fait référence au personnage qui chante une ligne donnée. Speaker - fait référence à la ligne particulière des paroles de la chanson. Lignes Construire une matrice de contiguïté Pour construire un graphe de réseau de tous les locuteurs , les éléments suivants doivent être définis : de Hamilton 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 . Mon hypothèse est que plus il y a de chansons dans lesquelles deux personnages apparaissent ensemble, plus leur relation est forte. nombre de chansons dans lesquelles chaque paire d'enceintes apparaît ensemble 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é , puis le convertir en une matrice de contiguïté. Je peux ensuite utiliser graph.adjacency dans 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. **{src, dest, weight}** le package igraph de R Visualiser le tracé du réseau Le graph_obj peut être visualisé à l'aide de la fonction . É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 ». plot.igraph 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 et entrent en jeu. Je commence par jouer avec les paramètres de la fonction pour créer (c'est-à-dire l'épaisseur du bord dans le tracé) par rapport au poids, et (c'est-à-dire la taille de la police du tracé). sommets) par rapport au degré. le poids des bords le degré du sommet plot.igraph edge.width vertex.label.cex 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 dans R pour créer un graphique de réseau . 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. visNetwork interactif Mesures de centralité est un concept clé de la théorie des graphes pour identifier la signification des nœuds : La centralité : Il s'agit d'une mesure du nombre d'arêtes connectées à chaque nœud. Degré de centralité : 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é propre il s'agit littéralement de la mesure dans laquelle un nœud donné se situe 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. Centralité intermédiaire : entre 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 la plus élevée (le « pont ») dans notre graphique, tandis que Hamilton a la la plus élevée (l'« influenceur »). Faites-en ce que vous voulez. centralité intermédiaire centralité de vecteur propre 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 , un jeu de mots et de jeux de mots qui est loin d’être simple. Jeopardy ! Les jeux de société comme utilisent des graphiques de réseau. Six Degrees of Kevin Bacon 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 pour renvoyer les pages les plus pertinentes pour une requête de recherche particulière. de graphes de connaissances 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. • Code : https://github.com/iswaryam/hamilton/ Crédit de l'ensemble de données : https://www.kaggle.com/lbalter/hamilton-lyrics# Si vous êtes un Potterhead, consultez mon GitHub – j'ai également représenté graphiquement les personnages de avec une méthode similaire. Harry Potter
