There are two excellent choices:
NetworkX
and
igraph
I like NetworkX, but I read good things about igraph as well. I routinely use NetworkX with graphs with 1 million nodes with no problem (it’s about double the overhead of a dict of size V + E)
If you want a feature comparison, see this from the Networkx-discuss list
Feature comparison thread