73

我需要能够在 python 中操作一个大的（10^7 个节点）图。每个节点/边对应的数据是最少的，比如说，少量的字符串。就内存和速度而言，最有效的方法是什么？

dict 的 dict 更灵活、更易于实现，但我直观地希望列表列表更快。list 选项还要求我将数据与结构分开，而 dicts 将允许以下内容：

graph[I][J]["Property"]="value"

你有什么建议？

是的，我应该更清楚我所说的效率是什么意思。在这种特殊情况下，我的意思是随机访问检索。

将数据加载到内存中并不是一个大问题。这是一劳永逸的。耗时的部分是访问节点，以便我可以提取信息并测量我感兴趣的指标。

我没有考虑将每个节点都设为一个类（所有节点的属性都相同），但似乎这会增加额外的开销层？我希望有人对他们可以分享的类似案例有一些直接的经验。毕竟，图是 CS 中最常见的抽象之一。

4

7 回答 7

56

我强烈建议您查看NetworkX。这是一匹经过实战考验的战马，也是大多数“研究”类型在需要对基于网络的数据进行分析时使用的第一个工具。我已经在笔记本上毫无问题地操作了具有 100 条边的图形。它的功能丰富且非常易于使用。您会发现自己更多地关注手头的问题，而不是底层实现中的细节。

Erdős-Rényi随机图生成和分析示例


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

可视化也很简单：

在此处输入图像描述

更多可视化：http: //jonschull.blogspot.com/2008/08/graph-visualization.html

于 2008-08-26T17:43:06.413 回答
13

尽管这个问题现在已经很老了，但我认为值得一提的是我自己的用于图形操作的 python 模块，称为graph-tool。它非常有效，因为数据结构和算法是在 C++ 中实现的，带有模板元编程，使用 Boost Graph Library。因此，它的性能（在内存使用和运行时）与纯 C++ 库相当，并且可以比典型的 python 代码好几个数量级，而不会牺牲易用性。我自己经常使用它来处理非常大的图表。

于 2010-11-27T14:10:33.897 回答
6

如前所述，NetworkX 非常好，另一个选项是igraph。这两个模块都将拥有您可能需要的大部分（如果不是全部）分析工具，并且这两个库通常用于大型网络。

于 2008-08-27T10:01:21.803 回答
4

字典也可能包含开销，具体取决于实际实现。哈希表通常包含一些可用节点的素数，即使您可能只使用几个节点。

从您的示例“Property”来看，您是否会更好地使用最终级别和真实属性的类方法？或者属性的名称从节点到节点变化很大？

我想说“高效”的含义取决于很多事情，例如：

  • 更新速度（插入、更新、删除）
  • 随机存取检索速度
  • 顺序检索速度
  • 使用的内存

我认为您会发现，速度快的数据结构通常会比速度慢的数据结构消耗更多的内存。情况并非总是如此，但大多数数据结构似乎都遵循这一点。

字典可能易于使用，并为您提供相对一致的快速访问，它很可能会使用比您建议的列表更多的内存。然而，当您将数据插入其中时，列表通常会包含更多开销，除非它们预先分配 X 节点，在这些节点中它们将再次使用更多内存。

一般来说，我的建议是使用对您来说最自然的方法，然后对系统进行“压力测试”，向其中添加大量数据，看看它是否会成为问题。

您还可以考虑为您的系统添加一个抽象层，这样如果您以后需要更改内部数据结构，您就不必更改编程接口。

于 2008-08-04T12:09:55.830 回答
3

据我了解，对于 Python 的 dicts 和列表，随机访问是在恒定时间内进行的，不同之处在于您只能对带有列表的整数索引进行随机访问。我假设您需要通过其标签查找节点，因此您需要一个字典。

然而，在性能方面，将它加载到内存中可能不是问题，但如果你使用太多，你最终会交换到磁盘，这甚至会破坏 Python 的高效 dicts 的性能。尽量减少内存使用量。此外，RAM 现在非常便宜。如果你经常做这种事情，没有理由不拥有至少 4GB。

如果您想获得有关降低内存使用率的建议，请提供有关您为每个节点跟踪的信息类型的更多信息。

于 2008-08-06T05:37:33.607 回答
2

制作基于类的结构可能比基于 dict 的结构有更多的开销，因为在 python 中，类在实现时实际上使用了 dicts。

于 2008-08-04T12:41:15.767 回答
1

毫无疑问，NetworkX 是迄今为止最好的图数据结构。它带有辅助函数、数据结构和算法、随机序列生成器、装饰器、Cuthill-Mckee 排序、上下文管理器等实用程序

NetworkX 很棒，因为它适用于图、有向图和多重图。它可以用多种方式写图：邻接表、多行邻接表、边表、GEXF、GML。它适用于 Pickle、GraphML、JSON、SparseGraph6 等。

它实现了各种辐射算法，包括：逼近、二分、边界、中心性、团、聚类、着色、分量、连通性、循环、有向无环图、距离度量、支配集、欧拉、同构、链接分析、链接预测、匹配，最小生成树，丰富的俱乐部，最短路径，遍历，树。

于 2016-01-18T09:08:03.070 回答