A Multi-Objective Genetic Algorithm for detecting dynamic communities using a local search driven immigrant's scheme

doi:10.1016/j.future.2019.10.041

2020-09-01

PRE

Ángel Panizo-LLedot

Gema Bello-Orgaz

David Camacho *

DOI：10.1016/j.future.2019.10.041

原文链接

原文求助

摘要

En 中文

The interest in Community Detection Problems on networks that evolves over time has experienced an increasing attention over the last years. Multi-Objective Genetic Algorithms and other bio-inspired methods have been successfully applied to tackle the community finding problem in static networks. Although, there are a large number of evolutionary and bio-inspired approaches that combine Local Search Strategies and other techniques from graph theory to handle the community detection problems in static networks, few research has been done related to the application of these algorithms over temporal, or dynamic, networks. This work is focused on the design, implementation, and the empirical analysis of a new Multi-Objective Genetic Algorithm that combines an Immigrant's scheme with local search strategies for dynamic community detection. The main contribution of this new algorithm is to address the adaptation of these strategies to dynamic networks. On the one hand, the Immigrant's scheme motif is to reuse previously acquired information to reduce computational time. On the other hand, in a dynamic environment is possible that a valid solution became invalid due to some changes in the environment, for example, if some nodes or edges have been removed or added to the network. Therefore, the aim of the local search operator used in the new algorithm is to transform an invalid solution, due to a change happened on the network, into a valid one maintaining the highest possible quality. Finally, the proposed algorithm has been tested using several synthetic and real-world networks, and compared against several algorithms (DYNMOGA, ALPA, Infomap) from the state of the art. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Dynamic community finding

Multi-Objective Genetic algorithms

Graph computing

Network analysis