Web services have been one of the major drivers of the distributed service economy, supporting businesses on a global scale. They enable cross-organizational functionality integration over the Web and thus are the foundation of modern distributed service-based systems. However, despite the rapid and continual increase of Web services available on the internet, the discovery and uptake of appropriate Web services by businesses on a Web scale is still a great challenge. The reasons for this meager uptake include (i) isolation of Web services in their ecosystem (ii) poor scaling mechanism for Web service ecosystem, (iii) the lack of social relationships among related Web services and (iv) inadequate semantic information for facilitating semantic-oriented Web service discovery, and the vocabulary gaps between the service functional descriptions given by service providers and the user’s Web service query. To fill these research gaps, there is a need for a Web service discovery framework which can easily be scaled, and can simulate social interactions between Web services based on their social, functional and non-functional attributes, and in turn improve Web services discoverability. This thesis aims to contribute to the service computing domain by developing a service discovery framework that can assist Web service consumers including corporations in fulfilling their ever increasing service needs, and help them benefit maximally from the advancements of Web service technology. In particular, the thesis has addressed the Web service discovery challenges from the complex network perspective by constructing evolving Web service social networks which enables social links formation among Web services based on well-defined complex network theoretical procedures. This will allow the integration of Web service ecosystem properties such as service sociability and functionality, and Web service network properties into the discovery framework, and thereby help in enhancing service discoverability. The thesis follows three key pathways in addressing the Web service discovery challenges mentioned above. In the first pathway, a critical study of Web service ecosystem which involves investigating the underlying mechanisms that drive the evolution and interactions of Web services in their ecosystem is conducted. This is important to understand the structure of the Web service ecosystem, the evolving properties that characterized its continual growth and nature of relationships or interactions withing the system. This is achieved by using network analysis approach to study the social interactions of existing Web services and their compositions. The study analysed the dynamical properties of a typical Web service ecosystem, and investigated the popularity distribution of Web services in the ecosystem in order to get clear insight into the social interactions among Web services. Distributions of different interaction patterns that appear in form of network motifs were also analysed . In addition, various topological properties similar to the ones that characterised most evolving real world network systems are measured in the service ecosystem. Then, the key attraction dimensions, specifically preferential attachment and similarity within the Web service system are quantified. In the second pathway, the challenge of Web service isolation and its effect on service discoverability are addressed. Based on the results of the analysis conducted in first pathway, two unique approaches for constructing evolving Web service social networks, which follow the Barabási-Albert and the Popularity-Similarity Optimization complex network theoretical procedures have been proposed. Both approaches enable simulation of social links and the incorporation of social properties such as popularity, and topological properties into the Web service discovery framework. For Barabási-Albert based approach, the network is built solely on the principle of growth which is driven by popularity attractiveness , and for the Popularity-Similarity Optimization model, certain trade-offs which exist between the two Web services attraction dimensions including popularity and similarity are exploited to facilitate link formation between the services. Finally, in the third pathway, an evolving complex network-based Web service discovery service that exploits functional, social and network properties to find, select and rank Web services was proposed. The discovery service employs a novel motif-based page-rank feature with Google custom service to facilitate node ranking based on the network patterns, functional descriptions and popularity information of the Web services. The effectiveness of the proposed discovery method has been demonstrated by conducting extensive experiments on a real-world dataset crawled from Programmableweb.com.