Community detection in graphs based on surprise maximization using firefly heuristics
No Thumbnail Available
Identifiers
Publication date
2016-11-14
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers Inc.
Citations
Export
Abstract
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.
Description
Publisher Copyright: © 2016 IEEE.
Type
Citation
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
conference
conference