Back to search

Georgia Institute of Technology

Graph analysis of streaming relational data

Abstract

dc:description.abstract

Graph analysis can be used to study streaming data from a variety of sources, such as social networks, financial transactions, and online communication. The analysis of streaming data poses many challenges, including dealing with the high volume of data and the speed with which it is generated. This dissertation addresses challenges that occur throughout the graph analysis process. Because many datasets are large and growing, it may be infeasible to collect and build a graph from all the data that has been generated. This work addresses the challenges created by large volumes of streaming data through new sampling techniques. The algorithms presented can sample a subgraph in a single pass over an edge stream and are therefore appropriate for streaming applications. A sampling algorithm that can produce a temporally biased subgraph is also presented. Before graph analysis techniques can be applied, a graph must first be created from the data collected. When creating dynamic graphs, it is not obvious how to de-emphasize old information, especially when edges are derived from interactions. This work evaluates several methods of aging old data to create dynamic graphs. This dissertation also contributes new techniques for dynamic community detection and analysis. A new algorithm for local community detection on dynamic graphs is presented. Because it incrementally updates results when the graph changes, the method is suitable for streaming data. The creation of dynamic graphs allows us to study community changes over time. This work addresses the topic of community analysis with a vertex-level measure of community change. Together, these contributions advance the study of streaming relational data through graph analysis.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computational Science and Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zakrzewska, Anita N.
Advisor dc:contributor.advisor
  • Bader, David A.
Committee members dc:contributor.committeemember
  • Catalyurek, Umit
  • Dilkina, Bistra
  • Dovrolis, Constantine
  • Aluru, Srinivas
  • Riedy, Jason

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/59917

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zakrzewska, Anita N.. Graph analysis of streaming relational data. Doctoral thesis, Georgia Institute of Technology, 2018. http://hdl.handle.net/1853/59917