Abstract: The approach to build a complex network of web service was proposed. The Web services were used as nodes of the complex network in this method, and invocation relationship between Web services were regarded as the edges of the complex network. Service relationship of the Web service composition structure was researched by the network model. The key Web services were found in the numerous Web services, and at the same time the robustness and reliability of composite services had been enhanced. The experimental results indicated that the method was correct and effective, while the proposed approach was helpful to shift the research of Web services from the traditional SOA model to a complex network model. It is also instructive for further research on Web service composition.