Multi-clustering Gives Robustness to Modules in Networks

Abstract

Aims/ Objectives: A protein-protein interaction network is considered as a simple indirected graph, weighted or non weighted. A partition of the vertex set, into connected, eventually overlapping, clusters having an edge density larger than the whole graph, is searched. Such a cluster is denoted as a module. The cellular functionality of proteins is predicted from this network decomposition. To improve the prediction quality, we need to evaluate the robustness of these modules. Methodology: We propose a new method which consists in: selecting a non deterministic algorithm for graph partitioning into separate clusters (optimizing a modularity criterion);  applying this algorithm several times to generate a set of close partitions; calculating a consensus partition from this set. Results: This set of partitions permits to evaluate the robustness of any class as the average percentage of partitions joining any protein pair in this class. This robustness function can be applied to compare the consensus partition resulting of this procedure to the usually single partition computed from the graph. Then, we develop a simulation protocol selecting random graphs having a more or less strong community structure. We show that the multi-clustering method provides modules closer to the communities which are more robust than those of a single partition. Finally, we present a simple procedure to extend a strict partition into an overlapping class system, making multi assignment for proteins that could be placed equally into several modules, because their contributions to modularity are similar.