title: What scalability issues are associated with NetworkX?
body: <p>I'm interested in network analysis on large networks with millions of nodes and tens of millions of edges.  I want to be able to do things like parse networks from many formats, find connected components, detect communities, and run centrality measures like PageRank.</p>
  
  <p>I am attracted to NetworkX because it has a nice api, good documentation, and has been under active development for years.  Plus because it is in python, it should be quick to develop with.</p>
  
  <p>In a recent presentation (the slides are available on github <a href="https://github.com/drewconway/NetworkX_Intro_Materials" rel="noreferrer">here</a>), it was claimed that:</p>
  
  <blockquote>
    <p>Unlike many other tools, NX is designed to handle data on a scale
    relevant to modern problems...Most of the core algorithms in NX rely on extremely fast legacy code.</p>
  </blockquote>
  
  <p>The presentation also states that the base algorithms of NetworkX are implemented in C/Fortran.</p>
  
  <p>However, looking at the source code, it looks like NetworkX is mostly written in python.  I am not too familiar with the source code, but I am aware of a couple of examples where NetworkX uses numpy to do heavy lifting (which in turn uses C/Fortran to do linear algebra).  For example, the file <code>networkx/networkx/algorithms/centrality/eigenvector.py</code> uses numpy to calculate eigenvectors.</p>
  
  <p>Does anyone know if this strategy of calling an optimized library like numpy is really prevalent throughout NetworkX, or if just a few algorithms do it?  Also can anyone describe other scalability issues associated with NetworkX?</p>
  
  <p><strong>Reply from NetworkX Lead Programmer</strong>
  I posed this question on the NetworkX mailing list, and Aric Hagberg replied:</p>
  
  <blockquote>
    <p>The data structures used in NetworkX are appropriate for scaling to
    large problems (e.g. the data structure is an adjacency list).  The
    algorithms have various scaling properties but some of the ones you
    mention are usable  (e.g. PageRank,  connected components, are linear
    complexity in the number of edges).</p>
    
    <p>At this point NetworkX is pure Python code.  The adjacency structure
    is encoded with Python dictionaries which provides great flexibility
    at the expense of memory and computational speed.  Large graphs will
    take a lot of memory and you will eventually run out.</p>
    
    <p>NetworkX does use NumPy and SciPy for algorithms that are primarily
    based on linear algebra.  In that case the graph is represented
    (copied) as an adjacency matrix using either NumPy matrices or SciPy
    sparse matrices.  Those algorithms can benefit from the legacy C and
    FORTRAN code that is used under the hood in NumPy and SciPY.</p>
  </blockquote>