title: Efficient way to speeding up graph theory and complex network algorithms on CPU/GPU using Python?
body: <p><em><strong>P.S.:</strong> I've mentioned possible solutions to my problem but have many confusions with them, please provide me suggestions on them. Also if this question is not good for this site, please point me to the correct site and I'll move the question there. Thanks in advance.</em></p>
  <p>I need to perform some repetitive graph theory and complex network algorithms to analyze approx 2000 undirected simple graphs with no self-loops for some research work. Each graph has approx 40,000 nodes and approx 600,000 edges (essentially making them sparse graphs).</p>
  <p>Currently, I am using NetworkX for my analysis and currently running <code>nx.algorithms.cluster.average_clustering(G)</code> and <code>nx.average_shortest_path_length(G)</code> for 500 such graphs and the code is running for 3 days and have reached only halfway. This makes me fearful that my full analysis will take a huge and unexpected time.</p>
  <p>Before elaborating on my problem and the probable solutions I've thought of, let me mention my computer's configuration as it may help you in suggesting the best approach. I am running Windows 10 on an Intel i7-9700K processor with 32GB RAM and one Zotac GeForce GTX 1050 Ti OC Edition ZT-P10510B-10L 4GB PCI Express Graphics Card.</p>
  <p>Explaining my possible solutions and my confusions regarding them:</p>
  <p><strong>A) Using GPU with Adjacency Matrix as Graph Data Structure:</strong> I can put an adjacency matrix on GPU and perform my analysis by manually coding them with <strong>PyCuda</strong> or <strong>Numba</strong> using loops only as recursion cannot be handled by GPU. The nearest I was able to search is <a href="https://stackoverflow.com/questions/4601364/gpu-based-search-for-all-possible-paths-between-two-nodes-on-a-graph">this on stackoverflow</a> but it has no good solution.</p>
  <p><em><strong>My Expectations:</strong></em> I hope to speedup algorithms such as All Pair Shortest Path, All Possible Paths between two nodes, Average Clustering, Average Shortest Path Length, and Small World Properties, etc. If it gives a significant speedup per graph, my results can be achieved very fast.</p>
  <p><em><strong>My Confusions:</strong></em></p>
  <ol>
  <li>Could these graph algorithms can be efficiently coded in GPU?</li>
  <li>Which will be better to use? PyCuda or Numba?</li>
  <li>Is there any other way to store Graphs on GPU that could be more efficient as my graphs are sparse graphs.</li>
  <li>I am an average Python Programmer with no experience of GPU programming, so I will have to understand and learn GPU programming with PyCuda/ Numba. Which one is easier to learn?</li>
  </ol>
  <p><strong>B) Parallelizing Programs on CPU Itself:</strong> I can use Joblib or any other library to parallelly run the program on my CPU itself. I can arrange 2-3 more computers on which I can run small independent portions of programs or can run 500 graphs per computer.</p>
  <p><em><strong>My Expectations:</strong></em> I hope to speedup algorithms by parallelizing and dividing tasks among computers. If the GPU solution does not work, I may still have some hope by this method.</p>
  <p><em><strong>My Confusions:</strong></em></p>
  <ol>
  <li>Which other libraries are available as good alternatives for Joblib?</li>
  <li>Should I allot all CPU cores (8 cores in i7) for my programs or use fewer cores?</li>
  </ol>
  <p><strong>C) Apart from my probable solutions do you have any other suggestions for me?</strong> If a better and faster solution is available in any other language except C/C++, you can also suggest them as well, as I am already considering C++ as a fallback plan if nothing works.</p>
  <hr />
  <p><strong>Work In Progress Updates</strong></p>
  <ol>
  <li><p>In different suggestions from comments on this question and discussion in my community, these are the points I've suggested to explore.</p>
  <ul>
  <li>GraphBLAS</li>
  <li>boost.graph + extensions with python-wrappers</li>
  <li>graph-tool</li>
  <li>Spark/ Dask</li>
  <li>PyCuda/ Numba</li>
  <li>Linear Algerbra methods using Pytorch</li>
  </ul>
  </li>
  <li><p>I tried to run 100 graphs on my CPU (using <code>n_job=-1</code>) using Joblib, the CPU was continuously hitting a temperature of 100°C. The processor tripped after running for 3 hours. - As a solution, I am using 75% of available cores on multiple computers (so if available cores are 8, I am using 6 cores) and the program is running fine. the speedup is also good.</p>
  </li>
  </ol>