Re: [igraph] Performance issue on dymanic networks

[Tamas Nepusz]

Hello Lars,

> yes I do use weights, and they are indeed not integers but floating point 
> values.
In that case, try to use a non-zero "eps" value; set it to some small
number instead, e.g., 1e-6. The reason is that in the Hungarian
algorithm, there are cases when one has to decide whether a (real or
phantom) edge is "tight", where "tight" means that the sum of the
labels of its two endpoints is equal to the weight of the edge.
However, in floating-point arithmetics, it may happen that the
equality check fails even if it would be true in reality; for
instance, try this in Python:

>>> 0.1 + 0.2 == 0.3
False

(See http://0.30000000000000004.com/ for more details).

That's why igraph uses a tolerance threshold of 'eps' where an edge is
considered tight if the sum of the labels of its two endpoints minus
the weight of the edge is less than 'eps' in absolute value. If you
use eps=0 and the weights are not integers, some edges that are tight
might not be considered tight by the algorithm. If you use a value of
eps that is too large, then some non-tight edges might be considered
tight. Both options could lead to suboptimal solutions, but I think
that eps being equal to a small positive number such as 1e-6 should be
fine.

> Could you provide me an outline of how it is done in igraph's case, maybe 
> just a reference to a paper or a book,  according to the implementation in 
> your library.

The implementation in igraph uses the original graph data structure
plus an additional adjacency list that contains the tight phantom
edges that appeared during the course of the algorithm. That's the
only trick if I remember correctly. The additional (dummy) entries of
the matrix are not stored.

For what it's worth, I think that the implementation in igraph could
actually be improved a bit. Right now the problem is that we have an
O(n^2) loop where we update the set of tight phantom edges - this is
done by examining all possible pairs of vertices from the two parts of
the graph. I think we could do better there by re-checking only those
vertices where the label of the vertex was adjusted in the last
iteration.

All the best,
T.