## Abstract

Detecting communities of interconnected nodes is a frequently addressed problem in situation that be modeled as a graph. A common practical example is this arising from Social Networks. Anyway, detecting an optimal partition in a network is an extremely complex and highly time-consuming task. This way, the development and application of meta-heuristic solvers emerges as a promising alternative for dealing with these problems. The research presented in this paper deals with the optimal partitioning of graph instances, in the special cases in which connections among nodes change dynamically along the time horizon. This specific case of networks is less addressed in the literature than its counterparts. For efficiently solving such problem, we have modeled and implements a set of meta-heuristic solvers, all of them inspired by different processes and phenomena observed in Nature. Concretely, considered approaches are Water Cycle Algorithm, Bat Algorithm, Firefly Algorithm and Particle Swarm Optimization. All these methods have been adapted for properly dealing with this discrete and dynamic problem, using a reformulated expression for the well-known modularity formula as fitness function. A thorough experimentation has been carried out over a set of 12 synthetically generated dynamic graph instances, with the main goal of concluding which of the aforementioned solvers is the most appropriate one to deal with this challenging problem. Statistical tests have been conducted with the obtained results for rigorously concluding the Bat Algorithm and Firefly Algorithm outperform the rest of methods in terms of Normalized Mutual Information with respect to the true partition of the graph.

Original language | English |
---|---|

Title of host publication | Computational Science – ICCS 2019 - 19th International Conference, Proceedings |

Editors | João M.F. Rodrigues, Pedro J.S. Cardoso, Jânio Monteiro, Roberto Lam, Valeria V. Krzhizhanovskaya, Michael H. Lees, Peter M.A. Sloot, Jack J. Dongarra |

Publisher | Springer Verlag |

Pages | 367-380 |

Number of pages | 14 |

ISBN (Print) | 9783030227432 |

DOIs | |

Publication status | Published - 2019 |

Event | 19th International Conference on Computational Science, ICCS 2019 - Faro, Portugal Duration: 12 Jun 2019 → 14 Jun 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11538 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 19th International Conference on Computational Science, ICCS 2019 |
---|---|

Country/Territory | Portugal |

City | Faro |

Period | 12/06/19 → 14/06/19 |

## Keywords

- Bio-inspired computation
- Community detection
- Evolving graphic streams
- Nature-inspired heuristics