Gene Co-expression Network (GCN) analysis has been widely used for gene function and disease biomarker discovery. In this study, we present a workflow for identifying GCN associated with colon cancer metastasis. The workflow includes dense network discovery from weighted GCN followed by network activity analysis using a mutual information-based approach to identify gene networks related to metastasis. Our findings suggest several genomic regions as genetic aberrations related to colon cancer malignancy including chr11q13, 20q13, 8q24 and 14q22-23. Our work also demonstrates a novel way of interpreting gene co-expression analysis results besides functional relationships and the effectiveness of the mutual information based network analysis in detecting subtle changes between different disease states.