Back to search

University of South Florida

Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations

Abstract

dc:description

Real 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 × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/7293

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gandy, Clayton A.. Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations. Thesis thesis, University of South Florida, 2018. https://digitalcommons.usf.edu/etd/7293