RT Conference Proceedings
T1 Dynamic Partitioning of Evolving Graph Streams Using Nature-Inspired Heuristics
A1 Osaba, Eneko
A1 Bilbao, Miren Nekane
A1 Iglesias, Andres
A1 Del Ser, Javier
A1 Galvez, Akemi
A1 Fister, Iztok
A1 Fister, Iztok
A2 Rodrigues, João M.F.
A2 Cardoso, Pedro J.S.
A2 Monteiro, Jânio
A2 Lam, Roberto
A2 Krzhizhanovskaya, Valeria V.
A2 Lees, Michael H.
A2 Sloot, Peter M.A.
A2 Dongarra, Jack J.
AB 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.
PB Springer Verlag
SN 9783030227432
SN 0302-9743
YR 2019
FD 2019
LK https://hdl.handle.net/11556/2639
UL https://hdl.handle.net/11556/2639
LA eng
NO 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
NO conference
NO Publisher Copyright: © 2019, Springer Nature Switzerland AG.
NO Acknowledgements. E. Osaba and J. Del Ser would like to thank the Basque Government for its funding support through the EMAITEK program. A. Iglesias and A. Galvez acknowledge the financial support from the projects TIN2017-89275-R (AEI/FEDER, UE) and PDE-GIR (H2020, MSCA program, ref. 778035). Iztok Fister and Iztok Fister Jr. acknowledge the financial support from the Slovenian Research Agency (Research Core Founding No. P2-0041 and P2-0057).
DS TECNALIA Publications
RD 28 jul 2024