RTG: a recursive realistic graph generator using random typing |
| |
Authors: | Leman Akoglu Christos Faloutsos |
| |
Affiliation: | (1) School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA |
| |
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 27 K nodes and 125 K edges; and Committee-to-Candidate campaign donations (bipartite, directed, weighted) with 23 K nodes and 880 K edges. We also show how to handle time so that edge/weight additions are bursty and self-similar. |
| |
Keywords: | Simulation and modeling Model validation and analysis Graph generators |
本文献已被 SpringerLink 等数据库收录! |
|