title: A graph modification approach for finding core-periphery structures in protein interaction networks.
abstract: The core-periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core-periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.
authors.affiliation: International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, Berlin, 14195 Germany.
authors.forename: Sharon
authors.initials: S
authors.lastname: Bruckner
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, Berlin, 10587 Germany.
authors.forename: Falk
authors.initials: F
authors.lastname: Hüffner
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, Berlin, 10587 Germany.
authors.forename: Christian
authors.initials: C
authors.lastname: Komusiewicz
keywords: Graph classes; NP-hard problems; Protein complexes