In cancer, deregulated signaling can produce an invasive cellular phenotype. We modeled the invasive transition as a theoretical switch between two cytoskeletal structures: focal adhesions and extracellular matrix-degrading invadopodia. We constructed molecular interaction networks of each structure and identified upstream regulatory hubs through computational analyses. We compared these regulatory hubs to the status of signaling components from head and neck carcinomas, which led us to analyze phosphatidylinositol 3-kinase (PI3K) and protein kinase C α (PKCα). Consistent with previous studies, PI3K activity promoted both the formation and the activity of invadopodia. We found that PI3K induction of invadopodia was increased by overexpression of SH2 (Src homology 2) domain-containing inositol 5'-phosphatase 2 (SHIP2), which converts the phosphatidylinositol 3,4,5-trisphosphate [PI(3,4,5)P(3)] that is produced by PI3K activity to phosphatidylinositol 3,4-bisphosphate [PI(3,4)P(2)], which is believed to promote invadopodia formation. Knockdown of PKCα had divergent effects on invadopodia formation, depending on the status of PI3K. Loss of PKCα inhibited invadopodia formation in cells with wild-type PI3K pathway status. Conversely, in cells with constitutively active PI3K (through activating PI3K mutants or lacking the endogenous opposing enzyme PTEN), PKCα knockdown increased invadopodia formation. Mechanistic studies revealed a negative feedback loop from PKCα that dampened PI3K activity and invasive behavior in cells with genetic hyperactivation of the PI3K pathway. These studies demonstrated the potential of network modeling as a discovery tool and identified PI3K and PKCα as interacting regulators of invasive behavior.