RT Conference Proceedings
T1 Community detection in weighted directed networks using nature-inspired heuristics
A1 Osaba, Eneko
A1 Del Ser, Javier
A1 Camacho, David
A1 Galvez, Akemi
A1 Iglesias, Andres
A1 Fister, Iztok
A1 Fister, Iztok
A2 Camacho, David
A2 Novais, Paulo
A2 Tallón-Ballesteros, Antonio J.
A2 Yin, Hujun
AB Finding groups from a set of interconnected nodes is a recurrent paradigm in a variety of practical problems that can be modeled as a graph, as those emerging from Social Networks. However, finding an optimal partition of a graph is a computationally complex task, calling for the development of approximative heuristics. In this regard, the work presented in this paper tackles the optimal partitioning of graph instances whose connections among nodes are directed and weighted, a scenario significantly less addressed in the literature than their unweighted, undirected counterparts. To efficiently solve this problem, we design several heuristic solvers inspired by different processes and phenomena observed in Nature (namely, Water Cycle Algorithm, Firefly Algorithm, an Evolutionary Simulated Annealing and a Population based Variable Neighborhood Search), all resorting to a reformulated expression for the well-known modularity function to account for the direction and weight of edges within the graph. Extensive simulations are run over a set of synthetically generated graph instances, aimed at elucidating the comparative performance of the aforementioned solvers under different graph sizes and levels of intra- and inter-connectivity among node groups. We statistically verify that the approach relying on the Water Cycle Algorithm outperforms the rest of heuristic methods in terms of Normalized Mutual Information with respect to the true partition of the graph.
PB Springer Verlag
SN 9783030034955
SN 0302-9743
YR 2018
FD 2018
LK https://hdl.handle.net/11556/1941
UL https://hdl.handle.net/11556/1941
LA eng
NO Osaba , E , Del Ser , J , Camacho , D , Galvez , A , Iglesias , A , Fister , I & Fister , I 2018 , Community detection in weighted directed networks using nature-inspired heuristics . in D Camacho , P Novais , A J Tallón-Ballesteros & H Yin (eds) , Intelligent Data Engineering and Automated Learning – IDEAL 2018 - 19th International Conference, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 11315 LNCS , Springer Verlag , pp. 325-335 , 19th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2018 , Madrid , Spain , 21/11/18 . https://doi.org/10.1007/978-3-030-03496-2_36
NO conference
NO Publisher Copyright: © Springer Nature Switzerland AG 2018.
NO Acknowledgements. E. Osaba and J. Del Ser would like to thank the Basque Government for its funding support through the EMAITEK program. I. Fister Jr. and I. Fister acknowledge the financial support from the Slovenian Research Agency (Research Core Fundings No. P2-0041 and P2-0057). A. Iglesias and A. Galvez acknowledge the financial support from the projects TIN2017-89275-R (AEI/FEDER, UE), PDE-GIR (H2020, MSCA program, ref. 778035), and JU12 (SODERCAN/FEDER UE). E. Osaba and J. Del Ser would like to thank the Basque Government for its funding support through the EMAITEK program. I. Fister Jr. and I. Fister acknowledge the financial support from the Slovenian Research Agency (Research Core Fundings No. P2-0041 and P2-0057). A. Iglesias and A. Galvez acknowledge the financial support from the projects TIN2017-89275-R (AEI/FEDER, UE), PDE-GIR (H2020, MSCA program, ref. 778035), and JU12 (SODERCAN/FEDER UE).
DS TECNALIA Publications
RD 28 jul 2024