Strongly Connected Components in StreamGraphs: Computation and Experimentations


Léo Rannou, Clémence Magnien, and Matthieu Latapy

The 9th International Conference on Complex Networks and their Applications (Complex Networks 2020)


Stream graphs model highly dynamic networks in which nodes and/or links arrive and/or leave over time. Strongly connected components in stream graphs were defined recently, but no algorithm was provided to compute them. We present here several solutions with polynomial time and space complexities, each with its own strengths and weaknesses. We provide an implementation and experimentally compare the algorithms in a wide variety of practical cases. In addition, we propose an approximation scheme that significantly reduces computation costs, and gives even more insight on the dataset.

This entry was posted in Papers