Linear Clustering Process on Networks

Abstract

Community detection and graph partitioning have seamlessly integrated themselves into the fabric of network science by providing valuable insights into the structure, function, and dynamics of complex networks. In this thesis, a comprehensive performance comparison of the recently introduced Linear Clustering Process (LCP) is carried out against well-established clustering algorithms from literature. We evaluate its effectiveness using synthetic benchmarks commonly employed in the field, as well as real-world networks with both known and unknown community structures. Through our analysis, we reveal that the Linear Clustering Process consistently yields superior community partitions with optimized modularity when the clusters are well-defined compared to the majority of the assessed algorithms. Meanwhile, remarkably, this improved performance is achieved while maintaining computational complexity comparable to the simplest existing clustering algorithms. Furthermore, this thesis also provides an empirical approach for enhancing the performance of a variant of Linear Clustering Process on power-law networks.