Python - dane wykresu

CSGraph oznacza Compressed Sparse Graph, który koncentruje się na algorytmach szybkiego grafu opartych na rzadkich reprezentacjach macierzowych.

Reprezentacje wykresów

Na początek pozwól nam zrozumieć, czym jest rzadki wykres i jak pomaga w reprezentacji wykresu.

Czym dokładnie jest rzadki wykres?

Graf to po prostu zbiór węzłów, które mają między sobą połączenia. Wykresy mogą reprezentować prawie wszystko - połączenia w sieciach społecznościowych, gdzie każdy węzeł jest osobą i jest połączony ze znajomymi; obrazy, w których każdy węzeł jest pikselem i jest połączony z sąsiednimi pikselami; punkty w wielowymiarowej dystrybucji, gdzie każdy węzeł jest połączony z najbliższymi sąsiadami i praktycznie wszystkim innym, co można sobie wyobrazić.

Jednym z bardzo skutecznych sposobów przedstawiania danych wykresu jest rzadka macierz: nazwijmy ją G. Macierz G ma rozmiar N x N, a G [i, j] podaje wartość połączenia między węzłem „i” a węzłem 'jot'. Rzadki wykres zawiera głównie zera - to znaczy większość węzłów ma tylko kilka połączeń. Ta właściwość okazuje się być prawdziwa w większości interesujących nas przypadków.

Stworzenie podmodułu rzadkiego wykresu było motywowane kilkoma algorytmami używanymi w scikit-learning, które obejmowały:

Isomap - Wielokrotny algorytm uczenia się, który wymaga znalezienia najkrótszych ścieżek na wykresie.
Hierarchical clustering - Algorytm grupowania oparty na minimalnym drzewie rozpinającym.
Spectral Decomposition - Algorytm projekcji oparty na rzadkich grafach laplaców.

Jako konkretny przykład wyobraźmy sobie, że chcielibyśmy przedstawić następujący nieukierunkowany wykres -

Ten wykres ma trzy węzły, gdzie węzły 0 i 1 są połączone krawędzią o wadze 2, a węzły 0 i 2 są połączone krawędzią o wadze 1. Możemy skonstruować gęste, zamaskowane i rzadkie reprezentacje, jak pokazano w poniższym przykładzie , pamiętając, że niekierowany graf jest reprezentowany przez symetryczną macierz.

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

Powyższy program wygeneruje następujące dane wyjściowe.

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

Jest to identyczne z poprzednim wykresem, z wyjątkiem tego, że węzły 0 i 2 są połączone krawędzią o zerowej wadze. W tym przypadku gęsta reprezentacja powyżej prowadzi do niejednoznaczności - jak można przedstawić nie-krawędzie, jeśli zero jest znaczącą wartością. W takim przypadku należy użyć reprezentacji zamaskowanej lub rzadkiej, aby wyeliminować niejednoznaczność.

Rozważmy następujący przykład.

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

Powyższy program wygeneruje następujące dane wyjściowe.

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