Summary: A planted partition graph is an Erdős-Rényi type random graph, where, based on a given partition of the vertex set, vertices in the same part are linked with a higher probability than vertices in different parts. Graphs of this type are frequently used to evaluate graph clustering algorithms, i.e., algorithms that seek to partition the vertex set of a graph into densely connected clusters. We propose a self-evident modification of this model to generate sequences of random graphs that are obtained by atomic updates, i.e., the deletion or insertion of an edge or vertex. The random process follows a dynamically changing ground-truth clustering that can be used to evaluate dynamic graph clustering algorithms. We give a theoretical justification of our model and show how the corresponding random process can be implemented efficiently.
For the entire collection see [Zbl 1259.68004].