Local k-core clustering for gene networks

The k-core of a graph is the maximal subgraph with minimum vertex degree k. When the core with the largest k is found, it can be removed and the next core can be found. In each of these cores (or shells), connected components have been enumerated in an existing graph clustering method. Here we propose a method to find graph clusters that are not just k-cores but also made of r-cliques. Just like the existing k-core clustering approach, our approach is also based on vertex and edge removals that can be made completely using local information (within the neighborhood). Our local and recursive algorithms are based on new graph theoretical insights that relate concepts including neighborhood, clique percolation, and k-core. We demonstrate our method with a gene network from PubMed data and compare our results with that from the existing k-core approach and use MeSH and TF-IDF ranking to show the differences in subject enrichment our approach can make.