Graph.get_adjacency()速度很慢，输出结果很奇怪 [英] Graph.get_adjacency() is slow and the output is strange

问题描述

考虑python-igraph 0.7中的图形对象G.如果我想要G的邻接矩阵A，我必须写A=G.get_adjacency()，但是有两个问题:

Consider a graph object G in python-igraph 0.7. If I want the adjacency matrix A of G, I have to write A=G.get_adjacency(), but there are two problems:

1. 即使G的节点数很稀疏，也只有3000个，但在我的商用笔记本电脑上很长时间内仍会生成A.邻接矩阵的创建是否可能是如此昂贵?
2. 输出A是一个Matrix对象，因此，如果要在A上的numpy模块上进行操作，则必须先在列表中转换它，然后在numpy.matrix中对其进行转换.此外，如果A稀疏，则需要在稀疏scipy矩阵中进行第三次转换.

Igraph中有什么方法可以在合理的时间内获得稀疏图的scipy.sparse矩阵?

Is there in Igraph any way to obtain a scipy.sparse matrix of a sparse graph in a reasonable time?

推荐答案

1. 图的稀疏与否无关紧要，因为igraph仍会创建一个密集矩阵，因此它是O(n ² )运算. (从技术上讲，矩阵本身是在C层中创建的，其中将矩阵初始化为全零需要O(n ² )，然后在O(m)中将其填充为1，其中n是顶点数和m是边数-但是矩阵被转发到Python层，在那儿它被转换成Matrix对象，而Python层不知道矩阵本质上是稀疏的，所以取O(n ² )进行转换，在我的笔记本电脑上，为具有3000个节点的图创建邻接矩阵大约需要500毫秒，

1. It does not matter whether the graph is sparse or not because igraph will still create a dense matrix so it's an O(n²) operation. (Technically, the matrix itself is created in the C layer where the initialization of the matrix to all zeroes takes O(n²) and then it is filled with ones in O(m) where n is the number of vertices and m is the number of edges -- but then the matrix is forwarded to the Python layer where it is converted into a Matrix object, and the Python layer has no idea that the matrix is essentially sparse so it takes O(n²) to convert it, On my laptop, creating the adjacency matrix for a graph with 3000 nodes is around 500 msec and I think this is probably normal.

是的，虽然有些冗长，但有一种方法可以立即从igraph图中创建稀疏矩阵:

Yes, there is a way to create a sparse matrix out of an igraph graph straight away, although it's a bit verbose:

from scipy.sparse import coo_matrix
from numpy import hstack, ones

def graph_to_sparse_matrix(graph):
    xs, ys = map(array, zip(*graph.get_edgelist()))
    if not graph.is_directed():
        xs, ys = hstack((xs, ys)).T, hstack((ys, xs)).T
    else:
        xs, ys = xs.T, ys.T
    return coo_matrix((ones(xs.shape), (xs, ys)))

此版本可以在我的计算机上以约26毫秒的速度将相同的图形转换为SciPy稀疏矩阵.

This version converts the same graph to a SciPy sparse matrix in ~26 msec on my machine.

这篇关于Graph.get_adjacency()速度很慢，输出结果很奇怪的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！