A comparison of community search with community detection

Kamath Pailodi, Vidya

Permalink

https://hdl.handle.net/2142/124272 Copy

Description

Title

A comparison of community search with community detection

Author(s)

Kamath Pailodi, Vidya

Issue Date

2024-04-25

Director of Research (if dissertation) or Advisor (if thesis)

Chacko, George

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

Networks, Clustering, Community Detection, Community Search, Scientometrics

Abstract

Clustering is a widely used technique to study the topological features of complex real-world networks. Community detection is a commonly used method that uses a top-down graph partitioning approach to often find disjoint subsets. These methods often produce a large fraction of singleton clusters, and the clusters do not typically form well-connected communities. They also face the resolution limit problem, which fails to identify communities of smaller sizes. Moreover, many of these methods cannot handle large networks. Recently, many studies have discussed the advantages of an efficient bottom-up approach called "Community Search", which extracts a community around a particular node of interest. In this thesis, we compare the Iterative K-Core (IKC) community detection algorithm and the Community Search k-core (CSK) method based on the principle of the minimum degree of a node in a cluster. A comparative study is conducted to discuss the advantages of the CSK method in addressing the limitations of community detection by applying these methods to a large scientific network of 14 million documents in exosome research, namely, the Curated Exosome Network (CEN). Our results demonstrate that the CSK extracts larger clusters than the IKC method for a given query node and are well-connected. CSK extracts more number of distinct clusters than IKC, and the extracted clusters typically overlap. Moreover, CSK allows a node to be part of multiple communities. Cluster quality metrics such as conductance, connectivity, and modularity showed correlations with CSK cluster sizes, which were not observed for IKC clusters. Finally, preliminary observations suggest that clustering based on topological features correlates with thematic similarity. Our observations suggest that CSK can be advantageous in generating cohesive clusters of varying sizes and cluster qualities, and helpful in exploring the topological structure surrounding a seed node in a complex real-world network.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Vidya Kamath Pailodi

Owning Collections