Uncovering the Structure of Heterogenous Biological Data: Fuzzy Graph Partitioning in the k-partite Setting

With the increasing a availability of large-scale interaction networks derived eitther from experimental data or from text mining, we face the challenge of interpreting and analyzing these data sets in a comprehensive fashion. A particularity of these networks, which sets it apart from other examples in various scientific fields lies in their k-partiteness. Whereas graph partitioning has received considerable attention, only few researchers have focused on this generalized situation. Recently, Long et al. Have proposed a method for jointly clustering such a network and at the same time estimating a weighted graph connecting the clusters thereby allowing simple interpretation of the resulting clustering structure. In this contribution, we extend this work by allowing fuzzy clusters for each node type. We propose an extended cost function for partitioning that allows for overlapping clusters. Our main contribution lies in employed in algorithms for non-negativ matrix factorization. Results on clustering a manually annotated bipartite gene-complex graph show signigiantly higher homogeneity beween gene and corresponding complex clusters than expected by chance.