A comparison of community search with community detection

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Kamath Pailodi, Vidya

Contributors dc:contributor

• Chacko, George

• Networks
• Clustering
• Community Detection
• Community Search
• Scientometrics

Statement dc:rights

• Copyright 2024 Vidya Kamath Pailodi

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F124272