Interactive Random Graph Generation with Evolutionary Algorithms

Abstract : This article introduces an interactive system called GraphCuisine that lets users steer an Evolutionary Algorithm (EA) to create random graphs matching a set of user-specified measures. Generating random graphs with particular characteristics is crucial for evaluating graph algorithms, layouts and visualization techniques. Current random graph generators provide limited control of the nal characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given one. This is due to the fact that the similarity of graphs is often based on unknown parameters leading to a long and painful iterative process including steps of random graph generation, parameter changes, and visual inspection. Our system is based on an approach of interactive evolutionary computation. Fitting generator parameters to create graphs with de ned measures is an optimization problem, while judging the quality of the resulting graphs often involves human subjective judgment. We describe the graph generation process from a user's perspective, provide details about our evolutionary algorithm and demonstrate how GraphCuisine is employed to generate graphs that mimic a given real world network.
Type de document :
Communication dans un congrès
W. Didimo and M. Patrignani. Graph Drawing 2012, Sep 2012, Berlin, Germany. Springer, 7704, pp.541-552, 2012, Lecture Notes in Computer Science; LNCS. <10.1007/978-3-642-36763-2_48>
Liste complète des métadonnées



https://hal.inria.fr/hal-00720161
Contributeur : Benjamin Bach <>
Soumis le : vendredi 1 février 2013 - 13:33:58
Dernière modification le : jeudi 9 février 2017 - 15:48:28
Document(s) archivé(s) le : jeudi 2 mai 2013 - 02:35:08

Fichiers

gd-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Benjamin Bach, André Spritzer, Evelyne Lutton, Jean-Daniel Fekete. Interactive Random Graph Generation with Evolutionary Algorithms. W. Didimo and M. Patrignani. Graph Drawing 2012, Sep 2012, Berlin, Germany. Springer, 7704, pp.541-552, 2012, Lecture Notes in Computer Science; LNCS. <10.1007/978-3-642-36763-2_48>. <hal-00720161>

Partager

Métriques

Consultations de
la notice

650

Téléchargements du document

550