Python - Grafik Verileri

CSGraph'ın açılımı Compressed Sparse Graph, seyrek matris gösterimlerine dayalı Hızlı grafik algoritmalarına odaklanan.

Grafik Gösterimleri

Başlangıç olarak, seyrek grafiğin ne olduğunu ve grafik gösterimlerine nasıl yardımcı olduğunu anlayalım.

Seyrek grafik tam olarak nedir?

Grafik, aralarında bağlantıları olan düğümlerin bir koleksiyonudur. Grafikler neredeyse her şeyi temsil edebilir - her düğümün bir kişi olduğu ve tanıdıklarla bağlantılı olduğu sosyal ağ bağlantıları; her düğümün bir piksel olduğu ve komşu piksellere bağlandığı görüntüler; her bir düğümün en yakın komşularına ve neredeyse hayal edebileceğiniz her şeye bağlı olduğu yüksek boyutlu bir dağılımdaki noktalar.

Grafik verilerini göstermenin çok etkili bir yolu, seyrek bir matristedir: buna G diyelim. G matrisi, N x N boyutundadır ve G [i, j], 'i' düğümü ile düğüm arasındaki bağlantının değerini verir. 'j'. Seyrek bir grafik çoğunlukla sıfır içerir - yani, çoğu düğümün yalnızca birkaç bağlantısı vardır. Bu özelliğin çoğu ilgi durumunda doğru olduğu ortaya çıkar.

Seyrek grafik alt modülünün oluşturulması, aşağıdakileri içeren scikit-learn'de kullanılan çeşitli algoritmalar tarafından motive edildi -

Isomap - Bir grafikteki en kısa yolları bulmayı gerektiren çok katlı bir öğrenme algoritması.
Hierarchical clustering - Minimum yayılma ağacına dayalı bir kümeleme algoritması.
Spectral Decomposition - Seyrek grafik laplacians tabanlı bir projeksiyon algoritması.

Somut bir örnek olarak, aşağıdaki yönsüz grafiği temsil etmek istediğimizi hayal edin -

Bu grafikte, düğüm 0 ve 1'in 2 ağırlık kenarıyla ve 0 ve 2 düğümlerinin 1 ağırlık kenarıyla bağlandığı üç düğüm vardır. Aşağıdaki örnekte gösterildiği gibi, yoğun, maskelenmiş ve seyrek gösterimleri oluşturabiliriz. , yönsüz bir grafiğin simetrik bir matrisle temsil edildiğini akılda tutarak.

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

Yukarıdaki program aşağıdaki çıktıyı üretecektir.

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

Bu, 0 ve 2 düğümlerinin sıfır ağırlıklı bir kenarla bağlanması dışında önceki grafikle aynıdır. Bu durumda, yukarıdaki yoğun gösterim belirsizliklere yol açar - sıfır anlamlı bir değer ise kenar olmayanlar nasıl temsil edilebilir. Bu durumda, belirsizliği ortadan kaldırmak için ya maskeli ya da seyrek bir temsil kullanılmalıdır.

Aşağıdaki örneği ele alalım.

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

Yukarıdaki program aşağıdaki çıktıyı üretecektir.

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