Finding Dense Regions of Rapidly Changing Graphs
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.
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 ...