Presentation
Poster 30: A Fast and Efficient Incremental Approach toward Dynamic Community Detection
Event Type
ACM Student Research Competition: Graduate Posters
ACM Student Research Competition: Undergraduate Posters
Posters
TP
EX
EXH
Student Program
TimeThursday, 21 November 20198:30am - 5pm
LocationE Concourse
DescriptionCommunity 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.
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.
Archive