TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 07.05.2014


Page Content

to Navigation

Clustering with the Core-Periphery Model

Dr. Falk Hüffner (TU Berlin)

In graph-based clustering, it is generally assumed that each cluster is a dense subgraph. However, in many applications, a cluster is better described by the core-periphery model: it has a dense core and a sparse periphery that is connected mostly to the core. We formalize clustering under this model as finding the minimum number of edge insertions and deletions such that each connected component in the resulting graph is a split graph, that is, a graph that can be partitioned into a clique (core) and an independent set (periphery). We show hardness and propose several algorithms, based on a forbidden subgraph characterizationm, Integer Linear Programming, and simulated annealing. We present some preliminary experiments with protein interaction networks.

Joint work with Sharon Bruckner (FU Berlin) and Christian Komusiewicz (TU Berlin).

07.05.2014 16:15
Falk Hüffner
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe