{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-8490"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-8490","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gandy, Clayton A."],"institution":"University of South Florida","degree_name":"MS in Computer Science (M.S.C.S.)","degree_level":"Thesis","degree_discipline":"Computer Science and Engineering","degree_department":null,"school":null,"contributors":["Adriana Iaminitchi, Ph.D.","Yicheng Tu, Ph.D.","John Skvoretz, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-06-25T07:00:00Z","date_published":"2018-06-25T07:00:00Z","updated_at":"2026-11-19T08:43:53Z","subjects":["binary node attribute networks","dk graph models","graph generators","social networks","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/7293","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/7293","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-8490","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Adriana Iaminitchi, Ph.D.","Yicheng Tu, Ph.D.","John Skvoretz, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Gandy, Clayton A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-06-25T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S.C.S."]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science (M.S.C.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["binary node attribute networks","dk graph models","graph generators","social networks","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/7293"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations"]}]}],"canonical_facts":{"dc:contributor":["Adriana Iaminitchi, Ph.D.","Yicheng Tu, Ph.D.","John Skvoretz, Ph.D."],"dc:creator":["Gandy, Clayton A."],"dc:date":["2018-06-25T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.usf.edu/etd/7293"],"dc:subject":["binary node attribute networks","dk graph models","graph generators","social networks","Computer Sciences"],"dc:title":["Borromean: Preserving Binary Node Attribute Distributions in Large Graph Generations"],"thesis:degree_discipline":["Computer Science and Engineering"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:degree_name":["MS in Computer Science (M.S.C.S.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:43:53Z"}