Mining Dense Subgraphs In Complex Biological Networks

The frequent patterns in biological networks play an important role to reveal the function of organism, the evolution and the disease. However, the traditional clustering algorithms of complex networks have high time complexity when applied to biological networks, because of its size. It's an urgent challenge for the methods for detecting dense subgraphs across massive biological networks.This paper proposes a new local measure of edges in complex networks, we called edge dense coefficient, which can be used to identify whether the edge is located inside the dense subgraph or not. There is a better anti-correlation exists between edge dense coefficient and edge betweenness. It is clear that the method based on edge dense coefficient can reduce the computational complexity on mining dense subgraphs in single network because of its simple computation. Moreover, we propose a new algorithm of mining frequent dense vertex sets across a network set based on edge dense coefficient. Considering that a (group) frequent pattern(s) trend to be included in only one subset, we resolve this problem by two steps: detecting all the potential subsets and mining frequent dense vertex sets in every candidate. Thus, the main solutions of our algorithm are refining the summary graph iteratively, and then clustering the edges in the summary graph to capture the frequent dense vertex sets. Via the simulation experiments, it is demonstrated that this algorithm can mine the frequent dense vertex sets from massive biological networks easily, effectively and robustly.Finally, we integrated the gene expression datasets about the saccharomyces cerevisiae, and constructed 20 co-expression networks, each contain 5672 genes. Then we applied our algorithm to these co-expression networks, and performed the Gene Ontology analysis of the result by the GOEAST. The results show that the genes contained in the FDVS are enriched GO terms.