Python - Dati del grafico

CSGraph sta per Compressed Sparse Graph, che si concentra su algoritmi di grafi veloci basati su rappresentazioni di matrici sparse.

Rappresentazioni grafiche

Per cominciare, cerchiamo di capire cos'è un grafo sparse e come aiuta nelle rappresentazioni grafiche.

Cos'è esattamente un grafico sparse?

Un grafico è solo una raccolta di nodi, che hanno collegamenti tra di loro. I grafici possono rappresentare quasi tutto: connessioni di social network, in cui ogni nodo è una persona ed è connesso a conoscenti; immagini, dove ogni nodo è un pixel ed è connesso ai pixel vicini; punti in una distribuzione ad alta dimensione, in cui ogni nodo è connesso ai suoi vicini più vicini e praticamente qualsiasi altra cosa tu possa immaginare.

Un modo molto efficiente per rappresentare i dati del grafo è in una matrice sparsa: chiamiamola G. La matrice G è di dimensione N x N, e G [i, j] fornisce il valore della connessione tra il nodo 'i' e il nodo 'j'. Un grafo sparso contiene principalmente zeri, ovvero la maggior parte dei nodi ha solo poche connessioni. Questa proprietà risulta essere vera nella maggior parte dei casi di interesse.

La creazione del sottomodulo del grafo sparse è stata motivata da diversi algoritmi utilizzati in scikit-learn che includevano quanto segue:

• Isomap - Un algoritmo di apprendimento molteplice, che richiede di trovare i percorsi più brevi in ​​un grafico.

• Hierarchical clustering - Un algoritmo di clustering basato su uno spanning tree minimo.

• Spectral Decomposition - Un algoritmo di proiezione basato su laplaciani di grafi sparsi.

Come esempio concreto, immagina di voler rappresentare il seguente grafico non orientato:

Questo grafico ha tre nodi, dove i nodi 0 e 1 sono collegati da un bordo di peso 2, ei nodi 0 e 2 sono collegati da un bordo di peso 1. Possiamo costruire le rappresentazioni dense, mascherate e sparse come mostrato nell'esempio seguente , tenendo presente che un grafo non orientato è rappresentato da una matrice simmetrica.

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

Il programma precedente genererà il seguente output.

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

Questo è identico al grafico precedente, tranne per il fatto che i nodi 0 e 2 sono collegati da un bordo di peso zero. In questo caso, la rappresentazione densa sopra porta ad ambiguità: come possono essere rappresentati i non bordi, se zero è un valore significativo. In questo caso, è necessario utilizzare una rappresentazione mascherata o sparsa per eliminare l'ambiguità.

Consideriamo il seguente esempio.

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

Il programma precedente genererà il seguente output.

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