What is the most efficient graph data structure in Python? [closed]

I would strongly advocate you look at NetworkX. It's a battle-tested war horse and the first tool most 'research' types reach for when they need to do analysis of network based data. I have manipulated graphs with 100s of thousands of edges without problem on a notebook. Its feature rich and very easy to use. You will find yourself focusing more on the problem at hand rather than the details in the underlying implementation.

Example of Erdős-Rényi random graph generation and analysis

"""Create an G{n,m} random graph with n nodes and m edgesand report some properties.This graph is sometimes called the Erd##[m~Qs-Rényi graphbut is different from G{n,p} or binomial_graph which is alsosometimes 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.htmlfrom networkx import *import sysn=10 # 10 nodesm=20 # 20 edgesG=gnm_random_graph(n,m)# some propertiesprint "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)

Visualizations are also straightforward:

More visualization: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Even though this question is now quite old, I think it is worthwhile to mention my own python module for graph manipulation called graph-tool. It is very efficient, since the data structures and algorithms are implemented in C++, with template metaprograming, using the Boost Graph Library. Therefore its performance (both in memory usage and runtime) is comparable to a pure C++ library, and can be orders of magnitude better than typical python code, without sacrificing ease of use. I use it myself constantly to work with very large graphs.

As already mentioned, NetworkX is very good, with another option being igraph. Both modules will have most (if not all) the analysis tools you're likely to need, and both libraries are routinely used with large networks.