Python - 圖資料

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

圖表示

首先，讓我們瞭解什麼是稀疏圖以及它如何幫助圖表示。

什麼是稀疏圖？

圖只是一組節點，節點之間有連結。圖幾乎可以表示任何東西——社交網路連線，其中每個節點都是一個人並與其熟人連線；影像，其中每個節點都是一個畫素並與其相鄰畫素連線；高維分佈中的點，其中每個節點都與其最近鄰連線，以及你能想象到的幾乎任何其他東西。

表示圖資料的一種非常有效的方法是使用稀疏矩陣：我們稱之為 G。矩陣 G 的大小為 N x N，而 G[i, j] 給出節點“i”和節點“j”之間連線的值。稀疏圖主要包含零——也就是說，大多數節點只有很少的連線。事實證明，在大多數感興趣的情況下，此屬性都是正確的。

稀疏圖子模組的建立受到 scikit-learn 中使用的幾種演算法的啟發，這些演算法包括以下內容：

• **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.])