University of South Florida
Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations
Abstract
dc:descriptionReal graph datasets are important for many science domains, from understanding epidemics to modeling traffic congestion. To facilitate access to realistic graph datasets, researchers proposed various graph generators typically aimed at representing particular graph properties. While many such graph generators exist, there are few techniques for generating graphs where the nodes have binary attributes. Moreover, generating such graphs in which the distribution of the node attributes preserves real-world characteristics is still an open challenge. This thesis introduces Borromean, a graph generating algorithm that creates synthetic graphs with binary node attributes in which the attributes obey an attribute-specific joint degree distribution. We show experimentally the accuracy of the generated graphs in terms of graph size, distribution of attributes, and distance from the original joint degree distribution. We also designed a parallel version of Borromean in order to generate larger graphs and show its performance. Our experiments show that Borromean can generate graphs of hundreds of thousands of nodes in under 30 minutes, and these graphs preserve the distribution of binary node attributes within 40% on average.
Degree
thesis:*- Name thesis:degree_name
- MS in Computer Science (M.S.C.S.)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Computer Science and Engineering
- Grantor
- University of South Florida
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gandy, Clayton A.
- Contributors dc:contributor
-
- Adriana Iaminitchi, Ph.D.
- Yicheng Tu, Ph.D.
- John Skvoretz, Ph.D.
Subjects
dc:subject × 5Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.usf.edu/etd/7293