Python圖資料

CSGraph代表壓縮稀疏圖，它著重於基於稀疏矩陣表示的快速圖演算法。

圖的表示

首先，讓我們了解一個稀疏圖是什麼以及它在圖表示中的作用。

什麼是稀疏圖？

圖形只是節點的集合，它們之間有連結。 圖表幾乎可以代表任何事物 - 社群網路連線，每個節點都是一個人，並且與熟人相連; 影象，其中每個節點是畫素並連線到相鄰畫素; 指向高維分布，其中每個節點都連線到最近的鄰居，並且幾乎可以想象其他任何事物。

• Isomap - 流形學習演算法，需要在圖中找到最短路徑。
• 分層聚類 - 基於最小生成樹的聚類演算法。
• 譜分解 - 基於稀疏圖拉普拉斯運算元的投影演算法。

一個具體的例子，假設想要表示無向圖，如下所示 -

該圖有三個節點，其中節點0和1通過權重2的邊連線，節點0和2通過權重1的邊連線。可以構造如下例所示的稠密，掩碼和稀疏表示 請記住，無向圖由對稱矩陣表示。

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)

上述程式將生成以下輸出。

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

這與前面的圖相同，只是節點0和2通過零權重的邊連線。 在這種情況下，上面的密集表示會導致含糊不清 - 如果零是一個有意義的值，那麼如何表示非邊緣。 在這種情況下，必須使用蒙版或稀疏表示來消除歧義。

看看下面的例子。

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)

上述程式將生成以下輸出。

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