To solve the problem of optimally deploy software applications on the offered infrastructure in the cloud, an optimization for graph partitioning algorithms are proposed. Firstly, this paper mathematical modeling the problem proposed. Then, researches three algorithms for this problem by minimizing the network usage. Finally, the evaluation results are presented on graphs generated by Eppstein power law generator. The results show that the algorithms proposed can optimize software deployment effectively in mobile cloud computing environment and produce 10%–40% smaller graph cut sizes than METIS 4.0 for typical mobile computing scenarios.