Institute for Web Science and Technologies · Universität Koblenz - Landau
Institute WeST

High-Precision Graph Generation

[go to overview]

We introduce an algorithm for generating graphs that reproduces properties of input graphs to a very high precision, using as information only six subgraph counts. Our algorithm works iteratively by decreasing a suitable error measure based on the requested statistic values. We show that our algorithm outperforms previous graph generation algorithms in terms of the error in the reconstructed graphs by a wide margin. We evaluate the algorithm in terms of precision, speed of convergence, scalability and versatility, and compare it to previous graph generators and models. We also show that our algorithm generates graphs with realistic degree distributions, graph spectra, clustering coefficient distributions and distance distributions.

27.03.14 - 09:15
B 016