DyLPA: a dynamic label propagation algorithm for detecting evolving communities

Networks and the corresponding techniques have attracted a lot of attention due to their powerful ability to model complex data. Community detection is a fundamental task but not well solved. Many existing community detection approaches focus on detecting communities for static networks while most of the networks in the real world are evolving continuously, for instance, the service social network. It delineates complex social collaboration and competition relationships among services, which is a special type of complex network. Service social networks share some fundamental properties with social networks, but also have some special properties, such as continuous-changing, which is not well presented or paid enough attention in current network researches. In this paper, we propose Dynamic Label Propagation Algorithm (DyLPA) to tackle the above properties. By introducing two-step propagation (local propagation and global propagation) and weight decaying mechanism, DyLPA can detect community structure time-continuously and effectively while it takes acceptable cost of time. We conducted extensive experiments on controllable synthetic data, and a case study on a real service social network to illustrate the effectiveness and generalizability of DyLPA. The results show that DyLPA is superior to the compared community detection approaches in several metrics. Furthermore, ablation studies are conducted to demonstrate the effects of global propagation in DyLPA.