Python圖數據

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

圖的表示

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

什麼是稀疏圖?

圖形只是節點的集合,它們之間有鏈接。 圖表幾乎可以代表任何事物 - 社交網絡連接,每個節點都是一個人,並且與熟人相連; 圖像,其中每個節點是像素並連接到相鄰像素; 指向高維分佈,其中每個節點都連接到最近的鄰居,並且幾乎可以想象其他任何事物。

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

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

Python圖數據

該圖有三個節點,其中節點0和1通過權重2的邊連接,節點02通過權重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])

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

看看下面的例子。

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