Python - Données graphiques

CSGraph signifie Compressed Sparse Graph, qui se concentre sur les algorithmes de graphe rapide basés sur des représentations matricielles éparses.

Représentations graphiques

Pour commencer, comprenons ce qu'est un graphe clairsemé et comment il aide dans les représentations graphiques.

Qu'est-ce qu'un graphique fragmenté exactement?

Un graphe est juste une collection de nœuds, qui ont des liens entre eux. Les graphiques peuvent représenter presque tout: les connexions aux réseaux sociaux, où chaque nœud est une personne et est connecté à des connaissances; des images, où chaque nœud est un pixel et est connecté à des pixels voisins; points dans une distribution à haute dimension, où chaque nœud est connecté à ses voisins les plus proches et à pratiquement tout ce que vous pouvez imaginer.

Une façon très efficace de représenter les données d'un graphe est dans une matrice creuse: appelons-la G. La matrice G est de taille N x N, et G [i, j] donne la valeur de la connexion entre le nœud 'i' et le nœud «j». Un graphe fragmenté contient principalement des zéros, c'est-à-dire que la plupart des nœuds n'ont que quelques connexions. Cette propriété s'avère être vraie dans la plupart des cas d'intérêt.

La création du sous-module de graphe clairsemé a été motivée par plusieurs algorithmes utilisés dans scikit-learn qui comprenaient les éléments suivants:

Isomap - Un algorithme d'apprentissage multiple, qui nécessite de trouver les chemins les plus courts dans un graphique.
Hierarchical clustering - Un algorithme de clustering basé sur un Spanning Tree minimum.
Spectral Decomposition - Un algorithme de projection basé sur des laplaciens à graphes clairsemés.

À titre d'exemple concret, imaginons que nous aimerions représenter le graphe non orienté suivant -

Ce graphe a trois nœuds, où les nœuds 0 et 1 sont reliés par une arête de poids 2, et les nœuds 0 et 2 sont reliés par une arête de poids 1. Nous pouvons construire les représentations denses, masquées et éparses comme le montre l'exemple suivant , en gardant à l'esprit qu'un graphe non orienté est représenté par une matrice symétrique.

G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])
                     
G_masked = np.ma.masked_values(G_dense, 0)
from scipy.sparse import csr_matrix

G_sparse = csr_matrix(G_dense)
print G_sparse.data

Le programme ci-dessus générera la sortie suivante.

array([2, 1, 2, 1])

Ceci est identique au graphique précédent, sauf que les nœuds 0 et 2 sont reliés par une arête de poids nul. Dans ce cas, la représentation dense ci-dessus conduit à des ambiguïtés - comment les non-arêtes peuvent être représentées, si zéro est une valeur significative. Dans ce cas, une représentation masquée ou clairsemée doit être utilisée pour éliminer l'ambiguïté.

Prenons l'exemple suivant.

from scipy.sparse.csgraph import csgraph_from_dense
G2_data = np.array
([
   [np.inf, 2, 0 ],
   [2, np.inf, np.inf],
   [0, np.inf, np.inf]
])
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print G2_sparse.data

Le programme ci-dessus générera la sortie suivante.

array([ 2., 0., 2., 0.])