Title

RnR: Reduce and Raise - Bottom-Up Community Detection in Bipartite and Tripartite Graphs

Abstract

Abstract

In this thesis, we propose a novel approach to solve the near-biclique detection and near-triclique detection problems. Finding cliques in graphs are proven to be NP-hard. There are various heuristics, and different approaches to deal with this problem. Our approach differs from the existing algorithms in a sense that it aims to find near-cliques that include nodes that are higher in degree not just in the clique but also in the whole graph. We make a trade-off between speed and quality, in favor of speed. In this thesis, we explain and compare seven novel algorithms, which are developed upon the existing algorithm, the popular Louvain method, which is a modularity-based community detection algorithm. The algorithms are tested using computer generated graphs. We observe that, our algorithms performs better for networks with dense regions and high sparsity values.

Biography:

Supervisor(s)

Supervisor(s)

KADIR EKMEKCI

Date and Location

Date and Location

2019-02-04;13:30:00-A101

Category

Category

MSc_Thesis