• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Finding Dense Regions of Rapidly Changing Graphs

    Thumbnail
    View/Open
    GABERT-DISSERTATION-2022.pdf (7.414Mb)
    Date
    2022-05-02
    Author
    Gabert, Kasimir Georg
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/66611
    Collections
    • College of Computing Theses and Dissertations [1191]
    • Georgia Tech Theses and Dissertations [23877]
    • School of Computational Science and Engineering Theses and Dissertations [100]

    Related items

    Showing items related by title, author, creator and subject.

    • Adaptive visual network analytics: Algorithms, interfaces, and systems for exploration and querying 

      Pienta, Robert S. (Georgia Institute of Technology, 2017-10-04)
      Large graphs are now commonplace, amplifying the fundamental challenges of exploring, navigating, and understanding massive data. Our work tackles critical aspects of graph sensemaking, to create human-in-the-loop network ...
    • 6-connected graphs are two-three linked 

      Xie, Shijie (Georgia Institute of Technology, 2019-11-11)
      Let $G$ be a graph and $a_0, a_1, a_2, b_1,$ and $b_2$ be distinct vertices of $G$. Motivated by their work on Four Color Theorem, Hadwiger's conjecture for $K_6$, and J\o rgensen's conjecture, Robertson and Seymour asked ...
    • Mage: Expressive Pattern Matching in Richly-Attributed Graphs 

      Pienta, Robert; Tamersoy, Acar; Tong, Hanghang; Chau, Duen Horng (Polo) (Georgia Institute of Technology, 2013)
      Given a large graph with millions of nodes and edges, say a social graph where both the nodes and edges can have multiple different kinds of attributes (e.g., job titles, tie strengths), how do we quickly find matches ...

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology