Protein communities detection optimization through an improved Parallel Newman-Girvan algorithm

Proteins and the networks they determine, called interactome networks, have received attention at an important degree during the last years, because they have been discovered to have an influence on some complex biological phenomena, such as problematic disorders like cancer. This paper presents a contribution that aims to optimize the Newman-Girvan community detection algorithm through a parallel implementation that is based on the MPI C programming environment. The optimization involves a double improvement of the original Newman-Girvan algorithm, which is accomplished both at the algorithmic and programming level. The resulting parallel implementation´s performance was carefully tested on real biological data and the results acknowledge the relevant speedup that the optimization determines. Moreover, the results are in line with the previous findings that our current research produced, as it reveals and confirms the existence of some important properties of those proteins that participate in the carcinogenesis process. Apart from being particularly useful for research purposes, the novel technique also speeds up the proteomic databases analysis process, as compared to some of the sequential community detection approaches, and also to the original sequential Newman-Girvan algorithm.