Graph.get_adjacency() 很慢，输出很奇怪

Question

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

1. 即使G是稀疏的，有3000个节点，A在我的商用笔记本电脑上也需要很长时间才能生成。难不成邻接矩阵的创建成本这么高？
2. 输出的A是一个Matrix对象，所以如果我想用numpy模块对A进行操作，我必须先将它转换成一个列表，然后再转换成一个numpy.matrix。此外，如果 A 是稀疏的，我需要在稀疏 scipy 矩阵中进行第三次转换。

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

Answer 1

1. 图是否稀疏并不重要，因为 igraph 仍会创建一个密集矩阵，因此它是一个 O(n²) 操作。 （从技术上讲，矩阵本身是在 C 层中创建的，其中将矩阵初始化为全零需要 O(n²)，然后在 O(m) 中用 1 填充，其中n 是顶点数，m 是边数——但是随后矩阵被转发到 Python 层，在那里它被转换成 Matrix 对象，而 Python 层不知道该矩阵本质上是稀疏的，因此需要 O(n²) 来转换它，在我的笔记本电脑上，为具有 3000 个节点的图创建邻接矩阵大约需要 500 毫秒，我认为这是应该是正常的吧。

2. 是的，有一种方法可以直接从 igraph 图创建稀疏矩阵，尽管它有点冗长：

   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 稀疏矩阵。