Connected components in dynamic graph

Hi everybody! I use igraph to find weak connected components in large dynamic graphs (more than ~200M edges). Dynamic means that some new edges with vertices are added from time to time. It’s very expensive to recalculate connected components on the whole graph. Is there any way to use this library with such dynamic graphs? Any help would be appreciated. Thanks!

Dynamic graph connectivity algorithms are not yet implemented in the C core of igraph, or python-igraph (well, there’s IGPercolationCurve in the Mathematica interface).

However, if you need only incremental connectivity, that is fairly straightforward to implement. You will find pointers in the Wikipedia article: Dynamic connectivity - Wikipedia

1 Like