Python - dados gráficos

CSGraph significa Compressed Sparse Graph, que se concentra em algoritmos de gráfico rápido com base em representações de matriz esparsa.

Representações Gráficas

Para começar, vamos entender o que é um gráfico esparso e como ele ajuda nas representações de gráfico.

O que exatamente é um gráfico esparso?

Um gráfico é apenas uma coleção de nós, que possuem links entre eles. Os gráficos podem representar quase tudo - conexões de redes sociais, em que cada nó é uma pessoa e está conectado a conhecidos; imagens, onde cada nó é um pixel e está conectado a pixels vizinhos; pontos em uma distribuição de alta dimensão, onde cada nó está conectado aos seus vizinhos mais próximos e praticamente qualquer outra coisa que você possa imaginar.

Uma maneira muito eficiente de representar os dados do gráfico é em uma matriz esparsa: vamos chamá-la de G. A matriz G é de tamanho N x N, e G [i, j] dá o valor da conexão entre o nó 'i' e o nó 'j'. Um gráfico esparso contém principalmente zeros - ou seja, a maioria dos nós tem apenas algumas conexões. Essa propriedade acaba sendo verdadeira na maioria dos casos de interesse.

A criação do submódulo de gráfico esparso foi motivada por vários algoritmos usados no scikit-learn que incluiu o seguinte -

Isomap - Um algoritmo de aprendizado múltiplo, que requer encontrar os caminhos mais curtos em um gráfico.
Hierarchical clustering - Um algoritmo de agrupamento baseado em uma árvore de abrangência mínima.
Spectral Decomposition - Um algoritmo de projeção baseado em laplacianos de grafos esparsos.

Como um exemplo concreto, imagine que gostaríamos de representar o seguinte gráfico não direcionado -

Este gráfico tem três nós, onde o nó 0 e 1 são conectados por uma aresta de peso 2, e os nós 0 e 2 são conectados por uma aresta de peso 1. Podemos construir as representações densa, mascarada e esparsa como mostrado no exemplo a seguir , lembrando que um gráfico não direcionado é representado por uma matriz simétrica.

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

O programa acima irá gerar a seguinte saída.

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

Ele é idêntico ao gráfico anterior, exceto os nós 0 e 2 são conectados por uma aresta de peso zero. Nesse caso, a representação densa acima leva a ambigüidades - como as não arestas podem ser representadas, se zero é um valor significativo. Nesse caso, uma representação mascarada ou esparsa deve ser usada para eliminar a ambigüidade.

Vamos considerar o seguinte exemplo.

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

O programa acima irá gerar a seguinte saída.

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