高连通子图的贪心挖掘算法

利用海量的生物网络数据发现功能模块越来越受到人们的重视,从蛋白质建模的网络图中挖掘高连通子图是其中一个很重要的问题,然而由于数据规模巨大,现有的算法在时间效率上无法胜任实际的应用需求。通过深入研究高连通图的性质定理,设计了一个高连通子图的贪心挖掘算法（HCSGM）算法,在时间复杂度上比HCS算法提高了一个数量级。实验结果表明,HCSGM算法在仿真数据上的挖掘结果优于HCS算法,并且能够从大规模网络图中快速地进行高连通子图挖掘,从而高效地从蛋白质相互作用数据库中挖掘出功能模块。

A Greedy Mining Algorithm for Highly Connected Subgraphs

The rapid accumulation of biological network data translates into an urgent need for computational methods of graph-based graph mining.One important problem is to identify highly connected subgraphs from network to discover functional modules.This paper explores several properties related to highly connected graph.Based on these properties,a novel algorithm,HCSGM is developed,for more efficiently mining highly connected subgraphs,which outperforms the HCS algorithm in running time.Finally,the performance of...