<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>

[{'answer_id': 1174, 'author': 'Lasse V. Karlsen', 'author_id': 267, 'author_profile': 'https://Stackoverflow.com/users/267', 'pm_score': 2, 'selected': False, 'text': '<p>A dictionary may also contain overhead, depending on the actual implementation. A hashtable usually contain some prime number of available nodes to begin with, even though you might only use a couple of the nodes.</p>\n\n<p>Judging by your example, "Property", would you be better of with a class approach for the final level and real properties? Or is the names of the properties changing a lot from node to node?</p>\n\n<p>I\'d say that what "efficient" means depends on a lot of things, like:</p>\n\n<ul>\n<li>speed of updates (insert, update, delete)</li>\n<li>speed of random access retrieval</li>\n<li>speed of sequential retrieval</li>\n<li>memory used</li>\n</ul>\n\n<p>I think that you\'ll find that a data structure that is speedy will generally consume more memory than one that is slow. This isn\'t always the case, but most data structures seems to follow this.</p>\n\n<p>A dictionary might be easy to use, and give you relatively uniformly fast access, it will most likely use more memory than, as you suggest, lists. Lists, however, generally tend to contain more overhead when you insert data into it, unless they preallocate X nodes, in which they will again use more memory.</p>\n\n<p>My suggestion, in general, would be to just use the method that seems the most natural to you, and then do a "stress test" of the system, adding a substantial amount of data to it and see if it becomes a problem.</p>\n\n<p>You might also consider adding a layer of abstraction to your system, so that you don\'t have to change the programming interface if you later on need to change the internal data structure.</p>\n'}, {'answer_id': 1191, 'author': 'Matthew Schinckel', 'author_id': 188, 'author_profile': 'https://Stackoverflow.com/users/188', 'pm_score': 2, 'selected': False, 'text': '<p>Making a class-based structure would probably have more overhead than the dict-based structure, since in python classes actually use dicts when they are implemented.</p>\n'}, {'answer_id': 3107, 'author': 'Peter Burns', 'author_id': 101, 'author_profile': 'https://Stackoverflow.com/users/101', 'pm_score': 2, 'selected': False, 'text': "<p>As I understand it, random access is in constant time for both Python's dicts and lists, the difference is that you can only do random access of integer indexes with lists.  I'm assuming that you need to lookup a node by its label, so you want a dict of dicts.</p>\n\n<p>However, on the performance front, loading it into memory may not be a problem, but if you use too much you'll end up swapping to disk, which will kill the performance of even Python's highly efficient dicts.  Try to keep memory usage down as much as possible.  Also, RAM is amazingly cheap right now; if you do this kind of thing a lot, there's no reason not to have at least 4GB.</p>\n\n<p>If you'd like advice on keeping memory usage down, give some more information about the kind of information you're tracking for each node.</p>\n"}, {'answer_id': 28705, 'author': 'Ryan Cox', 'author_id': 620, 'author_profile': 'https://Stackoverflow.com/users/620', 'pm_score': 7, 'selected': True, 'text': '<p>I would strongly advocate you look at <a href="http://networkx.github.com/" rel="noreferrer">NetworkX</a>. 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.</p>\n\n<p><strong>Example of <a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" rel="noreferrer">Erdős-Rényi</a> random graph generation and analysis</strong></p>\n\n<pre><code>\n"""\nCreate an G{n,m} random graph with n nodes and m edges\nand report some properties.\n\nThis graph is sometimes called the Erd##[m~Qs-Rényi graph\nbut is different from G{n,p} or binomial_graph which is also\nsometimes called the Erd##[m~Qs-Rényi graph.\n"""\n__author__ = """Aric Hagberg (hagberg@lanl.gov)"""\n__credits__ = """"""\n#    Copyright (C) 2004-2006 by \n#    Aric Hagberg \n#    Dan Schult \n#    Pieter Swart \n#    Distributed under the terms of the GNU Lesser General Public License\n#    http://www.gnu.org/copyleft/lesser.html\n\nfrom networkx import *\nimport sys\n\nn=10 # 10 nodes\nm=20 # 20 edges\n\nG=gnm_random_graph(n,m)\n\n# some properties\nprint "node degree clustering"\nfor v in nodes(G):\n    print v,degree(G,v),clustering(G,v)\n\n# print the adjacency list to terminal \nwrite_adjlist(G,sys.stdout)\n</code></pre>\n\n<p>Visualizations are also straightforward:</p>\n\n<p><img src="https://i.stack.imgur.com/5biM9.jpg" alt="enter image description here"></p>\n\n<p>More visualization: <a href="http://jonschull.blogspot.com/2008/08/graph-visualization.html" rel="noreferrer">http://jonschull.blogspot.com/2008/08/graph-visualization.html</a></p>\n'}, {'answer_id': 29836, 'author': 'Kai', 'author_id': 2963, 'author_profile': 'https://Stackoverflow.com/users/2963', 'pm_score': 3, 'selected': False, 'text': '<p>As already mentioned, NetworkX is very good, with another option being <a href="http://cneurocvs.rmki.kfki.hu/igraph/" rel="noreferrer">igraph</a>. 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.</p>\n'}, {'answer_id': 4292022, 'author': 'Tiago Peixoto', 'author_id': 180962, 'author_profile': 'https://Stackoverflow.com/users/180962', 'pm_score': 4, 'selected': False, 'text': '<p>Even though this question is now quite old, I think it is worthwhile to mention my own python module for graph manipulation called <a href="http://graph-tool.skewed.de" rel="noreferrer">graph-tool</a>. 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.</p>\n'}, {'answer_id': 34850877, 'author': 'Pranav Waila', 'author_id': 2639344, 'author_profile': 'https://Stackoverflow.com/users/2639344', 'pm_score': 1, 'selected': False, 'text': '<p>No doubt NetworkX is the best data structure till now for graph. It comes with utilities like Helper Functions, Data Structures and Algorithms, Random Sequence Generators, Decorators, Cuthill-Mckee Ordering, Context Managers</p>\n\n<p>NetworkX is great because it wowrs for graphs, digraphs, and multigraphs. It can write graph with multiple ways: Adjacency List, Multiline Adjacency List,\nEdge List, GEXF, GML. It works with Pickle, GraphML, JSON, SparseGraph6 etc. </p>\n\n<p>It has implimentation of various radimade algorithms including:\nApproximation, Bipartite, Boundary, Centrality, Clique, Clustering,    Coloring, Components, Connectivity, Cycles,  Directed Acyclic Graphs,\nDistance Measures,  Dominating Sets, Eulerian, Isomorphism,  Link Analysis,  Link Prediction, Matching, Minimum Spanning Tree, Rich Club, Shortest Paths, Traversal, Tree.</p>\n'}]
['https://Stackoverflow.com/questions/1171', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/280/']