direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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).

Date
Speaker
Location
Language
07.05.2014 16:15
Falk Hüffner
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras