A parallel graph sampling algorithm for analyzing gene correlation networks

Kathryn Dempsey, Kanimathi Duraisamy, Hesham Ali, Sanjukta Bhowmick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations


Efficient analysis of complex networks is often a challenging task due to its large size and the noise inherent in the system. One popular method of overcoming this problem is through graph sampling, that is extracting a representative subgraph from the larger network. The accuracy of the sample is validated by comparing the combinatorial properties of the subgraph and the original network. However, there has been little study in comparing networks based on the applications that they represent. Furthermore, sampling methods are generally applied agnostically, without mapping to the requirements of the underlying analysis. In this paper,we introduce a parallel graph sampling algorithm focusing on gene correlation networks. Densely connected subgraphs indicate important functional units of gene products. In our sampling algorithm, we emphasize maintaining highly connected regions of the network through parallel sampling based on extracting the maximal chordal subgraph of the network. We validate our methods by comparing both combinatorial properties and functional units of the subgraphs and larger networks. Our results show that even with significant reduction of the network (on average 20% to 40%), we obtain reliable samplings and many of the relevant combinatorial and functional properties are retained in the subgraphs.

Original languageEnglish (US)
Title of host publicationProcedia Computer Science
Number of pages10
StatePublished - 2011
Event11th International Conference on Computational Science, ICCS 2011 - Singapore, Singapore
Duration: Jun 1 2011Jun 3 2011


Other11th International Conference on Computational Science, ICCS 2011


  • Chordal graphs
  • Gene correlation networks
  • Parallel graph sampling

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'A parallel graph sampling algorithm for analyzing gene correlation networks'. Together they form a unique fingerprint.

Cite this