Differential co-expression signifies the deregulated pathways as opposed to differential expression that signifies change of gene expression. Kostka and Spang proposed a score and an algorithm to elicit differentially co-expressed gene-sets. We analyze the statistical properties of their score in two different data processing settings and obtain respective null-distributions to provide the statistical significance of a gene-set through the p-value of its score. We propose to use these p-values to automate their algorithm. In addition, we propose a two stage algorithm, based on Friendly Neighbors (FNs) algorithm, called FNs-KS algorithm for improved discovery of such gene set i.e. improves both sensitivity and specificity of the discovery.