Finding cliques in protein interaction networks via transitive closure of a weighted graph

Finding protein functional modules in protein interaction networks amounts to finding densely connected subgraphs. Standard methods such as cliques and k-cores produce very small subgraphs due to highly sparse connections in most protein networks. Furthermore, standard methods are not applicable on weighted protein networks. We propose a method to identify cliques on weighted graphs. To overcome the sparsity problem, we introduce the concept of transitive closure on weighted graphs which is based on enforcing a transitive affinity inequality on the connection weights, and an algorithm to compute them. Using protein network from TAP-MS experiment on yeast, we discover a large number of cliques that are densely connected protein modules, with clear biological meanings as shown on Gene Ontology analysis.