Community Tracking in Time Evolving Networks: An Evolutionary Multi-objective Approach

Abstract

In real world, almost all networks evolve over time. For example, in networks of friendships and acquaintances, people continually create and delete friendship relationship connections over time, thereby add and draw friends, and some people become part of new social networks or leave their networks, changing the nodes in the network. Recently, tracking communities encountering topological shifting drawn significant attentions and many successive algorithms have been proposed to model the problem. In general, evolutionary clustering can be defined as clustering data over time wherein two concepts: snapshot quality and temporal smoothness should be considered. Snapshot quality means that the clusters should be as precise as possible during the current time step. Temporal smoothness, on the other hand, means that the clusters should not changed dramatically between successive time steps. In this paper, a multi-objective optimization model, based on internal community density as snapshot metric, is proposed and compared with the state-of-the-art modularity based model. Both models are then used to solve the community tracking problem in dynamic social network. The problem, in both models, is stated as a multi-objective optimization problem and the decomposition based multi-objective evolutionary algorithm is used to solve the problem. Experimental results reveals that the proposed model significantly outperforms the already existing model in the ability of tracking more shifted communities.