TSInc: Tie strength based incremental community detection using information cascades

Community detection in dynamic networks is of great importance in social network analysis. For instance, online social networks such as Facebook, WhatsApp and LinkedIn are rapidly evolving with time. However, the majority of previous research have focused on community detection in static networks. It is computationally expensive to repeatedly use a static algorithm on snapshots of dynamic networks. In this paper, we propose a community detection algorithm namely, Tie Strength based Incremental Community detection (TSInc), aiming to find communities and track the dynamic events in each snapshot. TSInc determines communities using tie strength based information cascades. Following the initial snapshot, we construct a new subgraph based on the dynamic events in the subsequent snapshots and quickly assign communities. These communities in combination with the unchanged communities are merged to obtain the inherent community structure. These procedure is repeated for the remaining snapshots as well. Experimental results on several real-world dynamic networks and state-of-the-art approaches shows that TSInc algorithm outperforms the baseline algorithms in terms of effectiveness of the detected communities.