RT Conference Proceedings
T1 Community detection in graphs based on surprise maximization using firefly heuristics
A1 Del Ser, Javier
A1 Lobo, Jesus L.
A1 Villar-Rodriguez, Esther
A1 Bilbao, Miren Nekane
A1 Perfecto, Cristina
AB The detection of node clusters (communities) in graphs has been at the core of many modeling paradigms emerging in different fields and disciplines such as Social Sciences, Biology, Chemistry, Telecommunications and Linguistics. When evaluating the quality of a clustering arrangement unsupervised metrics can be utilized (e.g. modularity), which all rely on structural and topological characteristics of the cluster space rather than on an observed ground of truth that should be achieved. One of such metrics is the recently published Surprise, which evaluates how statistically unlikely a given clustering arrangement is with respect to a random network featuring the same distribution of nodes per cluster. To maximize this metric, a number of algorithms have been proposed in the literature, but their comparative performance varies significantly between networks of different shape and size. In this article a novel heuristic community detection approach is proposed as a means to achieve a universally well-performing tool for graph clustering based on Surprise maximization. The heuristic scheme relies on the search procedure of the so-called Firefly Algorithm, a nature-inspired meta-heuristic solver based on the collective behavior, mutual attractiveness and random yet controlled movement of these insects. The proposed technique emulates these observed behavioral patterns of fireflies in the genotype of the graph clustering problem rather than on an encoded representation of its search space (phenotype). Simulation results evince that the performance of our community detection scheme generalizes better than other schemes when applied over synthetically generated graphs with varying properties.
PB Institute of Electrical and Electronics Engineers Inc.
SN 9781509006229
YR 2016
FD 2016-11-14
LK https://hdl.handle.net/11556/2363
UL https://hdl.handle.net/11556/2363
LA eng
NO Del Ser , J , Lobo , J L , Villar-Rodriguez , E , Bilbao , M N & Perfecto , C 2016 , Community detection in graphs based on surprise maximization using firefly heuristics . in 2016 IEEE Congress on Evolutionary Computation, CEC 2016 . , 7744064 , 2016 IEEE Congress on Evolutionary Computation, CEC 2016 , Institute of Electrical and Electronics Engineers Inc. , pp. 2233-2239 , 2016 IEEE Congress on Evolutionary Computation, CEC 2016 , Vancouver , Canada , 24/07/16 . https://doi.org/10.1109/CEC.2016.7744064
NO conference
NO Publisher Copyright: © 2016 IEEE.
DS TECNALIA Publications
RD 2 sept 2024