Back to search

Georgia Institute of Technology

Finding Dense Regions of Rapidly Changing Graphs

Abstract

dc:description.abstract

Many of today's massive and rapidly changing graphs contain internal structure---hierarchies of locally dense regions---and finding and tracking this structure is key to detecting emerging behavior, exposing internal activity, summarizing for downstream tasks, identifying important regions, and more. Existing techniques to track these regions fundamentally cannot handle the scale, rate of change, and temporal nature of today's graphs. We identify the crucial missing piece as the need to address the significant variability in graph change rates, algorithm runtimes, temporal behavior, and dense structures themselves. We tackle tracking dense regions in three parts. First, we extend algorithms and theory around dense region computation. We computationally unify nuclei into computing hypergraph cores, providing significant improvements over hand-tuned nuclei algorithms and enabling higher-order nuclei. We develop new batch algorithms for maintaining core hierarchies. We then define new temporal dense regions, called core chains, that build on nuclei hierarchy maintenance and enable effective and powerful dense region tracking. Second, we scale up on shared-memory systems. We provide a parallel input and output library that reduces start-up costs of all known graph systems. We provide the first parallel scalable core and hypergraph core maintenance algorithms, building on the connection between $h$-indices and cores. This addresses computation on rapidly changing graphs during bursty periods with large numbers of graph changes. Third, we address scaling out to support massive graphs. We develop the first parallel $h$-index algorithm, the key kernel for tracking dense regions. We identify that system elasticity is imperative to handle large bursts of changes. We develop a dynamic and elastic graph system, using consistent hashing and sketches, and demonstrate competitive performance against static, inelastic graph systems while enabling new, dynamic applications. By addressing variability directly---in algorithm and system design---we break through previous barriers and bring dense region tracking to massive, rapidly changing graphs.

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
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gabert, Kasimir Georg
Advisor dc:contributor.advisor
  • Çatalyürek, Ümit V.
Committee members dc:contributor.committeemember
  • Pinar, Ali
  • Prakash, B. Aditya
  • Kumar, Srijan
  • Aluru, Srinivas

Subjects

dc:subject × 9

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Gabert, Kasimir Georg. Finding Dense Regions of Rapidly Changing Graphs. Doctoral thesis, Georgia Institute of Technology, 2022. http://hdl.handle.net/1853/66611