我想用Python创建邻接矩阵

Question

我有一个非常大的数据集，差不多有45万行和两列。我想用Python来计算邻接矩阵，因为之前我试着在Matlab里做，但因为数据量太大，出现了内存错误。我的数据值从100开始，一直到45万。

有没有人能帮我解决这个问题，因为我对Python还很陌生。

我需要先把文件导入到Python中，可以用Excel表格或者记事本，然后再计算邻接矩阵。

Answer 1

我建议使用defaultdict，因为它简单易用，只需要几行代码。我假设你的文件内容是这样的：

a b
c d

首先，把它放进一个列表中（可以参考这个链接：http://docs.python.org/2/library/fileinput.html），这样格式就变成了[(a, b),(c,d)]。

然后，使用defaultdict：

from collections import defaultdict

adjmat = defaultdict(int)
for edge in list:
    adjmat[edge] = 1

adjmat[a, b] 如果边存在，就会返回1，如果不存在则返回0。如果你在节点之间可以有多条边，只需要把它改成 adjmat[edge] += 1，这样 adjmat[a, b] 就会返回连接 a 和 b 的边的数量。

Answer 2

最简单的方法是什么呢？如果你有超过10,000个节点，但只有45,000条边，那就可以使用SciPy的稀疏矩阵。

http://www.scipy.org/SciPy_Tutorial#head-c60163f2fd2bab79edd94be43682414f18b90df7

SciPy提供了多种压缩方法，可以让矩阵在内存中占用更少的空间（因为矩阵中的值大部分都是0）。我相信MatLab也有类似的节省空间的稀疏矩阵数据结构。

如果你只是想知道怎么读取文件，我建议你把它保存为CSV或文本文件（把数据存储在Excel文件里其实没有什么好处）。Python自带一个库可以用来读写CSV文件：

http://docs.python.org/library/csv.html

如果你真的想使用XLS文件，那你可以用pyExcelerator（我自己没用过这个） - http://sourceforge.net/projects/pyexcelerator/ - 或者你可以使用OpenOffice.org + PyUNO，或者MS Office + COM。

Answer 3

如果我理解你的问题没错的话，你需要的内存比电脑里的RAM要多。即使有虚拟内存，你可能也无法分配这么大的内存块。所以，解决办法就是在构建邻接矩阵的时候，把它写入一个文件。这种方法在MatLab或Python中都可以使用。

---

我猜测你在处理CAIDA的路由器级拓扑测量数据，因为这个格式似乎和你描述的很相符。这个文件的每一行都包含了一个图的边，从一个IP路由器（第一列）到另一个（第二列）。如果要为192244个节点创建一个完整的邻接矩阵，假设每个节点只用一个比特，那么需要的内存将达到4.3 GB。我还是建议你直接把矩阵写入文件，而不是在内存中构建它。