Title :
A Clustering Algorithm for Mining Overlapping Highly Connected Subgraphs
Author :
Lin, Xiahong ; Gao, Lin ; Chen, Kefei
Abstract :
In this paper, we give several properties related to highly connected graph. Based on these properties, we give a redefinition of highly connected subgraph which results in an algorithm for determining whether a given graph is highly connected in linear time. Then we present a computationally efficient algorithm, called MOHCS, for mining overlapping highly connected subgraphs. We experimentally evaluate the performance of MOHCS using a variety of real and synthetic data sets. Our results show that MOHCS is effective in finding overlapping highly connected subgraphs both in computer- generated graph and yeast protein network.
Keywords :
biology computing; data mining; graph theory; pattern clustering; proteins; MOHCS algorithm; clustering algorithm; data mining; highly connected subgraph; yeast protein network; Algorithm design and analysis; Clustering algorithms; Computer networks; Computer science; Fungi; Gene expression; Greedy algorithms; Large-scale systems; Partitioning algorithms; Proteins;
Conference_Titel :
Bioinformatics and Biomedical Engineering, 2008. ICBBE 2008. The 2nd International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-1747-6
Electronic_ISBN :
978-1-4244-1748-3
DOI :
10.1109/ICBBE.2008.127
