<p>As described in <a href="https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.cycles.simple_cycles.html#r230" rel="nofollow noreferrer">NetworkX documentation</a>, <code>simple_cycles</code> uses Johnson's algorithm to find elementary cycles. The complexity of the algorithm is <code>O((V+E).(1+C))</code> where </p>

<ul>
<li><code>V</code> is the number of vertices;</li>
<li><code>E</code> is the number of edges;</li>
<li><code>C</code> the number of cycles.</li>
</ul>

<p>In your case <code>V+E ~= 150,000</code>, so assuming the python process is not overloaded, we could expect the running time to be <code>150,000.K.C</code>.</p>

<p>To try to find an estimate of <code>K</code>, you can run the algorithm on smaller graphs, using power of 10 (<code>V+E = 10, 100, 1000 ...</code>) to ensure the running time of the <code>simple_cycles</code> remain proportional to <code>(V+E)(1+C)</code>, get a rough value of <code>K</code> and estimate the running time for your graph based on the number of cycles you expect to find. More precisely, if we note R(V+E,C) the actual running time for each of the experimental smaller graph, and <code>C0, C1, ...Cn</code> their respective number of cycles, then we would expect to have</p>

<pre><code>R(100,C1)  / R(10,C0)  ~= 10.K.[(1+C1) / (1+C0)]
R(1000,C1) / R(100,C0) ~= 10.K.[(1+C2) / (1+C1)]
...
</code></pre>

<p>If the <code>simple_cycles</code> running time does not exhibit the complexity of Johnson's algorithm, then there is a non-algorithmic factor which is slowing down/preventing the computation - this would then need to be investigated.</p>

<p><strong>Follow-up</strong>
These are the results of some investigation with the graph you provided. I tried to compute the number of cycles with the NetworkX library for smaller subgraphs and reproduced below some interesting results. There are the number of nodes and edges for each subgraph along with the number of cycles computed.</p>

<pre><code>\#Nodes  | \#Edges | \#Cycles (computed)
----------------------------------------
   1,000 |     186 |                17
   2,000 |     675 |                37
   3,000 |   1,460 |                72
   4,000 |   2,538 |             2,147   
   4,250 |   2,881 |         2,351,883
</code></pre>

<p>I stopped at <code>#Nodes = 4000</code> for which I could not get any result within minutes.</p>

<p>Let's calculate, for each of these values, the value </p>

<pre><code>log10(C)/E with C = \#Cycles and E = \#Edges.

E = \#Edges | C = \#Cycles (computed) |  log(C)/E  | 
----------------------------------------------------
        186 |                      17 |     0.0067 |
        675 |                      37 |     0.0023 |
      1,460 |                      72 |     0.0013 |
      2,538 |                   2,147 |     0,0013 |
      2,881 |               2,351,883 |     0,0022 |
</code></pre>

<p>As we can see, at least for subgraphs of <code>G</code> with less than <code>~2,500</code> edges, the number of cycles follow roughly the following power law</p>

<pre><code>log10(C) = 0.0013.E =&gt; C = 1.003^E
</code></pre>

<p>The empirical 1.003 comes from the topology of your graph (as a side note, the <a href="https://arxiv.org/abs/1702.02662" rel="nofollow noreferrer">maximum theoretical number of cycles given the number of edges</a> is estimated to be <code>1.443^E</code>.).</p>

<p>Note that we don't know if this constant remains the same as the graph gets bigger - this would be an interesting thing to check, but using a different method than this brute-force one (we already have one thousand of a billion cycle when we reach 5000 edges).</p>

<p>In the case (and only in this case) that the constant does not change as the graph gets bigger up to the 150,000 edges of <code>G</code>, the approximate number of cycles would be... <code>~10^359</code></p>

<p>=> It seems you are actually hitting an algorithmic complexity wall. With this in mind, I don't know which alternative you wish to choose to move forward - maybe there exists non-exponential approximation algorithms?</p>

<p><strong>Note</strong><br>
To experiment with subgraphs of <code>G</code> I used the following commands - specifying a target number of nodes, for instance for 3,000 nodes:</p>

<pre><code> H = G.copy()
 H.remove_nodes_from(list(nodes)[3000:])
 len(list(nx.simple_cycles(H)))
</code></pre>
How to Estimate Roughly The Computation Time While Using Module NetworkX
<p>Hi I am dealing with a bit <strong>big</strong> (sorry for ambiguous term) graph, which has <strong>29,981 number of nodes</strong> with <strong>150,000 directed-edges</strong> in it. </p>

<p>I am dealing with it with module <strong>networkx</strong> which is fairly widely used nowadays among graph theorists. </p>

<p>I had executed following script early this morning in Jupyter but can't estimate when to finish:</p>

<pre><code>import netowkx as nx
import pickle

# to read the graph
with open ('/home/zachary/H{}'.format("29981"), 'rb') as fp:
    H = pickle.load(fp)     

print(list(nx.simple_cycles(H)))
</code></pre>

<p>How can I roughly guess the time of finish of this script?</p>

<p>I a bit knows of what <code>big O</code> and <code>small O</code>'s.. but normally this kind of theoretically knowledge still not yet matured in my mind to industrially use those knowledge to calculate and  estimate the computation time.</p>