Abstract: Service discovery is a hot topic in the field of services computing. As compared to classic methods that focus on service contents, this paper presents a new approach from the viewpoint of interconnectivity, to find important services and the corresponding composable services based on previous records of service composition. Empirical results show that (1) 95% of mashups on the website ProgrammableWeb contain important Web APIs discovered by our approach, and (2) the rate of success for analyzing the composability of a given set of Web APIs runs up to 98%. Thus, this approach would be helpful for effectively searching and recommending services on the Internet.