2
$\begingroup$

I have been recently getting into the field of various processes on networks. For example, stochastic processes like percolation, Ising models, various statistical-physics models; or deterministic models like simulating a set of coupled non-linear differential equations.

I have encountered NetworkX in Python as one of the go-to softwares for network-related problems. But Python is generally much slower than most languages, and I suspect the code will take a very long time to run when the network size increases. I also contemplated combining libraries like Numba, but Numba is incompatible with external libraries like NetworkX.

What is the general method of running such simulations in actual research? I would really like to know if there is a way to run fast dynamical simulations on networks.

$\endgroup$
4
  • 1
    $\begingroup$ Is there something like "the general method"? Maybe you have a specific application in mind, which might help single out resource recommendations. Specific network sizes maybe? Deterministic or probabilistic models? $\endgroup$
    – kricheli
    Apr 21, 2023 at 6:07
  • $\begingroup$ Related: stackoverflow.com/q/942361 $\endgroup$
    – kricheli
    Apr 21, 2023 at 6:07
  • $\begingroup$ @Kricheli I do realise the question may have been a bit vague, and the answer might depend on the details of the problem. This particular time I was trying to code for 'non-linear' flows in between the nodes of a network, which would correspond to a system of coupled non-linear ODES. But I was also hoping if there may be any single library or language that is just faster than networkx and can be used for both deterministic and stochastic processes. $\endgroup$ Apr 21, 2023 at 9:50
  • $\begingroup$ Have you convinced yourself that the software you use is indeed too slow? Why not first convince yourself that what you are using is indeed too slow for what you want to do. $\endgroup$ Apr 21, 2023 at 20:39

1 Answer 1

2
$\begingroup$

I assume that your networks are sparse (most entries of the adjacency matrix are zero) and irregular (no grids and similar repeating structures).

As an example, let’s look at an ODE: $\dot{x} = f(x).$ Solving this can be dissected into evaluating $f$ and the ODE solver. The latter can be completely vectorised, and thus you can expect efficient implementations in any programming language suited for scientific computations, including Python. Thus, your problem boils down to efficiently evaluating $f$. Now, for things like partial differential equations or if your network is a grid, this can again be efficiently vectorised, e.g., using NumPy or Numba. However, for complex networks, this is not possible, since there is no regular structure.

This leaves you with two options:

  • Using sparse-matrix representations for your network’s adjacency matrix. This is usually easy to implement, but cannot be applied to every problem and it also can have a considerable overhead.

  • Use some meta-programming tool (code that writes code) to hardcode your network dynamics in an efficient manner. The created code would be in a low-level language like C, and ideally be operated it from a high-level language like Python. There are also dedicated tools for this.

I wrote one of the latter tools: JiTCODE. Very briefly, it takes your ODE in symbolic form, converts it to C code, compiles that, and loads it back into Python for ODE solving. In the accompanying paper (preprint), I also discuss the numerical challenges in detail. For problems other than differential equations, similar thoughts apply: You need to either meta-program your network structure or exploit existing sparse-matrix solutions.

Some specific remarks:

But Python is generally much slower than most languages […]

Note that while pure Python code is slow, the way to go is usually to implement the bottleneck in a low-level language like C and operate this from Python. This is for example what NumPy does. NetworkX doesn’t do this (at least the last time I checked), which is why it’s so slow.

is incompatible with external libraries like NetworkX

You probably won’t be able to find a library that directly integrates NetworkX, but rather need to export your network as a NumPy array or similar. However, given that you usually won’t have an interaction between the two, I don’t see this as a big problem. In general, the problem of generating and analysing networks and running dynamics on them are rather distinct, so I don’t see much of a benefit from integrating all of this into one library.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.