Python Data Science 简明教程

Python - Graph Data

CSGraph 表示 Compressed Sparse Graph ，专注于基于稀疏矩阵表示的快速图算法。

Graph Representations

首先，我们了解一下稀疏图是什么，以及它在图表示中如何提供帮助。

What exactly is a sparse graph?

图只是一组节点，它们之间存在链接。图可以表示几乎任何内容 − 社交网络连接，其中每个节点都是一个人，并连接到熟人；图像，其中每个节点都是一个像素，并连接到相邻像素；高维分布中的点，其中每个节点都连接到其最近邻点，以及实际上你能想象到的任何其他内容。

用稀疏矩阵表示图数据是一种非常有效的方法：让我们称之为 G。矩阵 G 的大小为 N x N，G[i, j] 给出了节点“i”和节点“j”之间连接的值。稀疏图主要包含零 − 也就是说，大多数节点只有少数连接。此特性在大多数情况下都是成立的。

创建稀疏图子模块的动机来自 scikit-learn 中使用的几种算法，包括以下算法 −

  1. Isomap − 流形学习算法，需要在图中找到最短路径。

  2. Hierarchical clustering − 基于最小生成树的聚类算法。

  3. Spectral Decomposition − 基于稀疏图拉普拉斯算子的投影算法。

举个具体的例子，假设我们要表示以下无向图 −

undirected graph

此图有三个节点，其中节点 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])
undirected graph using symmetric matrix

这与之前的图相同，只是节点 0 和 2 由权重为 0 的边连接。在这种情况下，以上的稠密表示会导致歧义 − 如果 0 是一个有意义的值，那么如何表示非边。在这种情况下，必须使用掩码或稀疏表示来消除歧义。

让我们考虑以下示例。

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