增量图算法

Incrementalizing Graph Algorithms

Author: Wenfei Fan
Time: 2021
Conference: SIGMOD

MOTIVATION

Incremental algorithms are vital for dynamic graphs, but incremental algorithms are hard to write:

• A large number of batch algorithms are in place for static graphs.
• Few incremental algorithms have been developed.
• Fewer incremental algorithms offer performance guarantees.
  增量算法对于动态图的分析至关重要，但是增量算法难以实现和分析。所以现在批量的图算法很多，而增量算法很少，并且更有甚者能有性能上的保证。

Questions: Is it possible to have a systematic method for developing incremental graph algorithms with performance guarantees?

METHOD

本文的目的是针对一类叫做"固定点"算法，提供指导方法，依据步骤能从batch algorithms出发一步一步推导出有性能保证的incremental algorithms。并且对推导得到的incremental algorithms进行分类，分类的依据是额外利用的辅助结构不同。最后给出了该指导方法的理论保证。

Fixpoint Model

文中首先给出了固定点算法的描述，即如果一个算法满足如下公式，则可以叫做"fixpoint batch algorithm"。意思是如果算法的整体执行流程是按迭代进行的，即算法的每一次迭代都对范围内的状态变量应用其更新函数(update function)得到新的状态变量，一直迭代直到到达固定点。