Thesis Examination: MSc Student Kushagra Trivedi

Wed. Nov. 20 09:00 AM - Wed. Nov. 20 11:00 AM
Contact: Dylan Armitage
Location: Room 1RC028

Kushagra Trivedi - MSc Student in Applied Computer Science and Society

OVERLAPPING COMMUNITY DETECTION IN SOCIAL NETWORKS WITH VORONOI AND TOLERANCE NEIGHBOURHOOD-BASED METHOD

Community detection is typically viewed as a graph clustering problem with early detection algorithms focused on detecting non-overlapping communities and formulating various measures and optimization methods to evaluate the quality of clustering. In recent years, overlapping community detection especially in real-world social networks, has become an important and challenging research area since it introduces the possibility of membership of a vertex in more than one community. Overlapping community detection by its definition implies soft clustering and leads to an ideal application of granular computing methods. In this thesis, we propose a novel graph clustering algorithm for social networks using a hybrid computational geometry approach with Voronoi diagrams and tolerance-based neighborhoods (VTNM) to detect overlapping communities. Voronoi partitioning results in a crisp partition of an Euclidean space and a tolerance relation makes it possible to obtain soft partitions. A Voronoi diagram is a method to partition a plane into regions based on nearness to points in a specific set of sites (seeds). In the VTNM approach, these seeds are used as cores for determining tolerance neighborhoods via a non-transitive binary relation. The intersection of these neighborhoods are used to discover overlapping communities. We present empirical evidence on the performance of our proposed VTNM algorithm by comparing with eleven widely popular community detection methods on seven different real-world data sets. Our proposed VTNM algorithm shows promising results in terms of the Extended Modularity measure, Average F1-score and Normalized Mutual Information (NMI) measure.