TY - GEN
T1 - Combining bio-inspired meta-heuristics and novelty search for community detection over evolving graph streams
AU - Osaba, Eneko
AU - Camacho, David
AU - Ser, Javier Del
AU - Galvez, Akemi
AU - Panizo, Angel
AU - Iglesias, Andres
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/7/13
Y1 - 2019/7/13
N2 - Finding communities of interrelated nodes is a learning task that often holds in problems that can be modeled as a graph. In any case, detecting an optimal partition in a graph is highly time-consuming and complex. For this reason, the implementation of search-based metaheuristics arises as an alternative for addressing these problems. This manuscript focuses on optimally partitioning dynamic network instances, in which the connections between vertices change dynamically along time. Specifically, the application of Novelty Search mechanism for solving the problem of finding communities in dynamic networks is studied in this paper. For this goal, this procedure has been embedded in the search process undertaken by three different bio-inspired meta-heuristic schemes: Bat Algorithm, Firefly Algorithm and Particle Swarm Optimization. All these methods have been properly adapted for dealing with this discrete and dynamic problem, using a reformulated expression of the modularity coefficient as its fitness function. A thorough experimentation has been conducted using a benchmark composed by 12 synthetically created instances, with the main objective of analyzing the performance of the proposed Novelty Search mechanism when facing this problem. In light of the outperforming behavior of our approach and its relevance dictated by two different statistical tests, we conclude that Novelty Search is a promising procedure for finding communities in evolving graph data.
AB - Finding communities of interrelated nodes is a learning task that often holds in problems that can be modeled as a graph. In any case, detecting an optimal partition in a graph is highly time-consuming and complex. For this reason, the implementation of search-based metaheuristics arises as an alternative for addressing these problems. This manuscript focuses on optimally partitioning dynamic network instances, in which the connections between vertices change dynamically along time. Specifically, the application of Novelty Search mechanism for solving the problem of finding communities in dynamic networks is studied in this paper. For this goal, this procedure has been embedded in the search process undertaken by three different bio-inspired meta-heuristic schemes: Bat Algorithm, Firefly Algorithm and Particle Swarm Optimization. All these methods have been properly adapted for dealing with this discrete and dynamic problem, using a reformulated expression of the modularity coefficient as its fitness function. A thorough experimentation has been conducted using a benchmark composed by 12 synthetically created instances, with the main objective of analyzing the performance of the proposed Novelty Search mechanism when facing this problem. In light of the outperforming behavior of our approach and its relevance dictated by two different statistical tests, we conclude that Novelty Search is a promising procedure for finding communities in evolving graph data.
KW - Bio-inspired computation
KW - Community Detection
KW - Evolving Graphic Streams
KW - Novelty Search
UR - http://www.scopus.com/inward/record.url?scp=85070654968&partnerID=8YFLogxK
U2 - 10.1145/3319619.3326831
DO - 10.1145/3319619.3326831
M3 - Conference contribution
AN - SCOPUS:85070654968
T3 - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
SP - 1329
EP - 1335
BT - GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery, Inc
T2 - 2019 Genetic and Evolutionary Computation Conference, GECCO 2019
Y2 - 13 July 2019 through 17 July 2019
ER -