Show simple item record

dc.contributor.advisorBader, David A.
dc.contributor.authorZakrzewska, Anita N.
dc.date.accessioned2018-05-31T18:16:10Z
dc.date.available2018-05-31T18:16:10Z
dc.date.created2018-05
dc.date.issued2018-04-13
dc.date.submittedMay 2018
dc.identifier.urihttp://hdl.handle.net/1853/59917
dc.description.abstractGraph 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.
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.subjectGraph algorithms
dc.subjectGraph analysis
dc.subjectStreaming data
dc.subjectDynamic graphs
dc.subjectCommunity detection
dc.subjectSampling
dc.titleGraph analysis of streaming relational data
dc.typeDissertation
dc.description.degreePh.D.
dc.contributor.departmentComputational Science and Engineering
thesis.degree.levelDoctoral
dc.contributor.committeeMemberCatalyurek, Umit
dc.contributor.committeeMemberDilkina, Bistra
dc.contributor.committeeMemberDovrolis, Constantine
dc.contributor.committeeMemberAluru, Srinivas
dc.contributor.committeeMemberRiedy, Jason
dc.date.updated2018-05-31T18:16:10Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record