Mining Frequent Dense Subgraphs based on Extending Vertices from Unbalanced PPI Networks

The prediction of protein function is one of the problems arising in the recent progress in bioinformatics. A common used approach is to derive clusters from PPI dataset. However, such results often contain false positives. In this study, we propose a novel algorithm, EVDENSE, to efficiently mine frequent dense subgraphs from PPI networks. Instead of using summary graph, EVDENSE produces frequent dense patterns by extending vertices. Due to the unbalance character of PPI network, we also propose to generate frequent patterns using relative support. Through dealing with the 4 PPI datasets, the experiments show our method is efficiently. With the help of relative support, more frequent dense functional interaction patterns in the PPI networks can be identified.