Python - Dữ liệu đồ thị

CSGraph là viết tắt của Compressed Sparse Graph, trong đó tập trung vào các thuật toán đồ thị nhanh dựa trên biểu diễn ma trận thưa thớt.

Biểu diễn đồ thị

Để bắt đầu, chúng ta hãy hiểu biểu đồ thưa thớt là gì và nó giúp ích như thế nào trong việc biểu diễn đồ thị.

Chính xác thì đồ thị thưa thớt là gì?

Đồ thị chỉ là một tập hợp các nút, có các liên kết giữa chúng. Đồ thị có thể đại diện cho hầu hết mọi thứ - kết nối mạng xã hội, trong đó mỗi nút là một người và được kết nối với những người quen; hình ảnh, trong đó mỗi nút là một pixel và được kết nối với các pixel lân cận; các điểm trong phân phối chiều cao, nơi mỗi nút được kết nối với các nút lân cận gần nhất và thực tế là bất kỳ thứ gì khác mà bạn có thể tưởng tượng.

Một cách rất hiệu quả để biểu diễn dữ liệu đồ thị là trong một ma trận thưa thớt: chúng ta hãy gọi nó là G. Ma trận G có kích thước N x N và G [i, j] cung cấp giá trị của kết nối giữa nút 'i' và nút 'j'. Một biểu đồ thưa thớt chứa hầu hết các số không - tức là hầu hết các nút chỉ có một vài kết nối. Tính chất này hóa ra đúng trong hầu hết các trường hợp quan tâm.

Việc tạo ra mô-đun con biểu đồ thưa thớt được thúc đẩy bởi một số thuật toán được sử dụng trong scikit-learning bao gồm những điều sau:

Isomap - Một thuật toán học đa tạp, yêu cầu tìm các đường đi ngắn nhất trong đồ thị.
Hierarchical clustering - Một thuật toán phân cụm dựa trên cây khung tối thiểu.
Spectral Decomposition - Một thuật toán chiếu dựa trên laplacian đồ thị thưa thớt.

Như một ví dụ cụ thể, hãy tưởng tượng rằng chúng tôi muốn biểu diễn đồ thị vô hướng sau:

Đồ thị này có ba nút, trong đó nút 0 và 1 được nối với nhau bởi một cạnh trọng số 2, và các nút 0 và 2 được nối với nhau bởi một cạnh trọng số 1. Chúng ta có thể xây dựng các biểu diễn dày đặc, che khuất và thưa thớt như được hiển thị trong ví dụ sau , hãy nhớ rằng đồ thị vô hướng được biểu diễn bằng ma trận đối xứng.

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

Chương trình trên sẽ tạo ra kết quả sau.

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

Điều này giống với đồ thị trước, ngoại trừ các nút 0 và 2 được nối với nhau bằng một cạnh có trọng số bằng không. Trong trường hợp này, biểu diễn dày đặc ở trên dẫn đến sự mơ hồ - làm thế nào có thể biểu diễn các cạnh không, nếu giá trị 0 là một giá trị có nghĩa. Trong trường hợp này, phải sử dụng biểu diễn có mặt nạ hoặc biểu diễn thưa thớt để loại bỏ sự mơ hồ.

Chúng ta hãy xem xét ví dụ sau.

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

Chương trình trên sẽ tạo ra kết quả sau.

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