网站站长要会什么用,做网站怎么设置背景,东莞广告公司东莞网站建设价格,网站开发搜索功能CSGraph代表 压缩稀疏图 #xff0c;它着重于基于稀疏矩阵表示的快速图算法。
图表表示
首先#xff0c;让我们了解一个稀疏图是什么以及它在图表示中的作用。
什么是稀疏图#xff1f;
图形只是节点的集合#xff0c;它们之间有链接。图表几乎可以代表任何事物 - 社交网络…CSGraph代表 压缩稀疏图 它着重于基于稀疏矩阵表示的快速图算法。
图表表示
首先让我们了解一个稀疏图是什么以及它在图表示中的作用。
什么是稀疏图
图形只是节点的集合它们之间有链接。图表几乎可以代表任何事物 - 社交网络连接每个节点都是一个人并且与熟人相连;
图像其中每个节点是像素并连接到相邻像素; 指向高维分布其中每个节点都连接到最近的邻居并且几乎可以想象其他任何事物。
表示图形数据的一种非常有效的方式是在一个稀疏矩阵中让我们称之为G.矩阵G的大小为N×N并且G
[ij]给出节点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_valuenp.inf)
print G2_sparse.data
上述程序将生成以下输出。
array([ 2., 0., 2., 0.])
