Extensive and  automated data integration in bioinformatics facilitates the construction of complex biological networks. The challenge lies in the interpretation of these networks. While common methods mostly focus on the uni- or at most bipartite case, we address the more general situation of k-partite graphs with k node types and edges only allowed between different ones. To reveal their structural organization and compress the contained information in a more corse-grained fashion we asked how to detect clusters within each node type. Since nodes in biological graphs often participate in more than one cluster, we developed a fast and efficient k-partite graph clustering algorithm that allows for overlapping (fuzzy) clusters. It is based on multiplicative update rules commonly used in non-negative matrix factorization. We provide a MATLAB implementation and also code for the generation of modularly structured example graphs.


Fuzzy k-partite graph clustering algorithm for MATLAB:

Fuzzy k-partite graph clustering algorithm for Octave:

Generation of modular k-partite networks:


  • Florian Blöchl, Mara L. Hartsperger, Volker Stümpflen, Fabian J. Theis,
    'Uncovering the structure of heterogeneous biological data: fuzzy graph partitioning in the k-partite setting'.
    In Proc. GCB 2010, volume 173 of LNI, pages 31-40, 2010 [link]

  • Mara L. Hartsperger, Florian Blöchl, Volker Stümpflen, Fabian J. Theis,
    'Structuring heterogeneous biological information using fuzzy clustering of k-partite graphs'.
    BMC Bioinformatics 11:522, 2010. [link]