Graph Generators: State of the Art and Open Challenges

Abstract

The abundance of interconnected data has fueled the design and implementation of graph generators reproducing real-world linking properties, or gauging the effectiveness of graph algorithms, techniques and applications manipulating these data. We consider graph generation across multiple subfields, such as Semantic Web, graph databases, social networks, and community detection, along with general graphs. Despite the disparate requirements of modern graph generators throughout these communities, we analyze them under a common umbrella, reaching out the functionalities, the practical usage, and their supported operations. We argue that this classification is serving the need of providing scientists, researchers and practitioners with the right data generator at hand for their work. This survey provides a comprehensive overview of the state-of-the-art graph generators by focusing on those that are pertinent and suitable for several data-intensive tasks. Finally, we discuss open challenges and missing requirements of current graph generators along with their future extensions to new emerging fields.

arXiv commentACM Computing Surveys, 32 pages

References in corpus (16)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Variational Graph Auto-Encoders
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• Learning Deep Generative Models of Graphs
• Community detection in networks: Structural communities versus ground truth
• A Scalable Generative Graph Model with Community Structure
• Multiplicative Attribute Graph Model of Real-World Networks
• A Survey on Theoretical Advances of Community Detection in Networks
• Graphite: Iterative Generative Modeling of Graphs
• Darwini: Generating realistic large-scale social graphs
• An Introduction to Temporal Graphs: An Algorithmic Perspective