title: What is the most efficient graph data structure in Python?
body: <p>I need to be able to manipulate a large (10^7 nodes) graph in python. The data corresponding to each node/edge is minimal, say, a small number of strings. What is the most efficient, in terms of <strong><em>memory and speed</em></strong>, way of doing this? </p>
  
  <p>A dict of dicts is more flexible and simpler to implement, but I intuitively expect a list of lists to be faster. The list option would also require that I keep the data separate from the structure, while dicts would allow for something of the sort:</p>
  
  <pre><code>graph[I][J]["Property"]="value"
  </code></pre>
  
  <p>What would you suggest?</p>
  
  <hr>
  
  <p>Yes, I should have been a bit clearer on what I mean by efficiency. In this particular case I mean it in terms of random access retrieval.</p>
  
  <p>Loading the data in to memory isn't a huge problem. That's done once and for all. The time consuming part is visiting the nodes so I can extract the information and measure the metrics I'm interested in.</p>
  
  <p>I hadn't considered making each node a class (properties are the same for all nodes) but it seems like that would add an extra layer of overhead? I was hoping someone would have some direct experience with a similar case that they could share. After all, graphs are one of the most common abstractions in CS.</p>