论文标题
流图中紧密连接的组件：计算和实验
Strongly Connected Components in Stream Graphs: Computation and Experimentations
论文作者
论文摘要
流图模型高度动态的网络，其中节点和/或链接随着时间的推移到达和/或离开。最近定义了流图中强烈连接的组件，但是没有提供算法来计算它们。我们在这里介绍了多个具有多项式时间和空间复杂性的解决方案，每个解决方案都具有自己的优点和劣势。我们提供实施，并在各种实际情况下比较算法。此外，我们提出了一个近似方案，可显着降低计算成本，并对数据集提供更多的见解。
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.
