Supervisor: Ananth Kalyanaraman (Washington State University)
Abstract: Community detection is a discovery tool to identify groups of vertices which are tightly connected, called communities. Most of the literature on this subject caters to the static use-case where the underlying network does not change. However, many emerging real-world use-cases give rise to a need to incorporate dynamic graphs as inputs.
We present a fast and efficient incremental approach toward dynamic community detection. The key contribution is a generic technique called ∆-screening, which examines the most recent batch of changes made to an input graph and selects a subset of vertices to reevaluate for potential community (re)assignment. This technique can be incorporated into any of the community detection methods that use modularity as its objective function for clustering. For demonstration purposes, we incorporated the technique into two well-known community detection tools. Our experiments demonstrate that our approach is able to generate performance speedups without compromising on the output quality.
ACM-SRC Semi-Finalist: no
Poster Summary: PDF
Back to Poster Archive Listing