Community detection on time-evolving graphs

Community detection in graphs is a fundamental task in network analysis, aimed at identifying clusters of densely connected nodes. It has applications in many fields, such as social media, biological systems and cybersecurity. While traditional methods focus on static graphs, many real-world networks are dynamic, with evolving structures and community memberships. This thesis addresses the challenge of dynamic community detection, proposing a semi-supervised approach. In this context, semi-supervision means leveraging both graph structure and knowledge of part of ground truth communities in order to infer those in the remaining part of the graph. Therefore, in a dynamic setting, we have a graph evolving for many timesteps and, in each time instant, we know part of the ground-truth communities. Though the real communities we are informed of may differ from time to time, the addition of this information helps improving accuracy and robustness of algorithms. We firstly address the problem of the scarcity of dynamic network data with labeled communities, which are crucial benchmarks in this field. In order not to rely just on synthetic data, we propose a new semi-synthetic dynamic network generator. This algorithm allows to generate dynamic networks with community labels by starting from a real static graph. Therefore, it gives the opportunity to test algorithms on data with a synthetic dynamic dimension, but based on the topology of a real existing static network. Subsequently, we focus our attention on algorithms for community detection. Existing methods are either dynamic but not semi-supervised or semi-supervised but static, therefore this thesis aims to start a new research branch: dynamic semi-supervised community detection. In order to implement algorithms performing this novel task, we extend and adapt existing methods from related fields and consider them as baselines. The proposed techniques are evaluated on both synthetic and semi-synthetic datasets. Finally, we introduce architectural improvements on the best performing baseline, analyzing both their theoretical background and the performance enhancements they bring. The outcomes emphasize the benefits of integrating semi-supervised techniques with time-aware algorithms for more precise and insightful community detection in evolving networks. This work lays the foundation for future research in community detection, with potential applications across various domains where understanding the temporal evolution of partially annotated graph networks is crucial.