General graph generators: experiments, analyses, and improvements

Xiang, S; Wen, D; Cheng, D; Zhang, Y; Qin, L; Qian, Z; Lin, X

General graph generators: experiments, analyses, and improvements

Xiang, S Wen, D Cheng, D Zhang, Y

Qin, L

Qian, Z Lin, X

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Conference Proceeding
Citation:: VLDB Journal, 2021, pp. 1-29
Issue Date:: 2021-01-01

Closed Access

	Filename	Description	Size
	Xiang2021_Article_GeneralGraphGeneratorsExperime.pdf	Published version	688.06 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Xiang, S
dc.contributor.author	Wen, D
dc.contributor.author	Cheng, D
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Qian, Z
dc.contributor.author	Lin, X
dc.date.accessioned	2021-12-01T23:32:17Z
dc.date.available	2021-12-01T23:32:17Z
dc.date.issued	2021-01-01
dc.identifier.citation	VLDB Journal, 2021, pp. 1-29
dc.identifier.issn	1066-8888
dc.identifier.issn	0949-877X
dc.identifier.uri	http://hdl.handle.net/10453/152018
dc.description.abstract	Graph simulation is one of the most fundamental problems in graph processing and analytics. It can help users to generate new graphs on different scales to mimic observed real-life graphs in many applications such as social networks, biology networks, and information technology. In this paper, we focus on one of the most important types of graph generators: general graph generators, which aim to reproduce the properties of the observed graphs regardless of the domains. Though a variety of graph generators have been proposed in the literature, there are still several important research gaps in this area. In this paper, we first give an overview of the existing general graph generators, including recently emerged deep learning-based approaches. We classify them into four categories: simple model-based generators, complex model-based generators, autoencoder-based generators, and GAN-based generators. Then we conduct a comprehensive experimental evaluation of 20 representative graph generators based on 17 evaluation metrics and 12 real-life graphs. We provide a general roadmap of recommendations for how to select general graph generators under different settings. Furthermore, we propose a new method that can achieve a good trade-off between simulation quality and efficiency. To help researchers and practitioners apply general graph generators in their applications or make a comprehensive evaluation of their proposed general graph generators, we also implement an end-to-end platform that is publicly available.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	VLDB Journal
dc.relation.isbasedon	10.1007/s00778-021-00701-5
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0804 Data Format, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	General graph generators: experiments, analyses, and improvements
dc.type	Conference Proceeding
utslib.for	0804 Data Format
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2021-12-01T23:32:16Z
pubs.publication-status	Published

Abstract:

Graph simulation is one of the most fundamental problems in graph processing and analytics. It can help users to generate new graphs on different scales to mimic observed real-life graphs in many applications such as social networks, biology networks, and information technology. In this paper, we focus on one of the most important types of graph generators: general graph generators, which aim to reproduce the properties of the observed graphs regardless of the domains. Though a variety of graph generators have been proposed in the literature, there are still several important research gaps in this area. In this paper, we first give an overview of the existing general graph generators, including recently emerged deep learning-based approaches. We classify them into four categories: simple model-based generators, complex model-based generators, autoencoder-based generators, and GAN-based generators. Then we conduct a comprehensive experimental evaluation of 20 representative graph generators based on 17 evaluation metrics and 12 real-life graphs. We provide a general roadmap of recommendations for how to select general graph generators under different settings. Furthermore, we propose a new method that can achieve a good trade-off between simulation quality and efficiency. To help researchers and practitioners apply general graph generators in their applications or make a comprehensive evaluation of their proposed general graph generators, we also implement an end-to-end platform that is publicly available.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/152018