Efficient Detection of Communities in Biological Bipartite Networks

Paola Pesantez-Cabrera; Ananth Kalyanaraman

doi:10.1109/TCBB.2017.2765319

Back

Efficient Detection of Communities in Biological Bipartite Networks

Journal article

Open access

Efficient Detection of Communities in Biological Bipartite Networks

Paola Pesantez-Cabrera and Ananth Kalyanaraman

IEEE/ACM transactions on computational biology and bioinformatics, Vol.16(1), pp.258-271

01/2019

DOI: https://doi.org/10.1109/TCBB.2017.2765319

Handle:

https://hdl.handle.net/2376/107007

PMID: 29990252

Files and links (1)

url

https://doi.org/10.1109/TCBB.2017.2765319View

Published (Version of record) Open

Abstract

Drugs

Heterogeneous biological data

Heuristic algorithms

Computational modeling

bipartite modularity

Biology

Data models

Heterogeneous networks

community detection

Diseases

bipartite networks

graph algorithms

Methods to efficiently 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. Classical applications of community detection have largely focused on unipartite networks - i.e., graphs built out of a single type of objects. However, due to increased availability of biological data from various sources, there is now an increasing need for handling heterogeneous networks which are built out of multiple types of objects. In this paper, we address the problem of identifying communities from biological bipartite networks - i.e., networks where interactions are observed between two different types of objects (e.g., genes and diseases, drugs and protein complexes, plants and pollinators, and hosts and pathogens). Toward detecting communities in such bipartite networks, we make the following contributions: i) ( metric ) we propose a variant of bipartite modularity; ii) ( algorithms ) we present an efficient algorithm called biLouvain that implements a set of heuristics toward fast and precise community detection in bipartite networks ( https://github.com/paolapesantez/biLouvain ); and iii) ( experiments ) we present a thorough experimental evaluation of our algorithm including comparison to other state-of-the-art methods to identify communities in bipartite networks. Experimental results show that our biLouvain algorithm identifies communities that have a comparable or better quality (as measured by bipartite modularity) than existing methods, while significantly reducing the time-to-solution between one and four orders of magnitude.

Metrics

6 Record Views

See more details

Details

Title: Efficient Detection of Communities in Biological Bipartite Networks
Creators: Paola Pesantez-Cabrera - Washington State University, Pullman, WA
Ananth Kalyanaraman - Washington State University, Pullman, WA
Publication Details: IEEE/ACM transactions on computational biology and bioinformatics, Vol.16(1), pp.258-271
Academic Unit: Electrical Engineering and Computer Science, School of
Publisher: IEEE
Grant note: Office of Science (10.13039/100006132) DE-SC-0006516 / US Department of Energy DE-AC02-05CH11231 / U.S. Department of Energy (10.13039/100000015) National Energy Research Scientific Computing Center DOE Office of Science User Facility
Identifiers: 99900546558101842
Language: English
Resource Type: Journal article