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