Chantal Cherifi

Vincent Labatut

Jean-François Santucci

Topological Properties of Web Services Similarity Networks

Keywords: Web Services, Web services Similarity, Complex Networks, Semantic Web

The number of publicly available Web services (WS) is continuously growing. To perform efficient WS discovery, it is desirable to organize the WS space. Works in this direction propose to group WS according to certain shared properties. Such groups commonly called communities are based either on similarity or on interaction between WS. In this paper we focus on the former, and propose a new network-based approach to extract communities from a WS collection. This process is three-stepped: first we define several similarity functions able to compare WS operations, second we use them to build so-called similarity networks, and third we identify communities under the form of specific structures in these networks. We apply our method on a collection of real-world WS and comment the resulting communities. Finally, we additionally provide an analysis and an interpretation of our similarity networks with a complex networks perspective.

Introduction

A Web Service (WS) is an autonomous software component which can be published, discovered and invoked for remote use. When a provider creates a new WS, he describes it using a WS description language. A WS description file is comparable to an interface defined in the context of object-oriented programming: it lists the operations implemented by the WS. Currently, production WS use syntactic descriptions expressed with the WS description language (WSDL), which is a W3C (World Wide Web Consortium) recommendation. Such descriptions basically contain the names of the operations and their parameters names and data types, plus some lower level information regarding the network access to the WS.

To make a WS available to consumers, the provider records it in a registry by supplying the appropriate information, including the WS description. When a consumer wants to use a WS, it queries the registry to find one that matches his needs and obtain its access point. But finding the right WS is not an easy task. Indeed the number of available WS is continuously growing. Furthermore WS are volatile; they often operate in a highly dynamic environment as providers remove, modify, or relocate them frequently. Hence, it may be of great help to organize the WS space in a meaningful manner, in order to facilitate WS discovery, composition and substitution. To that end, the WS classification process aims at grouping WS into categories usually called communities. Most works in WS classification have focused on two classification types: grouping WS according to their similarity [START_REF] Medjahed | A dynamic Foundational Architecture for Semantic Web Services[END_REF][START_REF] Taher | Towards an Approach forWeb services Substitution[END_REF][START_REF] Benatallah | Declarative Composition and Peer-to-Peer Provisioning of Dynamic Web Services[END_REF] or to their possible interaction [START_REF] Dekar | A Graph b-Coloring Based Method for Composition-Oriented Web Services Classification[END_REF][START_REF] Sepehrifar | An Algorithm To Select The Optimal Composition Of The Services[END_REF].

In this work we focus on the former, and propose a new, network-based approach to build communities. Our approach is three-stepped: first we use several similarity functions to compare every pair of operations in a given WS collection, second we build a so-called similarity network from these values, and third we extract communities from this network. In parallel, we perform a detailed analysis and interpretation of the similarity network topological properties.

The rest of the paper is organized as follows. In section 2, we review the existing approaches regarding WS communities definition. We also explain how these communities can be used practically. Indeed, although this point is out of the scope of this article, it should be noted the communities mined with our own method can be used for the same purposes. Section 3 provides key information about complex networks, their analysis and properties. In section 4, we introduce similarity networks and the method we use to build them. In section 5 we present and discuss our results, focusing on the comparison of the proposed similarity functions and on the similarity networks properties. Conclusions and perspectives are given in section 6.

Related Works

Existing works adopt either a top-down or a bottom-up approach to define communities. In the former, abstract communities are designed a priori, and WS are then defined in order to fit these categories. In the later, communities are mined from an existing WS collection. They also can be distinguished depending on the type of WS description they use (syntactic vs. semantic), and their definition of the concept of similarity.

The top-down approach used in [START_REF] Medjahed | A dynamic Foundational Architecture for Semantic Web Services[END_REF] consists in defining WS similarity relatively to their application domains. They introduced the concept of community ontology, which serves as a template for describing communities of WS operating in the same thematic area, independently from their functionalities. The authors use communities to tackle the problems of organizing, describing, and managing semantic WS. A community is view itself as a WS which is created, advertised, discovered, and invoked in the same way regular WS are.

Benatallah et al. define a community as a group of WS sharing a common functionality, although they can simultaneously have different non-functional properties, like different providers or QoS parameters [START_REF] Benatallah | Declarative Composition and Peer-to-Peer Provisioning of Dynamic Web Services[END_REF]. A community is considered as a set of alternative WS represented by a set of generic operations. It is used in the context of discovery and composition. When some request targets a given functionality, the corresponding community is identified and the request is delegated to one of its members. The choice of the delegate is based on the parameters of the request, the characteristics of the members, the history of past executions and the status of ongoing executions.

Other authors use functionality-based similarity, but with a semantic web approach [START_REF] Taher | Towards an Approach forWeb services Substitution[END_REF]. Each community is associated to a specific functionality, shared by all the WS it contains, and represented by an ontological concept. A community is then defined as a triple containing an abstract WS (community functionality described by some abstract operations), a set of concrete WS and a mapping module between the abstract operations and the concrete WS. A community is considered as a set of substitutable WS (relatively to the community functionality) and is advertised in a UDDI registry for discovery purpose.

Unlike the first three ones, this work and the following ones follow a bottom-up approach. Nayak et al. [START_REF] Nayak | Web Service Discovery with additional Semantics and Clustering[END_REF] computed separately different similarities between WS on UDDI descriptions, WSDL terms and OWL-S terms using Jaccard coefficient. Similarities are then merged to obtain a so-called accumulative similarity. By proceeding likewise for all pairs in a WS collection, the authors build a similarity matrix, on which a clustering algorithm is applied to identify the communities.

Konduri et al [START_REF] Konduri | Clustering of Web Services Based on WordNet Semantic Similarity[END_REF] use the interface similarity assessment method [START_REF] Wu | Similarity-based Web service matchmaking[END_REF] to compute semantic similarity on operations and parameters name. This method compares several types of WS properties (common properties, special properties, WS interface and QoS) to get an overall similarity measure used to fill a similarity matrix. Like in the previous approach, communities are then identified by clustering. Each community is represented by a set of characteristic operations designed to be used for WS discovery.

Instead of using the community notion, Kona et al. developed a theory of substituability [START_REF] Kona | USDL: A Service-Semantics Description Language for Automatic Service Discovery and Composition[END_REF]. A semantical WS can be a substitute to another if it requires as many or less inputs and if it produces as many or more outputs. This holds both in terms of number of parameters, and ontological level of the concepts associated to the parameters. The theory was designed to build tools for automatically discovering and composing WS.

Our approach is bottom-up and relies on syntactic WS descriptions, although it can be easily extended to semantic ones. The main differences are the use of four original distinct similarity functions, each one with its own interpretation, and the fact the communities are identified as specific structures in a complex network. Moreover, we focus on the operation level, by opposition to the WS level. In all four functions, the similarity is defined in terms of functionalities.

Complex Network Properties

Complex networks are a specific class of graphs, characterized by a huge number of nodes and non trivial topological properties. Used in many different fields to model real-world systems [START_REF] Costa | Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications[END_REF], they have been intensively studied both theoretically and practically [START_REF] Newman | The structure and function of complex networks[END_REF]. Because of their complexity, specific tools are necessary to analyze and compare them. This is usually performed through the comparison of several wellknown properties, supposed to summarize the essential of the network structure.

Components Organization

A component is a maximal connected sub graph, i.e. a set of interconnected nodes, all disconnected from the rest of the network. The component distribution and, more specifically, the size of the largest component are important network properties. The fact the network is split in several separated parts with various sizes is directly related to the modeled system effectiveness at doing its job. In some cases, a so-called giant component, whose size is far greater than the other components, is required for the system to work efficiently. For example, in a communication network like the Internet, the size of the largest component represents the largest fraction of the network within which communication is possible [START_REF] Newman | The structure and function of complex networks[END_REF]. Most real-world networks have a giant component. However, in some other cases, separated small parts are preferable. For instance, when epidemiologists model disease propagation in a population, they look for scattered networks.

Average Distance

The distance between two nodes is defined as the number of links in the shortest directed path connecting them. At the level of the whole network, this allows to process the average distance and the diameter. The former corresponds to the mean distance over all pairs of nodes [START_REF] Newman | The structure and function of complex networks[END_REF]. This notion is related to the small world property, observed when this distance is relatively small. The classic procedure to assess this property consists in comparing the average distance measured in some network of interest to the one estimated for an Erdős-Rényi (ER) network [START_REF] Erdos | On random graphs[END_REF] containing the same numbers of nodes and links, since this random generative model is known to produce networks exhibiting the small world property [START_REF] Newman | The structure and function of complex networks[END_REF]. In terms of dynamic processes, the existence of shortcuts between nodes can be interpreted as propagation efficiency [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. Most real-world networks have the small world property.

Transitivity

Network transitivity (also called clustering) corresponds to the triangle density in the considered network, where a triangle is a structure of three completely connected nodes. It is measured by a transitivity coefficient, which is the ratio of existing to possible triangles in the network [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. The higher this coefficient, the more probable it is to observe a link between two nodes which are both connected to a third one. A real-world network is supposed to have a higher transitivity than the corresponding ER network by an order of magnitude corresponding to their number of nodes, meaning their nodes tend to form densely connected groups.

Networks constitute a convenient way to represent a collection of WS, allowing visualizing, analyzing and taking advantage of the relationships of similarity observed between them. Generally speaking, we define a similarity network as a graph whose nodes correspond to objects, and links indicate a certain similarity between the connected nodes. They can be considered as complex networks and some authors previously used this approach to model WS collections in other contexts than community identification [START_REF] Liu | Design and Implementation of an Extended UDDI Registration Center for Web Service Graph[END_REF][START_REF] Oh | Effective Web Services Composition in Diverse and Large-Scale Services Networks[END_REF][START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF][START_REF] Gekas | Employing Graph Network Analysis for Web Service Composition[END_REF][START_REF] Shiaa | An Incremental Graph-based Approach to Automatic Service Composition[END_REF][START_REF] Kwon | PSR : Pre-computing Solutions in RDBMS for FastWeb Services Composition Search[END_REF][START_REF] Hashemian | A Graph-Based Approach to Web Services Composition[END_REF]Cherifi, Labatut & Santucci, 2010 -a;Cherifi, Labatut & Santucci, 2010 -b).

To build our similarity networks, we decided, as a first step, to focus on syntactically described operations. An operation is a part of a WS implementing a specific functionality. It is syntactically described by its name and its input and output parameters (names and data types). To represent a collection of WS descriptions under the form of a similarity network of operations, we first create a node to represent each operation in the collection. Then, a link is added between two nodes iff the corresponding operations present a certain similarity. In the resulting network, similar operations are connected and form graph components. We previously defined a community as a set of similar operations, so identifying them is straightforward here: each component simply corresponds to a community. Of course, the nature of the similarity relation is extremely important, and can be defined in various ways. In the following, we describe four similarity functions and explain how they can be interpreted and used.

Similarity Functions

In our case, a similarity function takes two operations and and quantifies their similarity. It can be either symmetrical ( ) or asymmetrical, and it can output binary or real values. The four functions we defined to build our networks are based on previous works focusing on WS retrieval [START_REF] Keller | Automatic Location of Web Services[END_REF][START_REF] Küster | Evaluating Semantic Web Service Matchmaking Effectiveness Based on Graded Relevance[END_REF]. In these articles, the authors defined several matchmaking operators and used them to compare sets of ontological concepts. We selected four of these operators: match, partial match, excess match, relation match, and adapted them to our goal, which is the processing of a similarity value between two sets of parameters. We obtained four similarity functions we called Full Similarity, Partial Similarity, Excess Similarity and Relation Similarity; all of them with a binary output. These functions are defined in terms of set relations between the input and output parameter sets of the compared operations.

Let , and , be the sets of input and output parameters for operation , respectively. Suppose we want to compare and . FullSim is a symmetrical function stating both operations are fully similar iff 1) they provide exactly the same outputs (

) and 2) they need overlapping inputs ( ). PartialSim and ExcessSim are asymmetrical. With the former, is partially similar to iff 1) some outputs are missing in ( ) and 2) they need overlapping inputs ( ). With the latter, is similar to with excess iff 1) provides all outputs plus additional ones ( ) and 2) needs only some of inputs (

). The RelationSim function is symmetrical and states both operations have a relational similarity iff 1) they have exactly the same outputs ( ) and 2) they share no common input (

). These definitions are summarized in Table 1. To determine the relations between two sets of parameters, one needs to be able to compare the parameters themselves. For this purpose, we selected the basic matching operator already used in our previous work (Cherifi, Labatut & Santucci, 2010 -a), consisting in comparing only the parameters names. Two parameters are said to be equal iff their names are the exact same strings. This is a very simple and rather naïve operator as it certainly leads to irrelevant matching and miss some relevant ones, from a semantic point of view. Nevertheless, for this first work, we chose to put our focus on building communities and studying their network properties, rather than trying more flexible matching operators.

To summarize this section: we defined four different similarity functions able to compare operations, all using the same simple matching operator to compare parameter names. Each function corresponding to a different definition of the concept of similarity, they will lead to different similarity networks when applied to a given WS collection.

Interpretation

We will now use an example to show how our similarity functions can be interpreted, and why they are relevant to compare operations. Consider the operations defined in Figure 1: is called get_CITYNAMEbyZIP and returns the city name corresponding to the specified zip code; is called get_CITYNAMEbyZIPGEOGRAPHICALREGION and returns the city name corresponding to the specified zip code and geographical region, is called get_GEOGRAPHICALLOCATIONbyZIP and returns the city name, longitude, latitude and altitude of the location corresponding to the specified zip code, is called get_WEATHERbyZIP and returns the weather report of the location corresponding to the specified zip code, is called get_WEATHERbyCITYNAME and returns the weather report of a city whose name has been specified, and is called get_WEATHERWEATHERREPORTSUBSCRbyCITYNAME and returns the weather report itself and a subscription form for a city whose name has been specified. and are fully similar, because they produce the same outputs and have common inputs.

is partially similar to , because it lacks some of outputs and they have common inputs.

is similar to with excess, because it produces all of outputs and more, and they have common inputs. Finally, and are relationally similar, because their outputs are the same and they have no common input. The meaning of these functions appears when one does not consider comparing two operations, but one operation and some given inputs and outputs. Suppose we have a user willing to provide his home town name and zip code in order to get a weather report. We could obviously look only for operations with both similar inputs and outputs, but this similarity function is most of the time too strict to produce relevant results, which is why we discarded it. It is the case here, since no operation corresponds exactly to the request. In this operation discovery context, the output the user desires is generally considered as the most important constraint [START_REF] Keller | Automatic Location of Web Services[END_REF]. FullSim can therefore be considered as the second best solution, since it includes all the desired outputs and a part of the available inputs. In our example, both and would be selected.

Still, it is possible to find no operation meeting these criteria, in which case the user might have to relax the constraints regarding his goal. In our example, suppose and are unavailable, and the user switches to ExcessSim. Operation is then the only solution, and it returns an additional weather report subscription compared to the initial request. It is likely the user will not be interested in this result, since he is looking for a free service. But on the contrary, he might have been interested in other additional outputs such as a list of weather reports for the neighboring cities. The PartialSim function works likewise, except it returns operations providing only a part of the desired goals (instead of more than the desired goals for ExcessSim).

The RelationSim function corresponds to a further relaxation of the user's constraints. Suppose the user is still looking for his weather report, but can only provide a zip code. If is unavailable, then no operation can be found using FullSim, PartialSim or ExcessSim. On the contrary, RelationSim will return , which has the appropriate output but completely different input. Even if the operation cannot be invoked directly, further search might provide the needed parameters, for instance by mining a composition of operations. In our case the user could invoke first and take advantage of its output (a city name) to invoke .

To conclude this section, we want to highlight the fact the proposed similarity functions were designed to be complementary, and not to be opposed. Each one corresponds to a specific use, directly related to the user goal. This is why, for completeness purpose, all four similarity networks will be build and analyzed in the next section.

Results and Discussion

We extracted similarity networks from the SAWSDL-TC1 collection of WS descriptions [START_REF] Klusch | Semantic web service selection with SAWSDL-MX[END_REF]. This test collection provides 894 WS descriptions written in SAWSDL, and distributed over 7 thematic domains (education, medical care, food, travel, communication, economy and weapon). It originates in the OWLS-TC2.2 collection, which contains real-world WS descriptions retrieved from public IBM UDDI registries, and semi-automatically transformed from WSDL to OWL-S. This collection was subsequently resampled to increase its size, and converted to SAWSDL. From a SAWSDL file, we can extract the information needed to build our similarity networks.

Network Structure and Components

Each network contains 785 nodes, corresponding to the 785 operations of the collection. The first four rows in Table 2 summarize the major results we processed regarding the networks structure. Except for the first row, all the others properties are computed on the trimmed networks, i.e. without any isolated nodes. For all our networks, and unlike most real-world networks, no giant component is emerging, but numerous small ones, and isolated nodes. An example of this common structure is shown in Figure 2. This reflects the decomposition of the collection into a reasonable number of communities. This is a good thing, because having only isolated nodes or a giant component would lead to useless communities. Indeed, in the former case, each community would contain only one operation, and in the latter all operations would be considered as similar to the all others. Both cases would have been surprising considering we processed a real-world collection.

The number of isolated nodes globally decreases when going from FullSim to RelationSim, and at the same time, the numbers of links and components increase. Indeed, as constraints on outputs become less strict, more links are created leading to new components or increase of the existing ones. The numbers of operations, links and components are the highest in the RelationSim network. It means in this collection, a lot of operations produce identical outputs with completely different inputs. This contributes to increase the number of available and potentially usable operations in a discovery process.

Each component corresponds to a group of similar operations representing a community. For instance, in this PartialSim network component, operations get_DESTINATION_HOTEL, get_SPORTS_HOTEL, get_ACTIVITY_HOTEL are linked with get_HOTEL. Indeed get_HOTEL operations provides only the HOTEL output parameter while the three others provide the HOTEL output parameter and an additional specific one. A get_HOTEL operation can satisfy a destination/hotel request, an activity/hotel request or a sports/hotel request but not completely. In the RelationSim network, one component gathers operations that produce an output parameter named get_LUXURYHOTEL. It contains five operations. One of them has the parameter CITY as input, another one has the parameter GEOGRAPHICAL-REGION as input.

More than 90% of nodes and links are contained in the first , , , communities in the FullSim, PartialSim, ExcessSim and RelationSim networks respectively. Table 3 shows range values for those principal communities. The most remarkable point is the links number of the largest RelationSim community. This corresponds to the PRICE output parameter which is common to several domains and sub-domains (food, car, book, device, economy). This number then falls to for the RECOMMENDEDPRICE output parameter, and to for the FUNDING output parameter, which are also shared by several domains.

Average Distance and Transitivity

As shown in Table 2, all the similarity networks exhibit a small average distance. By comparison, this distance is approximately ranging from to in ER random networks of comparable sizes, which means the similarity networks possess the smallworld property. In other words, many shortcuts exist in the networks, indicating that several operations share the same input parameters for FullSim, PartialSim and ExcessSim. For the RelationSim case, this observation confirms the previous point according to which a lot of operations produce same parameters with completely different inputs. Nevertheless, the fact small components are numerous also has an impact on this result, since non-existing paths are not taken into account when processing the average distance.

For all the similarity networks, the measured transitivity is higher than for comparable ER networks (whose transitivity is less than ). It is not enough to conclude our networks have a high transitivity relatively to other real-world networks, though. However, given our networks do not have a giant component, this still means a significant number of triangles exist inside the communities. Consider for example the component containing the get_SKILLEDOCCUPATION operations in the FullSim network. The four operations have the SKILLEDOCCUPATION parameter as output. They are linked with four triangles because of their input parameters sets {CITY, COUNTRY}, {COUNTRY}, {COUNTRY, PUBLICCOMPANY} and {COUNTRY, COMPANY}.

Conclusion

In this paper, we proposed a new method for building WS communities, aiming at grouping WS operations which are similar in terms of functionalities. We designed four similarity functions, each one corresponding to a different definition of the concept of similarity. We described a method using a similarity function to build a similarity network of WS operations. In such a network, communities are topologically defined under the form of components, i.e. maximal connected subgraphs. As an example, we applied each function on a given real-world collection of WS to generate different similarity networks of operations. We shown our method allows identifying consistent communities of operations from these networks. We additionally discussed and compared the topological properties of the networks through the use of complex networks tools. All four networks exhibit a small average distance, which is a property observed in most real-world networks. At the opposite side, the transitivity property is small when compared to other real-world networks, but still high enough if we consider the networks do not exhibit any giant component.

The originality of our work lies in the similarity functions and in the similarity network-based method, which, to our knowledge, were never used in the context of WS communities building before. We additionally gave a analysis of the networks. We plan to extend it in two ways. First, the collection we used to build similarity networks is based on a set of real-world WS descriptions, but half of them were generated through resampling. Hence, it cannot be considered as perfectly realistic. We want to analyze similarity networks extract from a collection of real WS descriptions like the one found in [START_REF] Hess | ASSAM: A Tool for Semi-Automatically Annotating Semantic Web Services[END_REF] which contain WSDL files. Second, it would be interesting to build networks based on semantic descriptions and compare their properties to those of the syntactic networks presented in this article. As semantics seems to improve WS discovery and composition, we can expect better results for semantic network-based communities.

Figure 1

 1 Figure 1 Similarity between WS operations

Figure 2 A

 2 Figure 2 A PartialSim Component

Table 1

 1 Similarity Functions Definitions

	Similarity function	Sets Relations	Direction
	FullSim		symetrical
	PartialSim		assymetrical
	ExcessSim		assymetrical
	RelationSim		symetrical

Table 2

 2 Networks Properties

	Property	FullSim	PartialSim	ExcessSim	RelationSim
	Isolated nodes
	Nodes in trimmed
	network
	Components
	Links
	Average distance
	Transitivity

Table 3

 3 Networks Components Properties

	Property	FullSim	PartialSim	ExcessSim	RelationSim
	Nodes
	Links


Chantal Cherifi

Vincent Labatut

Jean-François Santucci

Benefits of Semantics on Web Service Composition from a Complex Network Perspective

Keywords: Web Services, Service Composition, Complex Networks, Interaction Networks, Semantic Web

The number of publicly available Web services (WS) is continuously growing, and in parallel, we are witnessing a rapid development in semanticrelated web technologies. The intersection of the semantic web and WS allows the development of semantic WS. In this work, we adopt a complex network perspective to perform a comparative analysis of the syntactic and semantic approaches used to describe WS. From a collection of publicly available WS descriptions, we extract syntactic and semantic WS interaction networks. We take advantage of tools from the complex network field to analyze them and determine their properties. We show that WS interaction networks exhibit some of the typical characteristics observed in real-world networks, such as short average distance between nodes and community structure. By comparing syntactic and semantic networks through their properties, we show the introduction of semantics in WS descriptions should improve the composition process.

Introduction

A Web Service (WS) is an autonomous software component which can be published, discovered and invoked for remote use. For this purpose, its characteristics must be made publicly available, under the form of a so-called service description. This file comparable to interfaces defined in the context of object-oriented programming lists the operations implemented by the service. Currently, production WS use syntactic descriptions expressed with the WS description language (WSDL), which is a W3C (World Wide Web Consortium) recommendation. Such descriptions basically contain the names of the operations and their parameters names and data types, plus some lower level information regarding the network access to the service. WS were initially designed to interact with each other, in order to provide a composition of WS able to offer higher level functionalities [START_REF] Benatallah | Towards patterns of web services composition[END_REF]. Current production discovery mechanisms support only keyword-based search in WS registries and no form of inference nor flexible match can be performed [START_REF] Sycara | Automated Discovery, Interaction and Composition of Semantic Web Services[END_REF]. More advanced research (non-production) approaches rely on comparing structured data such as parameters types and names, or analyzing unstructured textual comments [START_REF] Ma | Web Services Discovery Based on Latent Semantic Approach[END_REF][START_REF] Stroulia | Semantic structure matching for assessing Web-service similarity[END_REF][START_REF] Wu | Similarity-based Web service matchmaking[END_REF]. This is generally not enough to distinguish WS in terms of functionality, and consequently makes it difficult, or even impossible, to use these methods to automate WS composition. Indeed, syntactically discovered WS must be manually validated to ensure they implement the desired behavior, leading to static, a priori compositions.

To solve this limitation, the WS research community introduced semantics in WS descriptions, through the use of new semantic description languages. Different formats exist, among which we can distinguish purely semantic descriptions (OWL-S, a W3C recommendation), from annotated WSDL descriptions (WSDL-S and SAWSDL). Although those languages allow to associate ontological concepts with various elements of the description, the research community has been focusing only on the concepts qualifying the operations inputs and outputs. Retrieving semantic information is far more costly than collecting syntactic descriptions, even when considering only parameters. The latter can be performed quickly and completely automatically. The former is a long task, requiring human intervention to label each parameter with the proper concept. Annotation tools exist to help, but they are clearly not mature yet, and often defined for specific collections or languages [START_REF] Hess | ASSAM: A Tool for Semi-Automatically Annotating Semantic Web Services[END_REF][START_REF] Gomadam | Radiant: A tool for semantic annotation of Web Services[END_REF]. Maybe for these reasons, no semantic annotation language emerged as an industry standard. Although they appeared more than five years ago, all production WS still rely on WSDL. Even at a research level, very few publicly available significant collections of semantically annotated WS exist, making it very difficult to test new algorithms.

This situation leads to one question: is describing WS semantically worth the cost? To our knowledge, no one did ever compare the information underlying syntactic and semantic WS descriptions. In this work, we try to tackle this problem from the service composition perspective, through the use of complex networks. We consider a set of WS as a broad interaction space, in which WS are related if they can be chained up in a composition process. We model this space by building so-called interaction networks, based on syntactic and semantic descriptions of a given WS collection. We assume that the information conveyed by the two different kinds of descriptions appears in the corresponding interaction networks. We then compare the syntactic and semantic descriptive approaches through the networks topological properties. Our main contributions are the formal definition of three types of semantic networks, an extended investigation of the WS networks topology and the comparison of syntactic and semantic networks. In section 2, we present complex networks and their main topological properties. Section 3 introduces interaction networks and explains how they can be extracted from WS descriptions. Section 4 is dedicated to the presentation and discussion of our experimental results, i.e. the obtained networks, their topological properties and how they compare. Finally, in section 5, we emphasize the original points of our work, discuss its limitations and their possible solutions.

Complex Networks Properties

Complex networks are a specific class of graphs, characterized by a huge number of nodes and non trivial topological properties. Used in many different fields to model real-world systems [START_REF] Da Fontura Costa | Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications[END_REF], they have been intensively studied both theoretically and practically [START_REF] Newman | The structure and function of complex networks[END_REF]. Because of their complexity, specific tools are necessary to analyze and compare them. This is usually performed through the comparison of several wellknown properties, supposed to summarize the essential of the network structure.

The distance between two nodes is defined as the number of links in the shortest directed path connecting them. At the level of the whole network, this allows to process the average distance and the diameter. The former corresponds to the mean distance over all pairs of nodes [START_REF] Newman | The structure and function of complex networks[END_REF]. This notion is related to the small world property, observed when this distance is relatively small. The classic procedure to assess this property consists in comparing the average distance measured in some network of interest to the one estimated for an Erdős-Rényi (ER) network [START_REF] Erdos | On random graphs[END_REF] containing the same numbers of nodes and links, since this random generative model is known to produce networks exhibiting the small world property [START_REF] Newman | The structure and function of complex networks[END_REF]. In terms of dynamic processes, the existence of shortcuts between nodes can be interpreted as propagation efficiency [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. Most real-world networks have the small world property. The diameter is the greatest distance over all pairs of nodes in the network.

A network transitivity (also called clustering) corresponds to its density of triangles, where a triangle is a structure of three completely connected nodes. It is measured by a transitivity coefficient, which is the ratio of existing triangles to possible triangles in the considered network [START_REF] Watts | Collective dynamics of small-world networks[END_REF]. The higher this coefficient, the more probable it is to observe a link between two nodes which are both connected to a third one. A real-world network is supposed to have a higher transitivity than the corresponding ER network by an order of magnitude corresponding to their number of nodes, meaning their nodes tend to form densely connected groups.

The degree of a node corresponds to the number of links attached to it. In a directed network, one can distinguish in and out degrees, i.e. the numbers of incoming and outgoing links, respectively. Nodes with a high in (resp. out) degree are called authorities (resp. hubs). The degree distribution of a network is particularly revealing of its structure. Most real-world networks have a power law degree distribution [START_REF] Newman | The structure and function of complex networks[END_REF][START_REF] Albert | The diameter of the world wide web[END_REF][START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF], resulting in the so-called scale free property. In other words, real-world networks contain a very few nodes with extremely high degree, and a massive number of nodes with very small degree.

A component is a maximal connected sub graph, i.e. a set of interconnected nodes, all disconnected from the rest of the network. The component distribution and, more specifically, the size of the largest component are important network properties. Indeed, depending on the context, the fact the network is split in several separated parts with various sizes can be a direct representation of the modeled system effectiveness at doing its job. For example, in a communication network like the Internet, the size of the largest component represents the largest fraction of the network within which communication is possible [START_REF] Newman | The structure and function of complex networks[END_REF]. Most real-world networks have a so-called giant component, whose size is far greater than the other components.

A community is defined as a subset of nodes densely interconnected relatively to the rest of the network. Unlike components, communities are not necessarily disconnected from each other (and generally, they are significantly connected). Specific community detection algorithms must be used to identify them, leading to a partition of the overall nodes set. Most of them are dedicated to undirected networks, and only a very few recent tools can use the information conveyed by directed links. We chose to use a well tested program, and therefore focused on undirected links. We selected the Walktrap algorithm which exhibits good performances according to recent benchmarks [START_REF] Orman | A Comparison of Community Detection Algorithms on Artificial Networks[END_REF]. To assess the quality of a network partition, the standard measure is Newman's modularity [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], whose value also depends on the considered network structure. Consequently, its theoretical maximal value of (perfect community structure and partition) is rarely reached, and in practice values between and are considered high [START_REF] Newman | Modularity and community structure in networks[END_REF]. A value of represents a random partition or the absence of community structure. Many real-world networks have a community structure [START_REF] Newman | The structure and function of complex networks[END_REF].

Interaction Networks

Generally speaking, we define an interaction network as a directed graph whose nodes correspond to interacting objects and links indicate the possibility for the tail nodes to act on the head nodes. They can be considered as complex networks, and few authors used similar approaches to model collections of WS, using different granularity levels [START_REF] Oh | Effective Web Services Composition in diverse and large-scale services networks[END_REF] and based on syntactic [START_REF] Oh | Effective Web Services Composition in diverse and large-scale services networks[END_REF][START_REF] Liu | Design and Implementation of an Extended UDDI Registration Center for Web Service Graph[END_REF] or on semantic [START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF][START_REF] Gekas | Employing Graph Network Analysis for Web Service Composition[END_REF][START_REF] Shiaa | An Incremental Graph-based Approach to Automatic Service Composition[END_REF][START_REF] Kwon | PSR : Pre-computing Solutions in RDBMS for FastWeb Services Composition Search[END_REF][START_REF] Hashemian | A Graph-Based Approach to Web Services Composition Symposium on Applications and the Internet[END_REF] descriptions. In this work, we focused on networks of operations, because operations are the main point of interest when it comes to WS composition. We used both syntactic and semantic descriptions, since our goal is to compare the two types of WS descriptions.

As stated before, a WS interface is defined under the form of a set of operations. An operation represents a specific functionality, described independently from its implementation, for interoperability purposes. Besides its functionality, it is characterized by two sets of input and output parameters, noted and , respectively. In a syntactic description, each parameter has a name and a type. This type is also defined independently from any implementation, again for interoperability reasons. Most of the time, the XML schema definition language (XSD) is used. In a semantic description, name and type are also generally specified, and an additional ontological concept is associated to the parameter, in order to give it a precise meaning. The most popular language used to describe these concepts is OWL, which also generally uses an XML representation.

To represent a collection of WS description under the form of an interaction network of operations, we first define a node to represent each operation in the collection. Then, a link is drawn from an operation towards another operation iff for each input parameter in , a similar output parameter exists in . In other words, the link exists if and only if operation can provide all the information requested to apply operation . In Fig. 1, the left side represents a set of considered operations (numbers) and their input and output parameters (letters), whereas the right side corresponds to the associated interaction network of operations. All the second operation inputs ( ) are included in the first operation outputs ( ), i.e.

, so a link exists between these operations in the interaction network. On the contrary, neither the first nor second (

) operations provide all the parameters required by the third one ( ), which is why there is no link pointing towards the third operation in the interaction network.

In the interaction network, a link between two operations therefore represents the possibility to compose them. Determining if two parameters are similar is a complex task which depends on the nature of the considered parameters (syntactic vs. semantic description) and on how the notion of similarity is defined. These factors are implemented under the form of a so-called matching function. A matching function takes two parameters and , and determines their level of similarity [START_REF] Shvaiko | A Survey of Schema-Based Matching Approaches[END_REF], generally under the form of a value in . It can be either symmetrical (

) or asymmetrical, and its output can be either binary or real. When comparing two parameters, a real output allows representing various levels of similarity, which is a good thing because it conveys a more subtle information than a raw binary value. But it also results in a more complex processing during network generation, and possibly in a network containing weighted links. Yet, most of the standard tools we decided to use to compare networks are defined for unweighted networks only, so we selected only binary matching functions in order to avoid this situation. Because of the different nature of the concerned information, we used different matching functions to compare syntactically and semantically described parameters, resulting in syntactic and semantic interaction networks, respectively. For syntactic descriptions, we compare parameters names: two parameters are said to be similar if their names are the exact same strings. The semantic matching is performed using the ontological concept associated to the parameters. We selected the three operators classically used in previous WS-related works to compare ontological concepts [START_REF] Paolucci | Semantic Matching of Web Services Capabilities[END_REF]: exact (symmetrical), plug-in and subsume (both asymmetrical). The first corresponds to a perfect matching, i.e. both concepts belong to the same ontology and are exactly identical. The second means the concept associated to the first parameter is more specific than the other one; the third represents the fact the first concept is more general than the second one. Note more flexible matching functions can be defined, both for syntactic [START_REF] Kil | On the Topological Landscape of Semantic Web services Matchmaking[END_REF] and semantic [START_REF] Keller | Automatic Location of Web Services[END_REF][START_REF] Küster | Evaluating Semantic Web Service Matchmaking Effectiveness Based on Graded Relevance[END_REF][START_REF] Li | A Software Framework for Matchmaking Based on Semantic Web Technology[END_REF][START_REF] Lecue | Applying Abduction in Semantic Web Service Composition[END_REF] descriptions. Our main goal is to compare syntactic and semantic descriptions, not matching functions. We opted for standard and simple tools. In summary, we can extract four distinct networks: syntactic equal , and semantic exact , plug-in and subsume .

Operations Parameter s

Interaction Network

Results and Discussion

We extracted interaction networks from the SAWSDL-TC1 collection of WS descriptions [START_REF] Klusch | Semantic web service selection with SAWSDL-MX[END_REF][START_REF]SAWSDL[END_REF]. This test collection provides 894 semantic WS descriptions written in SAWSDL, and distributed over 7 thematic domains (education, medical care, food, travel, communication, economy and weapon). It originates in the OWLS-TC2.2 collection, which contains real-world services descriptions retrieved from public IBM UDDI registries, and semi-automatically transformed from WSDL to OWL-S. This collection was subsequently resampled to increase its size, and converted to SAWSDL. An SAWSDL file describes a service both syntactically and semantically. This allowed us to extract our syntactic and semantic networks from the same collection, and to compare them consistently. Other publicly available collections exist, but they do not suit our needs for different reasons. The collection must be composed of a large number of real WS, described both syntactically and semantically. The ASSAM fulldataset and OPOSSum SWS-TC [START_REF] Assam | [END_REF][START_REF] Opossum | [END_REF] collections are only syntactic for the first and semantic for the second. The ICEBE05 test set (not available on line anymore) is a huge collection, but its descriptions have been artificially generated. SWS-TC and Jena Geography Dataset collections from OPOSSum [START_REF] Opossum | [END_REF]35] are too small to be studied through our complex networks approach. All the extracted networks contain many isolated nodes. They represent of the total nodes in the syntactic network ( ), whereas this proportion is approximately in the semantic networks ( , and ). All networks exhibit a giant component. In the syntactic network, , it contains of the remaining nodes and of the remaining links. The others components are much smaller ranging from to nodes. The semantic network is separated in distinct components, the giant one containing of the nodes and of the links in the trimmed network (see Fig. 2). The other semantic networks ( and ) present very similar proportions. The fact distinct components exist reflects the decomposition of the collection into several non-interacting groups of operations. The presence of a giant component is a good property, because it means the number of possible interactions is high, allowing a large proportion of operations to participate in a composition. In the rest of this section, we focus on the giant components properties, discarding isolated nodes and smaller components. As shown in Table 1, the number of nodes and links is globally higher in the syntactic network, , than in the semantic networks. This is mainly due to the fact some operation parameters have exactly the same name and are therefore considered as equal in terms of syntactic matching, whereas they do not have the same meaning. For instance, two parameters can be both named parameter and represent completely different data. In terms of interaction, this kind of false positive matching results in inappropriate compositions. Using semantic information is supposed to decrease this ambiguity and improve the composition process. As shown in Table 1, both syntactic and semantic networks exhibit small average distances: and , respectively. By comparison, this distance is approximately ranging from to in ER random networks of comparable size, which means the interaction networks possess the small-world property. In other words, many short cuts exist in the networks, indicating one can find compositions implementing a requested functionality using a relatively small number of operations. The component diameter is a good indicator of the largest possible composition, which leads here to surprisingly small values ( ) regarding the network size. This may be due to the fact the considered collection was initially designed to assess matchmaking functions, and not really composition processes. One may also observe the significant difference between syntactic ( ) and semantic networks ( ), which confirms our previous remark regarding how their connectivity differs. More than the syntactic/semantic opposition, this seem to be related to the matching function flexibility, since both average distance and diameter are smaller for plug-in ( ) and subsume (

) than for exact network ( ). Unlike most real-world networks, the measured transitivity is relatively low for both syntactic and semantic networks. Indeed, as shown in Fig. 2, operations are organized hierarchically, resulting in a network structure dominated by trees rather than triangles. This favors the apparition of hubs and authorities, the former corresponding to operations possibly usable by many other operations and the latter to operations possibly using many other operations. They play a central role in the composition process, and their failure can be critical. If some operation is a hub, its output is needed by many other operations. If it becomes unavailable, all these operations cannot be composed anymore, unless other operations providing them equivalent parameters exist. If some operation is an authority, it can be composed from many other operations, which makes it less sensitive to their failure.

We fitted the networks degree distributions to the power law using the method proposed in [START_REF] Clauset | Power-Law Distributions in Empirical Data[END_REF]. We obtained almost zero p-values and therefore rejected this hypothesis, for all 4 networks. Even when analyzing these distributions empirically, it was difficult to interpret them, because no pattern seemed to emerge. We propose two explanations for this. First, power law fitting tests requires much data, and the size of the considered collection might be too small to allow a consistent analysis. Second, an important bias might have been introduced when the collection was resampled to increase its size, since this was certainly performed without any regard concerning the preservation of the degree distribution. However this is difficult to assess since we do not have access to this information, but only to the resulting collection. Of course, it is also possible our networks simply do not possess the scale free property.

The Walktrap algorithm detected communities with a good modularity for equal and exact networks. This community structure seems to reflect the collection domains, i.e. there is a partial correspondence between the groups of operations retrieved from the network structure and those defined thematically. Indeed, it makes sense to observe denser relationships between operations belonging to the same application field, because it is likely they were designed to be complementary and interact with each other. The low modularity observed for plug-in and subsume networks ( , ) is certainly due to the looser matching function, leading to more links between operations from different domains.

Conclusion

In this paper, we compared the information conveyed by syntactic and semantic WS descriptions, through the use of complex networks. For this purpose, we extracted 4 different interaction networks (1 syntactic and 3 semantic) from one collection of descriptions, using different matching functions. We processed, discussed and compared their topological properties. All four networks exhibit some properties observed in most real-world complex networks: small average distance, presence of a giant component and community structure. This globally reflects a large number of potential compositions. Some other properties expected from a real-world network are missing: transitivity is low and degrees are not power law distributed. We suppose this is due to the properties of the collection we analyzed, more precisely its hierarchical nature and the fact it was partially constituted by resampling.

When comparing syntactic and semantic networks, we observed the syntactic giant component was slightly larger, which might be due to the presence of false positives, i.e. operations irrelevantly connected. Although semantic giant components contain less links, their interconnection structure is more efficient, leading to a smaller average distance between operations (in terms of composition) and a smaller diameter (maximal composition size). We can conclude the introduction of semantics in WS description allows a more accurate representation of their potential interactions, and should consequently result in a more efficient search for composition processes, at least for the considered collection. When comparing only the three semantic networks, a clear distinction appears between the loose matching functions and the exact one. They lead to networks with even smaller diameters and average distances, corresponding to a larger proportion of links between the domains, which in turns result in a weaker community structure. This highlights the importance of the selected matching function.

The approach of representing a WS collection with an interaction network is generally used in the context of composition mining, i.e. to find the best composition relatively to some criteria of interest [START_REF] Oh | Effective Web Services Composition in diverse and large-scale services networks[END_REF][START_REF] Liu | Design and Implementation of an Extended UDDI Registration Center for Web Service Graph[END_REF][START_REF] Talantikite | Semantic annotations for web services discovery and composition[END_REF][START_REF] Gekas | Employing Graph Network Analysis for Web Service Composition[END_REF][START_REF] Shiaa | An Incremental Graph-based Approach to Automatic Service Composition[END_REF][START_REF] Kwon | PSR : Pre-computing Solutions in RDBMS for FastWeb Services Composition Search[END_REF][START_REF] Hashemian | A Graph-Based Approach to Web Services Composition Symposium on Applications and the Internet[END_REF]. Oh studied some of their topological properties, but only for syntactic networks, and did not consider the directed nature of the interaction networks nor their communities [START_REF] Oh | Effective Web Services Composition in diverse and large-scale services networks[END_REF], which are of utmost importance in the context of WS composition. Additionally, this is the first time, to our knowledge, an analysis is conducted on the topology of semantic networks, and consequently on the comparison with syntactic networks.

We can see two main limitations to our study, which we hope to solve in the near future. First, the collection we used is based on a set of real-world WS descriptions, but half of them were generated through resampling, so it cannot be considered as perfectly realistic. As a matter of fact, no other publicly available collection provides both syntactic and semantic descriptions for the same services, which is an indispensable prerequisite to a consistent comparison. The only solution we can see is to constitute our own collection, by semantically annotating a set of real syntactic descriptions. Second, we used a selected set of matching functions to extract the interaction networks. Many other functions exist, in particular more flexible syntactic distances [START_REF] Cohen | A Comparison of String Distance Metrics for Name-Matching Tasks[END_REF] can be used to perform less strict comparisons of the parameters names. For semantic matching, more subtle subsume-and plug-in-based functions can also be derived, for instance by considering the geodesic distance between two concepts located on the same branch of an ontology. This could have significant implications on the resulting network properties, since it is directly related to the amount of false positives (nodes irrelevantly connected) and false negatives (nodes irrelevantly disconnected). Besides these improvements on data and matching functions, we plan to extend our work in two ways. First, we want to analyze in greater details the partial overlapping observed between communities and domains. It may correspond to operations shared between domains, which could be of great interest for a provider as they may be highly demanded. A related point is to test whether properties observed for the whole network are also valid for domains or sets of domains. Second, to confirm the observations we made on the network of operations, it is possible to extract and study equivalent networks at two other granularity levels [START_REF] Oh | Effective Web Services Composition in Diverse and Large-Scale Services Networks[END_REF]. We already performed the analysis of dependency networks at the parameters level [START_REF] Cherifi | Web Services Dependency Networks Analysis[END_REF], and plan to focus on interaction networks of whole WS very soon.

Fig. 1 .

 1 Fig. 1. Example of interaction network extraction.

Fig. 2 .

 2 Fig. 2. Trimmed exact semantic network . The giant component is located on the right side.

Table 1 .

 1 Properties of the giant components.

	Property	Syntactic	Semantic
	Nodes	395	341	369	329
	Links	3666	3426	2446	3864
	Average distance	2.19	1.87	1.32	1.39
	Diameter	8	4	3	3
	Transitivity	0.032	0.022	0.002 0.027
	Communities	16	12	7	4
	Modularity	0.52	0.50	0.13	0.07


Chantal Cherifi

Vincent Labatut

Jean-François Santucci

On Flexible Web Services Composition Networks

Keywords: Web services, Web services Composition, Interaction Networks, Similarity Metrics, Flexible Matching

The semantic Web service community develops efforts to bring semantics to Web service descriptions and allow automatic discovery and composition. However, there is no widespread adoption of such descriptions yet, because semantically defining Web services is highly complicated and costly. As a result, production Web services still rely on syntactic descriptions, key-word based discovery and predefined compositions. Hence, more advanced research on syntactic Web services is still ongoing. In this work we build syntactic composition Web services networks with three well known similarity metrics, namely Levenshtein, Jaro and Jaro-Winkler. We perform a comparative study on the metrics performance by studying the topological properties of networks built from a test collection of real-world descriptions. It appears Jaro-Winkler finds more appropriate similarities and can be used at higher thresholds. For lower thresholds, the Jaro metric would be preferable because it detect less irrelevant relationships.

Introduction

Web Services (WS) are autonomous software components that can be published, discovered and invoked for remote use. For this purpose, their characteristics must be made publicly available under the form of WS descriptions. Such a description file is comparable to an interface defined in the context of object-oriented programming. It lists the operations implemented by the WS. Currently, production WS use syntactic descriptions expressed with the WS description language (WSDL) [START_REF] Christensen | Web Services Description Language (WSDL) 1.1[END_REF], which is a W3C (World Wide Web Consortium) specification. Such descriptions basically contain the names of the operations and their parameters names and data types.

Additionally, some lower level information regarding the network access to the WS is present. WS were initially designed to interact with each other, in order to provide a composition of WS able to offer higher level functionalities. Current production discovery mechanisms support only keyword-based search in WS registries and no form of inference or approximate match can be performed.

WS have rapidly emerged as important building blocks for business integration. With their explosive growth, the discovery and composition processes have become extremely important and challenging. Hence, advanced research comes from the semantic WS community, which develops a lot of efforts to bring semantics to WS descriptions and to automate discovery and composition. Languages exist, such as OWL-S [START_REF] Martin | OWL-S: Semantic Markup for Web Services[END_REF], to provide semantic unambiguous and computer-interpretable descriptions of WS. They rely on ontologies to support users and software agents to discover, invoke and compose WS with certain properties. However, there is no widespread adoption of such descriptions yet, because their definition is highly complicated and costly, for two major reasons. First, although some tools have been proposed for the annotation process, human intervention is still necessary. Second, the use of ontologies raises the problem of ontology mapping which although widely researched, is still not fully solved. To cope with this state of facts, research has also been pursued, in parallel, on syntactic WS discovery and composition.

Works on syntactic discovery relies on comparing structured data such as parameters types and names, or analyzing unstructured textual comments. Hence, in [START_REF] Wu | Similarity-based Web Service Matchmaking[END_REF], the authors provide a set of similarity assessment methods. WS Properties described in WSDL are divided into four categories: lexical, attribute, interface and QoS. Lexical similarity concerns textual properties such as the WS name or owner. Attribute similarity estimates the similarity of properties with more supporting domain knowledge, like for instance, the property indicating the type of media stream a broadcast WS provides. Interface similarity focuses on the WS operations input and output parameters, and evaluates the similarity of their names and data types. Qos similarity assesses the similarity of the WS quality performance. A more recent trend consists in taking advantage of the latent semantics. In this context, a method was proposed to retrieve relevant WS based on keyword-based syntactical analysis, with semantic concepts extracted from WSDL files [START_REF] Ma | Web Services Discovery Based on Latent Semantic Approach[END_REF]. In the first step, a set of WS is retrieved with a keyword search and a subset is isolated by analyzing the syntactical correlations between the query and the WS descriptions. The second step captures the semantic concepts hidden behind the words in a query and the advertisements in the WS, and compares them.

Works on syntactic composition encompasses a body of research, including the use of networks to represent compositions within a set of WS. In [START_REF] Kil | Graph Theoretic Topological Analysis of Web Service Networks[END_REF], the input and output parameters names are compared to build the network. To that end, the authors use a strict matching (exact similarity), an approximate matching (cosine similarity) and a semantic matching (WordNet similarity). The goal is to study how approximate and semantic matching impact the network small-world and scale-free properties. In this work, we propose to use three well-known approximate string similarity metrics, as alternatives to build syntactic WS composition networks. Similarities between WS are computed on the parameters names. Given a set of WS descriptions, we build several networks for each metrics by making their threshold varying. Each network contains all the interactions between the WS that have been computed on the basis of the parameters similarities retrieved by the approximate matching. For each network we compute a set of topological properties. We then analyze their evolution for each metric, in function of the threshold value. This study enables us to assess which metric and which threshold are the most suitable.

Our main contribution is to propose a flexible way to build WS composition networks based on approximate matching functions. This approach allows to link some semantically related WS that does not appear on WS composition networks based on strict equality of the parameters names. We provide a thorough study regarding the use of syntactic approximate similarity metrics on WS networks topology. The results of our experimentations allow determining the suitability of the metrics and the threshold range that maintains the false positive rate at an acceptable level.

In section 2, we give some basic concepts regarding WS definition, description and composition. Interaction networks are introduced in section 3 along with the similarity metrics. Section 4 is dedicated to the network properties. In section 5 we present and discuss our experimental results. Finally, in section 6 we highlight the conclusions and limitations of, and explain how our work it can be extended.

Web Services

In this section we give a formal definition of WS, explain how it can be described syntactically, and define WS composition.

A WS is a set of operations. An operation represents a specific functionality, described independently from its implementation for interoperability purposes. It can be characterized by its input and output parameters, noted and , respectively. corresponds to the information required to invoke operation , whereas is the information provided by this operation. At the WS level, the set of input and output parameters of a WS are and , respectively. Fig. 1 represents a WS labeled with two operations numbered and , and their sets of input and output parameters: , WS are either syntactically or semantically described. In this work, we are only concerned by the syntactic description of WS, which relies on the WSDL language. A WS is described by defining messages and operations under the form of an XML document. A message encapsulates the data elements of an operation. Each message consists in a set of input or output parameters. Each parameter has a name and a data type. The type is generally defined using the XML schema definition language (XSD), which makes it independent from any implementation.

WS composition addresses the situation when a request cannot be satisfied by any available single atomic WS. In this case, it might be possible to fulfill the request by combining some of the available WS, resulting in a so-called composite WS. Given a request with input parameters , desired output parameters and a set of available WS, one needs to find a WS such that and . Finding a WS that α can fulfill alone is referred to as WS discovery. When it is impossible for a single WS to fully satisfy , one needs to compose several WS , so that for all , is required at a particular stage in the composition and . This problem is referred to as WS composition. The composition thus produces a specification of how to link the available WS to realize the request.

Interaction Networks

An interaction network constitutes a convenient way to represent a set of interacting WS. It can be an object of study itself, and it can also be used to improve automated WS composition. In this section, we describe what these networks are and how they can be built.

Generally speaking, we define an interaction network as a directed graph whose nodes correspond to interacting objects and links indicate the possibility for the source nodes to act on the target nodes. In our specific case, a node represents a WS, and a link is created from a node towards a node if and only if for each input parameter in , a similar output parameter exists in . In other words, the link exists if and only if WS can provide all the information requested to apply WS . In Fig. 2, the left side represents a set of WS with their input and output parameters, whereas the right side corresponds to the associated interaction network. Considering WS and WS , all the inputs of , , are included in the outputs of , , i.e.

. Hence, is able to provide all the information needed to interact with . Consequently, a link exists between and in the interaction network. On the contrary, neither nor ( , ), provide all the parameters required by ( ), which is why there is no link pointing towards in the interaction network. An interaction link between two WS therefore represents the possibility of composing them. Determining if two parameters are similar is a complex task which depends on how the notion of similarity is defined. This is implemented under the form of the matching function through the use of similarity metrics.

Interaction network Web services

α β γ α
Parameters similarity is performed on parameter names. A matching function takes two parameter names and , and determines their level of similarity. We use an approximate matching in which two names are considered similar if the value of the similarity function is above some threshold. The key characteristic of the syntactic matching techniques is they interpret the input in function of its sole structure. Indeed, string-based terminological techniques consider a term as a sequence of character. These techniques are typically based on the following intuition: the more similar the strings, the more likely they convey the same information.

We selected three variants of the extensively used edit distance: Levenshtein, Jaro and Jaro-Winkler [START_REF] Cohen | A Comparison of String Distance Metrics for Name-Matching Tasks[END_REF]. The edit distance is based on the number of insertions, deletions, and substitutions of characters required to transform one compared string into the other.

The Levenshtein metric is the basic edit distance function, which assigns a unit cost to all edit operations. For example, the number of operations to transform both strings kitten and sitting into one another is : 1) kitten (substitution of k with s) sitten; 2) sitten (substitution of e with i) sittin; 3) sittin (insertion of g at the end) sitting.

The Jaro metric takes into account typical spelling deviations between strings. Consider two strings and . A character in is "in common" with if the same character appears in about the place in . In equation 1, is the number of matching characters and is the number of transpositions. A transposition is the operation needed to permute two matching characters if they are not farther than the distance expressed by equation 2.

(1)

(2)

The Jaro-Winkler metric, equation 3, is an extension of the Jaro metric. It uses a prefix scale which gives more favorable ratings to strings that match from the beginning for some prefix length .

(3)

The metrics score are normalized such that equates to no similarity and is an exact match.

Network Properties

The degree of a node is the number of links connected to this node. Considered at the level of the whole network, the degree is the basis of a number of measures. The minimum and maximum degrees are the smallest and largest degrees in the whole network, respectively. The average degree is the average of the degrees over all the nodes. The degree correlation reveals the way nodes are related to their neighbors according to their degree. It takes its value between (perfectly disassortative) and (perfectly assortative). In assortative networks, nodes tend to connect with nodes of similar degree. In disassortative networks, nodes with low degree are more likely connected with highly connected ones [START_REF] Boccaletti | Complex Networks: Structure and Dynamics[END_REF].

The density of a network is the ratio of the number of existing links to the number of possible links. It ranges from (no link at all) to (all possible links exist in the network, i.e. it is completely connected). Density describes the general level of connectedness in a network. A network is complete if all nodes are adjacent to each other. The more nodes are connected, the greater the density [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF].

Shortest paths play an important role in the transport and communication within a network. Indeed, the geodesic provides an optimal path way for communication in a network. It is useful to represent all the shortest path lengths of a network as a matrix in which the entry is the length of the geodesic between two distinctive nodes. A measure of the typical separation between two nodes in the network is given by the average shortest path length, also known as average distance. It is defined as the average number of steps along the shortest paths for all possible pairs of nodes [START_REF] Boccaletti | Complex Networks: Structure and Dynamics[END_REF].

In many real-world networks it is found that if a node is connected to a node , and is itself connected to another node , then there is a high probability for to be also connected to . This property is called transitivity (or clustering) and is formally defined as the triangle density of the network. A triangle is a structure of three completely connected nodes. The transitivity is the ratio of existing to possible triangles in the considered network [START_REF] Newman | The Structure and Function of Complex Networks[END_REF]. Its value ranges from (the network does not contain any triangle) to (each link in the network is a part of a triangle). The higher the transitivity is, the more probable it is to observe a link between two nodes possessing a common neighbor.

Experiments

In those experiments, our goal is twofold. First we want to compare different metrics in order to assess how the links creation is affected by the similarity between the parameters in our interaction network. We would like to identify the best metric in terms of suitability regarding the data features. Second we want to isolate a threshold range within which the matching results are meaningful. By tracking the evolution of the network links, we will be able to categorize the metrics and to determine an acceptable threshold value. We use the previously mentioned complex network properties to monitor this evolution. We start this section by describing our method. We then give the results and their interpretation for each of the topological property mentioned in section 4.

We analyzed the SAWSDL-TC1 collection of WS descriptions [START_REF]SemWebCentral[END_REF]. This test collection provides semantic WS descriptions written in SAWSDL, and distributed over thematic domains (education, medical care, food, travel, communication, economy and weapon). It originates in the OWLS-TC2.2 collection, which contains real-world WS descriptions retrieved from public IBM UDDI registries, and semi-automatically transformed from WSDL to OWL-S. This collection was subsequently re-sampled to increase its size, and converted to SAWSDL. We conducted experiments on the interaction networks extracted from SAWSDL-TC1 using the WS network extractor WS-NEXT [START_REF] Rivierre | WS-NEXT: A Web Services Network Extractor Toolkit[END_REF]. For each metric, the networks are built by varying the threshold from to with a step. Fig. 3 shows the behavior of the average degree versus the threshold for each metric. First, we remark the behavior of the Jaro and the Jaro-Winkler curves are very similar. This is in accordance with the fact the Jaro-Winkler metric is a variation of the Jaro metric, as previously stated. Second, we observe the three curves have a sigmoid shape, i.e. they are divided in three areas: two plateaus separated by a slope. The first plateau corresponds to high average degrees and low threshold values. In this area the metrics find a lot of similarities, allowing many links to be drawn. Then, for small variations of the threshold, the average degree brutally decreases. The second plateau corresponds to average degrees comparable with values obtained for a threshold set at , and deserves a particular attention, because this threshold value causes links to appear only in case of exact match. We observe that each curve inflects at a different threshold value. The curves inflects at , and for Levenshtein, Jaro and Jaro-Winkler, respectively. Those differences are related to the number of similarities found by the metrics. With a threshold of , they retrieve , and similarities respectively. To highlight the difference between the curves, we look at their meaningful part, ranging from the inflexion point to the threshold value of . We calculated the percentage of average degrees in addition to the average degree obtained with a threshold of for different threshold values. The results are gathered in Table 1. For a threshold of , the average degree is and the percentage reference is of course . In the threshold area ranging from the inflexion point to , the average degree variation is always above , which seems excessive. Nevertheless, this point needs to be confirmed. Let us assume that above of the minimum average degree, results may be not acceptable ( corresponding to an average degree of ). From this postulate, the appropriate threshold is for the Levenshtein metric, for the Jaro metric. For the Jaro-Winkler metric, the percentage of is reached at a threshold of , then it jumps to at the threshold of . Therefore, we can assume that the threshold range that can be used is for Levenshtein, for Jaro and for Jaro-Winkler.

Table 1. Proportional variation in average degree between the networks obtained for some given thresholds and those resulting from the maximal threshold. For each metric, the smaller considered threshold corresponds to the inflexion point.

Threshold Levenshtein Jaro - - - Jaro-Winkler - - - -
To go deeper, one has to consider the qualitative aspects of the results. In other words, we would like to know if the additional links are appropriate i.e. if they correspond to parameters similarities having a semantic meaning. To that end, we analyzed the parameters similarities computed by each metric from the threshold values and we estimated the false positives. As we can see in Table 2, the metrics can be ordered according to their score: Jaro returns the least false positives, Levenshtein stands between Jaro and Jaro-Winckler, which retrieves the most false positives. The score of Jaro-Winkler can be explained by analyzing the parameters names. This result is related to the fact this metric favors the existence of a common prefix between two strings. Indeed, in those data, a lot of parameters names belonging to the same domain start with the same beginning. The meaningful part of the parameter stands at the end. As an example, let us mention the two parameter names Provide MedicalFlightInformation_DesiredDepartureAirport and Provide MedicalFlightInformation_DesiredDepartureDateTime. Those parameters were considered as similar although the end parts have not the same meaning. We find that Levenshtein and Jaro have a very similar behavior concerning the false positives. Indeed, the first false positives that appear are names differing by a very short but very meaningful sequence of characters. As an example, consider: The string Non gives a completely different meaning to both parameters, which cannot be detected by the metrics. To refine our conclusions on the best metric and the most appropriate threshold for each metric, we decided to identify the threshold values leading to false positives. With the Levenshtein, Jaro and Jaro-Winkler metric, we have no false positive at the thresholds of , , and , respectively. Compared to the appropriate similarities retrieved with a threshold of , they find , and more appropriate similarities, respectively. In Table 3, we gathered the additional similarities retrieved by each metric. At the considered thresholds, it appears that Levenshtein finds some similarities that neither Jaro nor Jaro-Winkler find. Jaro-Winkler retrieves all the similarities found by Jaro and some additional ones. We also analyzed the average degree value at those thresholds. The network extracted with Levensthein does not present an average degree different from the one observed at a threshold of . Jaro and Jaro-Winkler networks show an average degree which is above the one obtained for a threshold of . Hence, if the criterion is to retrieve of false positives, Jaro-Winkler is the most suitable metric.

Jaro _GOVERNMENT-ORGANIZATION ~ _GOVERNMENTORGANIZATION _LINGUISTICEXPRESSION ~_LINGUISTICEXPRESSION1 _GEOGRAPHICAL-REGION ~ _GEOGRAPHICAL-REGION1 _GEOGRAPHICAL-REGION ~ _GEOGRAPHICAL-REGION2 _GEOPOLITICAL-ENTITY ~ _GEOPOLITICAL-ENTITY1 Jaro-Winkler _GOVERNMENT-ORGANIZATION ~ _GOVERNMENTORGANIZATION _GEOGRAPHICAL-REGION ~ _GEOGRAPHICAL-REGION1 _GEOGRAPHICAL-REGION ~ _GEOGRAPHICAL-REGION2 _GEOPOLITICAL-ENTITY ~ _GEOPOLITICAL-ENTITY1 _LINGUISTICEXPRESSION ~ _LINGUISTICEXPRESSION1 _SCIENCE-FICTION-NOVEL ~ _SCIENCEFICTIONNOVEL _GEOGRAPHICAL-REGION1 ~ _GEOGRAPHICAL-REGION2 _TIME-MEASURE ~ _TIMEMEASURE _LOCATION ~ _LOCATION1 _LOCATION ~ _LOCATION2
The variations observed for the density are very similar to those discussed for the average degree. At the threshold of , the density is rather high, with a value of . Nevertheless, we do not reach a complete network whose density is equal to . This is due to the interaction network definition, which implies that for a link to be drawn from a WS to another, all the required parameters must be provided. At the threshold of , the density drops to . At the inflexion points, the density for Levenshtein is , whereas it is for both Jaro and Jaro-Winkler. The variations observed are of the same order of magnitude than those observed for the average degree. For the Levenshtein metric the variation is while for both other metrics it reaches . Considering a density value above the density at the threshold of , which is , this density is reached at the following thresholds: for Levenshtein, for Jaro and for Jaro-Winkler. The corresponding percentages of false positives are , and . Those values are comparable to the ones obtained for the average degree. Considering the thresholds at which no false positive is retrieved ( , and ), the corresponding densities are the same that the density at the threshold of for the three metrics. The density is a property which is less sensible to small variations of the number of similarities than the average degree. Hence, it does not allow concluding which metric is the best at those thresholds. The maximum degree (cf. Fig. 4) globally follows the same trend than the average degree and the density. At the threshold of and on the first plateau, the maximum degree is around . At the threshold of , it falls to . Hence, the maximum degree is roughly multiplied by . At the inflexion points, the maximum degree is , and for Levenshtein, Jaro and Jaro-Winkler respectively. The variations are all of the same order of magnitude and smaller than the variations of the average degree and the density. For Levenshtein, Jaro and Jaro-Winkler the variations values are , and respectively. Considering the maximum degree above , which is , this value is approached within the threshold ranges , , for Levenshtein, Jaro and Jaro-Winkler respectively. The corresponding maximum degrees are for Levenshtein and for both Jaro and Jaro-Winkler. The corresponding percentages of false positives are , and . Results are very similar to those obtained for the average degree and the metrics can be ordered the same way. At the thresholds where no false positive is retrieved ( , and

), the maximum degree is not different from the value obtained with a threshold of . This is due to the fact few new similarities are introduced in this case. Hence, no conclusion can be given on which one of the three metric is the best.

As shown in Fig. 5, the curves of the minimum degree are also divided in three areas: one high plateau and one low plateau separated by a slope. A the threshold of , the minimum degree is . At the threshold of , the minimum degree is . This value corresponds to isolated nodes in the network. The inflexion points here appear latter: at for Levenshtein and at for both Jaro and Jaro-Winkler. The corresponding minimum degrees are for Levenshtein and for Jaro and Jaro-Winkler. The thresholds at which the minimum degree starts to be different from are for Levenshtein with a value of , for Jaro with a value of , and for Jaro-Winkler with a value of . The minimum degree is not very sensible to the variations of the number of similarities. Its value starts to increase at a threshold where an important number of false positive have been introduced. The transitivity curves (Fig. 6) globally show the same evolution than the ones of the average degree, the maximum degree and the density. The transitivity at the threshold of almost reaches the value of . Indeed, the many links allow the existence of numerous triangles. At the threshold of , the value falls to . At the inflexion points, the transitivity values for Levenshtein, Jaro and Jaro-Winkler are , and respectively. In comparison with the transitivity at a threshold level of , the variations are , , . They are rather high and of the same order than the ones observed for the average degree. Considering the transitivity value above the one at a threshold of , which is , this value is reached at the threshold of for Levenshtein, for Jaro and for Jaro-Winkler. Those thresholds are very close to the one for which there is no false positive. The corresponding percentages of false positives are , and . Hence, for those threshold values, we can rank Jaro and Jaro-Winkler at the same level, Levensthein being the least performing. Considering the thresholds at which no false positive is retrieved, ( , and ), the corresponding transitivity are the same than the transitivity at . For this reason and by the same way than for the density and the maximum degree, no conclusion can be given on the metrics. The degree correlation curves are represented in Fig. 7. We can see that the Jaro and the Jaro-Winkler curves are still similar. Nevertheless, the behavior of the three curves is different from what we have observed previously. The degree correlation variations are of lesser magnitude than the variations of the other metrics. For low thresholds, curves start by a stable area in which the degree correlation value is . This indicates that no correlation pattern emerges in this area. For high thresholds the curves decrease until they reach a constant value ( ). This negative value reveals a slight disassortative degree correlation pattern. Between those two extremes, the curves exhibit a maximum value that can be related to the variations of the minimum degree and to the maximum degree. Starting from a threshold value of the degree correlation remains constant until a threshold value of , and for Lenvenshtein, Jaro and Jaro-Winkler respectively. Fig. 8 shows the variation of the average distance according to the threshold. The three curves follow the same trends and Jaro and Jaro-Winkler are still closely similar. Nevertheless, the curves behavior is different from what we observed for the other properties. For the three metrics, we observe that the average distance globally increases with the threshold until it reaches a maximum value and then start to decrease. The maximum is reached at the thresholds of for Levenshtein, Jaro and Jaro-Winkler. The corresponding average distance values are , and respectively. Globally the average distance increases with the threshold. For low threshold values the average distance is around while for the threshold of , networks have an average distance of . Indeed, it makes sense to observe a greater average distance when the network contains less links. This means that almost all the nodes are neighbors of each other. This is in accordance with the results of the density which is not far from the value of for small thresholds. We remark that the curves start to increase as soon as isolated nodes appear. Indeed, the average distance calculation is only performed on interconnected nodes. The thresholds associated to the maximal average distance correspond to the inflexion points in the maximum degree curves. The thresholds for which the average distance stays stable correspond to the thresholds in the maximum degree curves for which the final value of the maximum degree start to be reached. Hence from the observation of the average distance, we can refine the conclusions from the maximum degree curves by saying that the lower limit of acceptable thresholds is , and for Levenshtein, Jaro and Jaro-Winkler respectively.

Conclusion

In this work, we studied different metrics used to build WS composition networks. To that end we observed the evolution of some complex network topological properties. Our goal was to determine the most appropriate metric for such an application as well of the most appropriate threshold range to be associated to this metric. We used three well known metrics, namely Levenshtein, Jaro and Jaro-Winkler, especially designed to compute similarity relation between strings. The evolution of the networks from high to low thresholds reflects a growth of the interactions between WS, and hence, of potential compositions. New parameter similarities are revealed, and links are consequently added to the network, along with the threshold increase. If one is interested by a reasonable variation of the topological properties of the network as compared to a threshold value of , it seems that the Jaro metric is the most appropriate, as this metric introduces less false positives (inappropriate similarities) than the others. The threshold range that can be associated to each metric is globally , and for Levenshtein, Jaro and Jaro-Winkler, respectively. We also examined the behavior of the metrics when no false positive is introduced and new similarities are all semantically meaningful. In this case, Jaro-Winkler gives the best results. Naturally the threshold ranges are lower in this case, and the topological properties are very similar to the ones obtained with a threshold value of . Globally, the use of the metrics to build composition networks is not very satisfying. As the threshold decreases, the false positive rate becomes very quickly prohibitive. This leads us to turn to an alternative approach. It consists in exploiting the latent semantics in parameters name. To extend our work, we plan map the names to ontological concepts with the use of some knowledge bases, such as WordNet [START_REF] Pease | Linking Lexicons and Ontologies: Mapping WordNet to the Suggested Upper Merged Ontology[END_REF] or DBPedia [13]. Hence, we could provide a large panel on the studied network properties according to the way similarities are computed to build the networks.

Fig. 1 .

 1 Fig. 1. Schematic representation of a WS , with two operations and and six parameters , , , , and .

Fig. 2 .

 2 Fig. 2. Example of a WS interaction network.

Fig. 3 .

 3 Fig. 3. Average degree in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles) and Jaro-Winkler (blue crosses) metrics.

Fig. 4 .

 4 Fig. 4. Maximum degree in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles) and Jaro-Winkler (blue crosses) metrics.

Fig. 5 .

 5 Fig. 5. Minimum degree in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles) and Jaro-Winkler (blue crosses) metrics.

Fig. 6 .

 6 Fig. 6. Transitivity in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles), and Jaro-Winkler (blue crosses) metrics.

Fig. 7 .

 7 Fig. 7. Degree correlation in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles) and Jaro-Winkler (blue crosses) metrics.

Fig. 8 .

 8 Fig. 8. Average distance in function of the metric threshold. Comparative curves of the Levenshtein (green triangles), Jaro (red circles) and Jaro-Winkler (blue crosses) metrics.

Table 2 .

 2 Parameters

	similarities from the	threshold values.	similarities are retrieved
	at the threshold.
	Metric	threshold	Number of retrieved	Number of	Percentage of
	value		similarities		false positives	false positives
	Levenshtein
	Jaro
	Jaro-Winkler

Table 3 .

 3 Additional appropriate similarities for each metric at the threshold of of false positives.

	Metric	Similarities
	Threshold
	Levenshtein	GetPatientMedicalRecords_PatientHealthInsuranceNu
		mber ~
		SeePatientMedicalRecords_PatientHealthInsuranceNu
		mber
		_GOVERNMENT-ORGANIZATION ~
		_GOVERNMENTORGANIZATION
		_GOVERMENTORGANIZATION ~ _GOVERNMENTORGANIZATION
		_LINGUISTICEXPRESSION ~ _LINGUISTICEXPRESSION1