Dense Temporal Subgraphs in Protein-Protein Interaction Networks

Temporal networks have been successfully applied to represent the dynamics of protein-protein interactions. In this paper we focus on the identification of dense subgraphs in temporal protein-protein interaction networks, a relevant problem to find group of proteins related to a given functionality. We consider a drawback of an existing approach for this problem that produce large time intervals over which temporal subgraphs are defined. We propose a problem to deal with this issue and we design (1) an exact algorithm based on dynamic programming which solves the problem in polynomial time and (2) a heuristic, based on a segmentation of the time domain and the computation of a refinement. The experimental results we present on seven protein-protein interaction networks show that in many cases our heuristic is able to reduce the time intervals with respect to those computed by the existing methods.