Graphique Data Science avec Python/NetworkX

Nous sommes inondés de données. Les bases de données et les feuilles de calcul en constante expansion regorgent d'informations commerciales cachées. Comment pouvons-nous analyser des données et en tirer des conclusions alors qu'il y en a tellement ? Les graphiques (réseaux, pas les graphiques à barres) offrent une approche élégante.

Nous utilisons souvent des tableaux pour représenter les informations de manière générique. Mais les graphiques utilisent une structure de données spécialisée : au lieu d'une ligne de tableau, un nœud représente un élément. Une arête relie deux nœuds pour indiquer leur relation.

Cette structure de données graphique nous permet d'observer les données sous des angles uniques, c'est pourquoi la science des données graphiques est utilisée dans tous les domaines, de la biologie moléculaire aux sciences sociales :

Alors, comment les développeurs peuvent-ils tirer parti de la science des données graphiques ? Passons au langage de programmation de science des données le plus utilisé : Python.

Premiers pas avec les graphes de la "théorie des graphes" en Python

Les développeurs Python disposent de plusieurs bibliothèques de données graphiques, telles que NetworkX, igraph, SNAP et graph-tool. Mis à part les avantages et les inconvénients, ils ont des interfaces très similaires pour la gestion et le traitement des structures de données de graphe Python.

Nous utiliserons la bibliothèque populaire NetworkX. Il est simple à installer et à utiliser et prend en charge l'algorithme de détection de communauté que nous utiliserons.

La création d'un nouveau graphique avec NetworkX est simple :

 import networkx as nx G = nx.Graph()

Mais G n'est pas encore vraiment un graphe, étant dépourvu de nœuds et d'arêtes.

Comment ajouter des nœuds à un graphique

Nous pouvons ajouter un nœud au réseau en chaînant sur la valeur de retour de Graph() avec .add_node() (ou .add_nodes_from() pour plusieurs nœuds dans une liste). Nous pouvons également ajouter des caractéristiques ou des attributs arbitraires aux nœuds en passant un dictionnaire en paramètre, comme nous le montrons avec le node 4 et le node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Cela affichera :

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Mais sans bords entre les nœuds, ils sont isolés et l'ensemble de données n'est pas mieux qu'un simple tableau.

Comment ajouter des arêtes à un graphique

Semblable à la technique pour les nœuds, nous pouvons utiliser .add_edge() avec les noms de deux nœuds comme paramètres (ou .add_edges_from() pour plusieurs arêtes dans une liste), et éventuellement inclure un dictionnaire d'attributs :

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

La bibliothèque NetworkX prend en charge des graphiques comme ceux-ci, où chaque bord peut avoir un poids. Par exemple, dans un graphe de réseau social où les nœuds sont les utilisateurs et les arêtes sont les interactions, le poids peut indiquer le nombre d'interactions qui se produisent entre une paire d'utilisateurs donnée, une mesure très pertinente.

NetworkX répertorie tous les bords lors de l'utilisation G.edges , mais il n'inclut pas leurs attributs. Si nous voulons des attributs de bord, nous pouvons utiliser G[node_name] pour obtenir tout ce qui est connecté à un nœud ou G[node_name][connected_node_name] pour obtenir les attributs d'un bord particulier :

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Cela affichera :

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Mais lire notre premier graphique de cette façon n'est pas pratique. Heureusement, il y a une bien meilleure représentation.

Comment générer des images à partir de graphiques (et de graphiques pondérés)

Visualiser un graphe est essentiel : Il permet de voir rapidement et clairement les relations entre les nœuds et la structure du réseau.

Un appel rapide à nx.draw(G) suffit :

Rendons les arêtes plus lourdes plus épaisses en conséquence via notre appel nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Nous avons fourni une épaisseur par défaut pour les bords sans poids, comme le montre le résultat :

Nos méthodes et algorithmes de graphes sont sur le point de devenir plus complexes, la prochaine étape consiste donc à utiliser un ensemble de données mieux connu.

Représentation graphique de la science des données à l'aide des données du film Star Wars : Épisode IV

Pour faciliter l'interprétation et la compréhension de nos résultats, nous utiliserons cet ensemble de données. Les nœuds représentent des personnages importants et les bords (qui ne sont pas pondérés ici) signifient la co-apparition dans une scène.

Remarque : L'ensemble de données provient de Gabasova, E. (2016). Réseau social Star Wars. DOI : https://doi.org/10.5281/zenodo.1411479.

Tout d'abord, nous allons visualiser les données avec nx.draw(G_starWars, with_labels = True) :

Les personnages qui apparaissent généralement ensemble, comme R2-D2 et C-3PO, semblent étroitement liés. En revanche, on peut voir que Dark Vador ne partage pas de scènes avec Owen.

Dispositions de visualisation Python NetworkX

Pourquoi chaque nœud est-il situé là où il se trouve dans le graphique précédent ?

C'est le résultat de l'algorithme par défaut spring_layout . Il simule la force d'un ressort, attirant les nœuds connectés et repoussant ceux qui sont déconnectés. Cela aide à mettre en évidence les nœuds bien connectés, qui se retrouvent au centre.

NetworkX a d'autres dispositions qui utilisent différents critères pour positionner les nœuds, comme circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

Le résultat:

Cette disposition est neutre dans le sens où l'emplacement d'un nœud ne dépend pas de son importance - tous les nœuds sont représentés de la même manière. (La disposition circulaire pourrait également aider à visualiser des composants connectés séparés - des sous-graphes ayant un chemin entre deux nœuds - mais ici, le graphique entier est un gros composant connecté.)

Les deux mises en page que nous avons vues présentent un certain encombrement visuel car les bords sont libres de traverser d'autres bords. Mais Kamada-Kawai, un autre algorithme dirigé par la force comme spring_layout , positionne les nœuds de manière à minimiser l'énergie du système.

Cela réduit le franchissement des bords, mais à un prix : c'est plus lent que les autres dispositions et donc pas fortement recommandé pour les graphiques avec de nombreux nœuds.

Celui-ci a une fonction de tirage spécialisée :

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Cela donne plutôt cette forme :

Sans aucune intervention particulière, l'algorithme place les personnages principaux (comme Luke, Leia et C-3PO) au centre, et les personnages moins importants (comme Camie et le général Dodonna) à la frontière.

Visualiser le graphique avec une mise en page spécifique peut nous donner des résultats qualitatifs intéressants. Pourtant, les résultats quantitatifs sont un élément essentiel de toute analyse de science des données, nous devrons donc définir certaines métriques.

Analyse des nœuds : Degré et PageRank

Maintenant que nous pouvons visualiser clairement notre réseau, il peut nous être intéressant de caractériser les nœuds. Il existe plusieurs métriques qui décrivent les caractéristiques des nœuds et, dans notre exemple, des caractères.

Une métrique de base pour un nœud est son degré : combien d'arêtes il a. Le degré du nœud d'un personnage de Star Wars mesure le nombre d'autres personnages avec lesquels il a partagé une scène.

La fonction degree() permet de calculer le degré d'un caractère ou de tout le réseau :

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

La sortie des deux commandes :

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

Le tri des nœuds du plus haut au plus bas selon le degré peut être fait avec une seule ligne de code :

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

Le résultat:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

N'étant qu'un total, le degré ne prend pas en compte les détails des arêtes individuelles. Un bord donné se connecte-t-il à un nœud autrement isolé ou à un nœud connecté à l'ensemble du réseau ? L'algorithme PageRank de Google agrège ces informations pour évaluer l'"importance" d'un nœud dans un réseau.

La métrique PageRank peut être interprétée comme un agent se déplaçant aléatoirement d'un nœud à un autre. Les nœuds mieux connectés ont plus de chemins qui les traversent, de sorte que l'agent aura tendance à les visiter plus souvent.

Ces nœuds auront un PageRank plus élevé, que nous pouvons calculer avec la bibliothèque NetworkX :

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Cela imprime le rang de Luke et nos personnages triés par rang :

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen est le personnage avec le PageRank le plus élevé, dépassant Luke, qui avait le plus haut degré. L'analyse : Bien qu'Owen ne soit pas le personnage qui partage le plus de scènes avec d'autres personnages, c'est un personnage qui partage des scènes avec de nombreux personnages importants tels que Luke lui-même, R2-D2 et C-3PO.

En revanche, C-3PO, le personnage avec le troisième degré le plus élevé, est celui avec le PageRank le plus bas. Bien que C-3PO ait de nombreuses relations, beaucoup d'entre elles sont avec des personnages sans importance.

Le point à retenir : l'utilisation de plusieurs métriques peut donner un aperçu plus approfondi des différentes caractéristiques des nœuds d'un graphique.

Algorithmes de détection de communauté

Lors de l'analyse d'un réseau, il peut être important de séparer les communautés : des groupes de nœuds fortement connectés les uns aux autres mais peu connectés avec des nœuds extérieurs à leur communauté.

Il existe plusieurs algorithmes pour cela. La plupart d'entre eux se trouvent dans des algorithmes d'apprentissage automatique non supervisés car ils attribuent une étiquette aux nœuds sans qu'il soit nécessaire qu'ils aient été étiquetés auparavant.

L'une des plus connues est la propagation d'étiquettes . Dans celui-ci, chaque nœud commence par une étiquette unique, dans une communauté d'un. Les étiquettes des nœuds sont mises à jour itérativement en fonction de la majorité des étiquettes des nœuds voisins.

Les étiquettes se diffusent à travers le réseau jusqu'à ce que tous les nœuds partagent une étiquette avec la plupart de leurs voisins. Des groupes de nœuds étroitement connectés les uns aux autres finissent par avoir la même étiquette.

Avec la bibliothèque NetworkX, l'exécution de cet algorithme ne prend que trois lignes de Python :

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

Le résultat:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

Dans cette liste d'ensembles, chaque ensemble représente une communauté. Les lecteurs familiers avec le film remarqueront que l'algorithme a réussi à séparer parfaitement les "bons" des "méchants", en différenciant les personnages de manière significative sans utiliser de véritable étiquette (communautaire) ou de métadonnées.

Insights intelligents à l'aide de la science des données graphiques en Python

Nous avons vu que commencer avec les outils de science des données graphiques est plus simple qu'il n'y paraît. Une fois que nous avons représenté les données sous forme de graphique à l'aide de la bibliothèque NetworkX en Python, quelques courtes lignes de code peuvent être éclairantes. Nous pouvons visualiser notre ensemble de données, mesurer et comparer les caractéristiques des nœuds et regrouper les nœuds de manière judicieuse via des algorithmes de détection de communauté.

Avoir la capacité d'extraire des conclusions et des informations d'un réseau à l'aide de Python permet aux développeurs de s'intégrer aux outils et à la méthodologie couramment trouvés dans les pipelines de services de science des données. Des moteurs de recherche à la planification des vols en passant par l'ingénierie électrique, ces méthodes s'appliquent facilement à un large éventail de contextes.

Lecture recommandée sur la science des données graphiques

Algorithmes de détection de communauté
Zhao Yang, René Algesheimer et Claudio Tessone. "Une analyse comparative des algorithmes de détection communautaire sur les réseaux artificiels." Rapports scientifiques, 6, no. 30750 (2016).

Apprentissage en profondeur des graphiques
Thomas Kipf. "Réseaux convolutifs de graphes." 30 septembre 2016.

Applications de la science des données graphiques
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein et Pablo Balenzuela. "Prédire les individus changeants à l'aide de l'exploration de texte et de l'apprentissage automatique des graphiques sur Twitter." (24 août 2020) : arXiv:2008.10749 [cs.SI].

Cohen, Elior. "Meetup PyData Tel-Aviv : Node2vec." Youtube. 22 novembre 2018. Vidéo, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.