Dynamic Partitioning of Evolving Graph Streams Using Nature-Inspired Heuristics
No Thumbnail Available
Identifiers
Publication date
2019
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Verlag
Citations
Export
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.
Description
Publisher Copyright: © 2019, Springer Nature Switzerland AG.
Type
Citation
Osaba , E , Bilbao , M N , Iglesias , A , Del Ser , J , Galvez , A , Fister , I & Fister , I 2019 , Dynamic Partitioning of Evolving Graph Streams Using Nature-Inspired Heuristics . in J M F Rodrigues , P J S Cardoso , J Monteiro , R Lam , V V Krzhizhanovskaya , M H Lees , P M A Sloot & J J Dongarra (eds) , Computational Science – ICCS 2019 - 19th International Conference, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 11538 LNCS , Springer Verlag , pp. 367-380 , 19th International Conference on Computational Science, ICCS 2019 , Faro , Portugal , 12/06/19 . https://doi.org/10.1007/978-3-030-22744-9_29
conference
conference