Sie sind hier

# Algorithmic Explorations Between Cliques and 2-Clubs

Mervin Triphaus (Master Thesis Defence TU Berlin)



The search of internally dense subgraphs, so-called clusters, in network structures is for several decades an internationally established discipline in applied informatics. It is applied in various domains like bioinformatics to detect clusters in so-called Protein-Protein interaction networks (PPI networks), in telecommunications to detect interference between links in wireless networks or also in detecting communities in social networks. One approach of defining clusters are t-robust 2-clubs. These are subgraphs of diameter two which have t-many paths of length at most two between each vertex pair. The edge density of t-robust 2-clubs depends on the size of the subgraph itself. In order to remove this dependency, γ-relative robust 2-clubs were defined. They are a variation of t-robust 2-clubs, where the required number of paths is parameterized by γ, relative to the amount of vertices in the subgraph. In this thesis we studied structural properties of γ-relative robust 2-clubs and developed a fixed parameter tractable (FPT) algorithm to detect these subgraphs. Furthermore we developed a method to separate the graph into multiple subgraphs. Our experiments show that our algorithm performs well if these subgraphs are small.

Date
Speaker
Location
Language
02.09.2019
14:00
Mervin Triphaus
TEL 512
English

Back to the research colloquium site.

To top