Background: Adenocarcinoma (AC) and squamous cell carcinoma (SCC) are the two most common subtypes of non-small cell lung carcinoma (NSCLC), and the cures for them are quite different from each other. Traditional morphological procedures could not effectively distinguish AC and SCC because of their morphologically similar cells.Objective: It is necessary to identify the genes which could effectively discriminate AC from SCC on the molecular level. Method: In this work, we apply the context likelihood of related algorithm to gene expression values to infer AC and SCC networks, respectively. We calculate the values of four centrality measures (the average degree, the average clustering coefficient, the average betwenness and the average coritivity) on both AC and SCC networks. The structural key genes are defined as the genes which make great contributions to the topological changes between two gene networks. Results: We find that the values of the average degree and the average coritivity of AC networks are much smaller than those of SCC networks. The degree and the coritivity are considered to be the effective measures to select structural key genes. We obtain 18 structural key genes, five of which have been previously identified as markers to distinguish between AC and SCC. Conclusion: Our results show that the structural key genes which are found by the effective measures may be used to distinguish the subtypes of NSCLC. The current method could be extended to other complex diseases for distinguishing subtypes and detecting the molecular targets for targeted therapy.