Web services are paving the way for a new type of business applications. This can be noticed from the large number of standards and initiatives related to Web services (Margaria, 2007; Papazoglou et al., 2007; Yu et al., 2008), which tackle a variety of issues such as security, fault tolerance, and substitution. These issues hinder the automatic composition of Web services. Composition handles the situation of a user's request that cannot be satisfied by any single, available Web service, whereas a composite Web service obtained by combining available Web services may be used. Despite the tremendous capabilities that empower Web services, they still lack some capabilities that would propel them to a higher level of adoption by the IT community and make them compete with other integration middleware like CORBA and .Net. As a result, Web services adoption could be slowed down if some issues such as the complexity of their discovery are not properly addressed (Langdom, 2003). For this particular issue of discovery, we examine in this chapter the use of social networks (Ethier, visited in 2008; Wasserman and Glaskiewics, 1994). Such networks permit to establish between people relationships of different types like friendship, kinship, and conflict. These relationships are dynamic and, hence, adjusted over time depending on different factors like outcomes of previous interaction experiences, and natures of partners dealt with. Replacing people with Web services is doable since Web services constantly engage in different types of interaction sessions with users and peers as well