Abstract: With the rapid increasing number of services and their types, how to discover the composible services which can meet uer’s requirements is one of the key issues that need to be resolved. Service recommendation technique has become one of the effective methods to deal with the problem of service resource overload. However, the existing service recommendation techniques usually ultilize service data which are hard to be collected and they also neglect the usability and composiblity of the services to be recommended. To avoid these limitations, this paper, utilizing service composition histories, introduces the theory and methodology in the complex network research and proposes an interactive service recommendation approach. It uses an affiliation network to abstract service composition histories (i.e., composite services, atomic services, and the affiliation relationships between them), obtains the service composition relationships by one-mode projection, and introduces the backbone network extraction technology to filter out the invalid compostion relationships; it uses degree and degree distribution to mine the service usage patterns; it takes into account the situation of the failure of services and finally proposes several algorithms for service recommendation according to three usage scenarios. Real data of services crawed from ProgrammableWeb are used as subjects to demonstrate the correctness and feasibility of the proposed approach.