Re: [igraph] time eastimation

[Tamas Nepusz]

Hi,

> I used igraph to i Implemented Independent cascade model (Greedy algorithm), 
> running the code on a small network (Round 2k N )..it seems endless.
> kindly,
> how can I estimate time needed for the program to run..
Empirically: run it for different values of the model parameters, plot
the runtimes, and then try to fit a curve to the observed runtimes to
get a rough estimate.

Formally: the runtime depends not (only) on the algorithm itself but
also on the efficiency of your implementation. Even the fastest
algorithm can be implemented in a way that it takes forever to run, so
we cannot decide whether the slowness is due to your particular
implementation, or because of the inherent complexity of the
algorithm, or because of a bug or bottleneck in igraph. If you want to
estimate the runtime of your implementation formally, you will have to
evaluate each instruction in your imlpementation carefully and
calculate how many times it will be executed during a typical course
of the algorithm, as a function of the algorithm parameters. The
analysis of the runtime of a particular algorithm is a complex topic
that cannot be covered in a single email, so if you are not familar
with time complexity analysis, you are advised to watch a course about
it online; Coursera seems to have a good one:

https://www.coursera.org/course/algo

Also, you might be interested in using a code profiler to identify
which parts of your code are slow.

All the best,
T.