Semantic service composition is an important issue in web service based systems. It is about how to build a new, reusable and value-added service by combining existing semantic web services. In this paper we propose a new hyper-graph based method supporting semantic service composition, which model the service composition problem as a hyper-graph. Then the hyper-graph based service composition algorithm has been implemented and evaluated. The evaluation results have shown that the method can effectively reduce the composition time and has good robustness, especially in the case of large number of web services and concepts.