Genetic Algorithms for Finding Episodes in Temporal Networks

The evolution of networks is a fundamental topic in network analysis and mining. One of the approaches that has been recently considered in this field is the analysis of temporal networks, where relations between elements can change over time. A relevant problem in the analysis of temporal networks is the identification of cohesive or dense subgraphs since they are related to communities. In this contribution, we present a method based on genetic algorithms and on a greedy heuristic to identify dense subgraphs in a temporal network. We present experimental results considering both synthetic and real-networks, and we analyze the performance of the proposed method when varying the size of the population and the number of generations. The experimental results show that our heuristic generally performs better in terms of quality of the solutions than the state-of-art method for this problem. On the other hand, the state-of-art method is faster, although comparable with our method, when the size of the population and the number of generations are limited to small values.