Detecting dense subgraphs in complex networks based on edge density coefficient

Densely connected patterns in biological networks can help biologists to elucidate meaningful insights. How to detect dense subgraphs effectively and quickly has been an urgent challenge in recent years. In this paper, we proposed a local measure named the edge density coefficient, which could indicate whether an edge locates a dense subgraph or not. Simulation results showed that this measure could improve both the accuracy and speed in detecting dense subgraphs. Thus, the G-N algorithm can be extended to large biological networks by this local measure. Finally, we applied this algorithm to microarray data sets of Saccharomyces cerevisiae, and performed the gene ontology analysis of the result by the GOEAST.