HOCTracker: Tracking the Evolution of Hierarchical and Overlapping Communities in Dynamic Social Networks

In this paper, we propose a unified framework, HOCTracker, for tracking the evolution of hierarchical and overlapping communities in online social networks. Unlike most of the dynamic community detection methods, HOCTracker adapts a preliminary community structure towards dynamic changes in social networks using a novel density-based approach for detecting overlapping community structures, and automatically tracks evolutionary events like birth, growth, contraction, merge, split, and death of communities. It uses a novel and efficient log-based approach to map evolutionary relations between communities identified at two consecutive time-steps of a dynamic network, which considerably reduces the number of community comparisons. Moreover, it does not require an ageing function to remove old interactions for identifying community evolutionary events. HOCTracker is applicable to directed/undirected and weighted/unweighted networks. Experimental results have shown that community structures identified by HOCTracker on some well-known benchmark networks are significant and in general better that the community structures identified by the state-of-the-art methods.