RTG: A Recursive Realistic Graph Generator Using Random Typing
Abstract
We propose a new, recursive model to generate realistic graphs, evolving over time. Our model has the following properties: it is (a) flexible, capable of generating the cross product of weighted/ unweighted, directed/undirected, uni/bipartite graphs; (b) realistic, giving graphs that obey eleven static and dynamic laws that real graphs follow (we formally prove that for several of the (power) laws and we estimate their exponents as a function of the model parameters); (c) parsimonious, requiring only four parameters. (d) fast, being linear on the number of edges; (e) simple, intuitively leading to the generation of macroscopic patterns. We empirically show that our model mimics two real-world graphs very well: Blognet (unipartite, undirected, unweighted) with 27K nodes and 125K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23K nodes and 880K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar.
Cite
Text
Akoglu and Faloutsos. "RTG: A Recursive Realistic Graph Generator Using Random Typing." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2009. doi:10.1007/978-3-642-04180-8_13Markdown
[Akoglu and Faloutsos. "RTG: A Recursive Realistic Graph Generator Using Random Typing." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2009.](https://mlanthology.org/ecmlpkdd/2009/akoglu2009ecmlpkdd-rtg/) doi:10.1007/978-3-642-04180-8_13BibTeX
@inproceedings{akoglu2009ecmlpkdd-rtg,
title = {{RTG: A Recursive Realistic Graph Generator Using Random Typing}},
author = {Akoglu, Leman and Faloutsos, Christos},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2009},
pages = {13-28},
doi = {10.1007/978-3-642-04180-8_13},
url = {https://mlanthology.org/ecmlpkdd/2009/akoglu2009ecmlpkdd-rtg/}
}