Detecting communities in biological bipartite networks

Abstract:

Methods to uncover and extract community structures are required in a number of biological applications where networked data and their interactions can be modeled as graphs, and observing tightly-knit groups of vertices ("communities") can offer insights into the structural and functional building blocks of the underlying network. While classical applications of community detection have focused largely on detecting molecular complexes from protein-protein networks and other similar graphs, there is an increasing need for extending the community detection operation to work for heterogeneous data sets - i.e., networks built out of multiple types of data. In this paper, we address the problem of identifying communities from biological bipartite networks - networks where interactions are observed between two different types of vertices (e.g., genes and diseases, drugs and protein complexes, plants and pollinators). Toward detecting communities in such bipartite networks, we make the following contributions: i) we define a variant of the bipartite modularity function defined by Murata to overcome one of its limitations; ii) we present an algorithm (biLouvain), building on an efficient heuristic that was originally developed for unipartite networks; and iii) we present a thorough experimental evaluation of our algorithm compared to other state-of-the-art methods to identify communities on bipartite networks. Experimental results show that our biLouvain algorithm identifies communities that have a comparable or better quality (bipartite modularity) than existing methods, while significantly reducing the time-to-solution between one and three orders of magnitude.

Año de publicación:

2016

Keywords:

• Community detection
• Graph algorithms
• Biological bipartite networks
• Heterogeneous biological data

Fuente:

scopus