An Efficient Generator for Clustered Dynamic Random Networks

Autor:	Robert Görke, Christian L. Staudt, Dorothea Wagner, Roland Kluge, Andrea Schumm
Rok vydání:	2012
Předmět:	Random graph Discrete mathematics Graph partition Neighbourhood (graph theory) law.invention Combinatorics law Frequency partition of a graph Random regular graph Line graph Feedback vertex set MathematicsofComputing_DISCRETEMATHEMATICS Clustering coefficient Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642348617 MedAlg
DOI:	10.1007/978-3-642-34862-4_16
Popis:	A planted partition graph is an Erdős-Renyi 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::db259b0e21020ee0afc7230dbcbce73e https://doi.org/10.1007/978-3-642-34862-4_16 Zobrazit plný text záznamu