Bojan Evkoski successfully defended his master’s degree titled Community evolution analysis with Ensemble Louvain.
Complex networks, or simply networks, are robust structures for representing relationships between entities (nodes) connected in nontrivial ways. These networks can be used to model many types of relationships and processes in physical, biological, social, and information systems. A valuable aspect of network analysis is the identification of strongly connected groups, as this allows the creation of a large-scale map of a system. These groups are called communities and often provide information about the function of the system represented by the network.
The expansion of data popularized the field of network analysis and opened up the possibility of closely observing the represented processes in a temporal manner. Temporal analysis of communities is known as community evolution and aims to detect and explain changes in the collective behaviour of groups. It can be a precious tool in answering many phenomena, especially for social networks, such as economical or political shifts, measuring the influence of topics in forming and dissolving communities, the evolution of echo chambers, etc.
In this thesis, we present two contributions to the field of community detection and evolution. The first is a community detection method named Ensemble Louvain, which produces stable communities with high quality, suitable for evolution analysis. It uses ensembles of a famous community detection algorithm, significantly outperforming it and other ensemble methods that utilize it.
The second contribution is a novel strategy for using artificial networks for community detection benchmarking. The Lancichinetti-Fortunato-Radicchi (LFR) benchmark is the most widely accepted algorithm for generating artificial networks that resemble real-world networks. In the commonly used setting, the diversity of LFR networks is limited. Because the performance of community detection algorithms can vary depending on other network properties, conclusions based on a single set of LFR parameter values can be misleading. Therefore, we propose a comprehensive benchmarking of community detection algorithms that avoids the shortcomings of the standard LFR benchmarking, called the Unconstrained LFR benchmark.
Finally, we present three of our published works where we apply our Ensemble Louvain on a real-world dynamic social network, gaining insight into the development of Twitter communities. We observe the communities by analyzing the evolution of their influential users, discussion topics, and hate speech use. With this, we show a clear example of how community evolution can be used in applied quantitative research in the interdisciplinary field of complex networks.