Interactive Random Graph Generation with Evolutionary Algorithms

Benjamin Bach, Andre Spritzer, Evelyne Lutton, Jean-Daniel Fekete

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper introduces an interactive system called GraphCuisine that lets users steer an Evolutionary Algorithm (EA) to create random graphs that match 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 final characteristics of the graphs they generate. The situation is even harder when one wants to generate random graphs similar to a given one, all-in-all leading to a long iterative process that involves several steps of random graph generation, parameter changes, and visual inspection. Our system follows an approach based on interactive evolutionary computation. Fitting generator parameters to create graphs with pre-defined measures is an optimization problem, while assessing the quality of the resulting graphs often involves human subjective judgment. In this paper 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. An interactive demo of GraphCuisine can be found on our website http://www.aviz.fr/Research/Graphcuisine.
Original languageEnglish
Title of host publicationGraph Drawing: 20th International Symposium, GD 2012, Redmond, WA, USA, September 19-21, 2012, Revised Selected Papers
EditorsWalter Didimo, Maurizio Patrignani
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages541-552
Number of pages12
ISBN (Electronic)978-3-642-36763-2
ISBN (Print)978-3-642-36762-5
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
Publisher Springer Berlin Heidelberg
Volume7704
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Interactive Random Graph Generation with Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this