Python - Data Grafik

CSGraph adalah singkatan dari Compressed Sparse Graph, yang berfokus pada algoritma grafik Cepat berdasarkan representasi matriks renggang.

Representasi Grafik

Untuk memulainya, mari kita pahami apa itu grafik renggang dan bagaimana grafik itu membantu dalam representasi grafik.

Apa sebenarnya grafik renggang itu?

Grafik hanyalah kumpulan node, yang memiliki hubungan di antara mereka. Grafik dapat mewakili hampir semua hal - koneksi jaringan sosial, di mana setiap node adalah orang dan terhubung ke kenalan; gambar, di mana setiap node adalah piksel dan terhubung ke piksel tetangga; titik dalam distribusi berdimensi tinggi, di mana setiap simpul terhubung ke tetangga terdekatnya dan praktis apa pun yang dapat Anda bayangkan.

Salah satu cara yang sangat efisien untuk merepresentasikan data grafik adalah dalam matriks renggang: sebut saja G. Matriks G berukuran N x N, dan G [i, j] memberikan nilai hubungan antara node 'i' dan node 'j'. Grafik renggang sebagian besar berisi nol - artinya, sebagian besar node hanya memiliki sedikit koneksi. Properti ini ternyata benar dalam banyak kasus yang menarik.

Pembuatan submodul grafik renggang dimotivasi oleh beberapa algoritme yang digunakan dalam scikit-learn yang meliputi:

Isomap - Algoritma pembelajaran berjenis, yang membutuhkan pencarian jalur terpendek dalam grafik.
Hierarchical clustering - Algoritme pengelompokan berdasarkan pohon rentang minimum.
Spectral Decomposition - Algoritma proyeksi berdasarkan grafik laplacians jarang.

Sebagai contoh konkret, bayangkan kita ingin merepresentasikan graf tak berarah berikut -

Grafik ini memiliki tiga node, di mana node 0 dan 1 dihubungkan oleh tepi berbobot 2, dan node 0 dan 2 dihubungkan oleh tepi bobot 1. Kita dapat membuat representasi padat, bertopeng, dan jarang seperti yang ditunjukkan pada contoh berikut , perlu diingat bahwa grafik yang tidak berarah direpresentasikan oleh matriks simetris.

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

Program di atas akan menghasilkan keluaran sebagai berikut.

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

Ini identik dengan grafik sebelumnya, kecuali node 0 dan 2 dihubungkan oleh tepi tanpa bobot. Dalam kasus ini, representasi padat di atas mengarah pada ambiguitas - bagaimana non-edge dapat direpresentasikan, jika nol adalah nilai yang berarti. Dalam hal ini, representasi bertopeng atau jarang harus digunakan untuk menghilangkan ambiguitas.

Mari kita perhatikan contoh berikut.

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

Program di atas akan menghasilkan keluaran sebagai berikut.

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