Hafida Naïm
email: hafida.naim@etu.univ-amu.frmustapha.aznag

Mustapha Aznag

Nicolas Durand

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Semantic Pattern Mining Based Web Service Recommendation

Keywords: Web services, Recommendation, Topic models, Formal concept analysis, Concept lattice, Maximal frequent itemsets

This paper deals with the problem of web service recommendation. We propose a new content-based recommendation system. Its originality comes from the combination of probabilistic topic models and pattern mining to capture the maximal common semantic of sets of services. We define the notion of semantic patterns which are maximal frequent itemsets of topics. In the off-line process, the computation of these patterns is performed by using frequent concept lattices in order to find also the sets of services associated to the semantic patterns. These sets of services are then used to recommend services in the on-line process. We compare the results of the proposed system in terms of precision and normalized discounted cumulative gain with Apache Lucene and SAWSDL-MX2 Matchmaker on real-world data. Our proposition outperforms these two systems.

Introduction

Web services1 are defined as software systems designed to support interoperable machine-to-machine interaction over a network. They are "loosely coupled, reusable software components that semantically encapsulate discrete functionality and are distributed and programmatically accessible over standard Internet protocols". Web services are self contained, modular business applications that have open, internet-oriented and standards based interfaces. The explosion of web services with identical or similar functionalities over the internet has become a problem for the users. How can they find the best services that match their requirements from a large number of web services which have the requested functionality? Recommendation systems and selection techniques can be used to overcome this problem and assist users by recommending relevant web services from a large number of available web services [START_REF] Yao | Unified Collaborative and Content-Based Web Service Recommendation[END_REF].

Recent research efforts on web service recommendation focus on two approaches: collaborative filtering and content-based recommendation. Collaborative filtering approaches [START_REF] Yao | Unified Collaborative and Content-Based Web Service Recommendation[END_REF][START_REF] Zheng | QoS-Aware Web Service Recommendation by Collaborative Filtering[END_REF] are used in almost all recommendation systems. They find relevant services for the current user by collecting information from other similar users. For example, a list of services that many users like, can be used as recommendations for other users that share a large overlap of services with this list. Content-based approaches [START_REF] Blake | A Web Service Recommender System Using Enhancing Syntactical Matching[END_REF][START_REF] Cassar | Probabilistic Matchmaking Methods for Automated Service Discovery[END_REF] recommend web services on the basis of the similarity between the user request and the web service description (e.g., service functionalities). If the similarity between the user request and a service is high, this service is then recommended to the user.

In this paper, we propose a new content-based recommendation system. Its originality comes from the combination of probabilistic topic models and pattern mining to capture the maximal common semantic of sets of services. To the best of our knowledge, this is the first time that such approach combining the two domains is proposed. The core of the system is to identify the services which are very semantically linked. For this purpose, we defined the notion of semantic patterns. These latter correspond to maximal frequent itemsets of topics. Topics (or latent factors) correspond to a family of generative probabilistic models based on the assumption that documents (i.e., service descriptions) are generated by a mixture of topics where topics are probability distributions on words [START_REF] Steyvers | Latent Semantic Analysis: A Road to Meaning, chap[END_REF]. Topic models are used as efficient dimension reduction techniques which are able to capture semantic relationships between word-topic and topic-service [START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF]. The maximal frequent itemset discovery computes the maximal sets of items (i.e., topics), with respect to set inclusion, that appear together in at least a certain number of transactions (i.e., services) recorded in a database [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF]. The semantic patterns allow to group together the services which are similar. Indeed, to each semantic pattern, the services containing this pattern can be associated. The services of a semantic pattern are very interesting: they are semantically linked and maximal. In order to compute semantic patterns and the corresponding sets of services, we used frequent concept lattices [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF]. These sets of services are then stored in a special structure, called MFI-tree [START_REF] Grahne | Fast Algorithms for Frequent Itemset Mining Using FP-Trees[END_REF], in order to save space and perform quick searches by the recommendation engine. From a specified service, the recommendation engine uses this tree to find semantically similar services. The obtained services are then ranked and recommended to the user. For evaluation purposes, we conducted experiments on real-world data, and evaluated the quality of the recommended services. We also compared our system with two existing approaches: Apache Lucene and SAWSDL-MX2 Matchmaker.

The remainder of this paper is organized as follows. Section 2 provides an overview of related work. In Section 3 we describe in detail our service recommendation system. The experiments and the results are presented in Section 4. Finally, the conclusion and future work can be found in Section 5.

Related Work

Recommendation systems are assimilated to information filtering systems because the ideas and the methods are very close. We focus on two main types of filtering: content-based filtering and collaborative filtering. The interested reader can refer to [START_REF] Ricci | Recommender Systems Handbook[END_REF] for further information about recommendation systems.

There is a lot of works on recommendation systems especially in the case of web navigation. So, we present some works in this context before considering the context of web services. Patterns are particularly used for collaborative filtering. These systems are based, for instance, on frequent itemsets, maximal frequent itemsets, clustering, formal concept analysis (i.e., concept lattices) or markov model [START_REF] Suguna | An Efficient Web Recommendation System using Collaborative Filtering and Pattern Discovery Algorithms[END_REF]. The semantic aspects can be introduced in content-based approaches by using topic models or ontologies. In [START_REF] Mao | Modeling User Interests Using Topic Model[END_REF][START_REF] Xu | Modelling User Behaviour for Web Recommendation Using LDA Model[END_REF], the authors have computed topic models. The probabilistic topic model is Latent Dirichlet Allocation (LDA). They do not use patterns. Let us note that we do not use LDA but Correlated Topic Model (see Section 3.1). A notion of semantic patterns has been proposed in [START_REF] Maccatrozzo | A Semantic Pattern-Based Recommender[END_REF] but the definition does not correspond to ours. They do not consider topics. A semantic pattern is a path that connects a source type to a target type through pairs property-type. Our definition is: semantic patterns are maximal frequent itemsets of topics.

Let us consider the context of web services. Generally, every web service has a WSDL (Web Service Description Language) document that contains the description of the service. To enrich web service descriptions, several Semantic Web methods and tools are developed, for instance, the authors of [START_REF] Sivashanmugam | Adding Semantics to Web services Standards[END_REF] use an ontology to annotate the elements in web services. Nevertheless, the creation and maintenance of ontologies may be difficult and involve a huge amount of human effort [START_REF] Atkinson | A Practical Approach to Web Service Discovery and Retrieval[END_REF]. The content-based approaches and/or the non-logic-based semantic approaches [START_REF] Cassar | Probabilistic Matchmaking Methods for Automated Service Discovery[END_REF][START_REF] Ma | Efficiently Finding Web Services Using a Clustering Semantic Approach[END_REF][START_REF] Mohebbi | A Comparative Evaluation of Semantic Web Service Discovery Approaches[END_REF][START_REF] Nayak | Web service Discovery with Additional Semantics and Clustering[END_REF] aim to reduce the complexity of the discovery process by analysing the frequency of occurrence of some concepts and determine semantics which are implicit in service descriptions. These approaches generally use techniques such as information retrieval, data mining and linguistic analysis [START_REF] Mohebbi | A Comparative Evaluation of Semantic Web Service Discovery Approaches[END_REF]. As the context of web navigation, the collaborative filtering approaches are widely used in web service recommendation systems [START_REF] Yao | Unified Collaborative and Content-Based Web Service Recommendation[END_REF][START_REF] Zheng | WSRec: A Collaborative Filtering Based Web Service Recommender System[END_REF][START_REF] Zheng | QoS-Aware Web Service Recommendation by Collaborative Filtering[END_REF]. In [START_REF] Zheng | QoS-Aware Web Service Recommendation by Collaborative Filtering[END_REF], the authors propose a collaborative filtering based approach for making personalized quality of service value prediction for the service users. In another context, Mehta et al. [START_REF] Mehta | An Architecture for Recommendation Based Service Mediation[END_REF], propose an architecture for recommendation-based service mediation in which they take into account two more dimensions of service description: quality and usage pattern. The usage pattern permits to find applications with a similar usage pattern to the application making the request and then returns a recommendation list containing the services used by such applications.

As we can see, recommendation systems can use topic models or ontologies for considering semantics. Patterns are used especially for collaborative filtering and for capturing usages. The maximal frequent itemsets are not considered. We propose a content-based recommendation system leveraging probabilistic topic models and pattern mining (more precisely, maximal frequent itemset mining).

Web Service Recommendation System

In this section, we first give an overview of the proposed system. We then describe more in detail the different steps of our approach. The proposed system relies on the notion of topics and semantic patterns. Topic models are used to capture semantic relationships between word-topic and topic-service. Semantic patterns capture the maximal common semantic of sets of services. The services corresponding to semantic patterns are used by the system. Let us note that this work extends our previous works on probabilistic web services clustering and discovery based on probabilistic topic models [START_REF] Aznag | Correlated topic model for web services ranking[END_REF][START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF].

Figure 1 shows the overview of our system with the different steps involved. As shown in this figure, we can distinguish two kinds of process: online process and offline process. The different steps of the offline process are listed as follows:

(1) Topics extraction, (2) Semantic patterns extraction. Once all these tasks are done, we can easily recommend web services from a service selected by the user in the list of services returned by a discovery system. We note that this is the only task of the online process.

Topics extraction and cluster assignments

Topics (or latent factors) are a concept introduced by Probabilistic Topic Models [START_REF] Blei | A Correlated Topic Model of Science[END_REF]. They are a family of generative probabilistic models based on the assumption that documents are generated by a mixture of topics where topics are probability distributions on words. Topic models are used, in our context, as efficient dimension reduction techniques, which are able to capture semantic relationships between word-topic and topic-service interpreted in terms of probability distributions. In [START_REF] Aznag | Correlated topic model for web services ranking[END_REF][START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF], we investigated the use of three probabilistic topic models PLSA, LDA and CTM [START_REF] Blei | A Correlated Topic Model of Science[END_REF] to extract topics from semantically enriched service descriptions and propose a probabilistic method for web services clustering and discovery. The results obtained from comparing the three methods based on PLSA, LDA and CTM showed that the CTM model provides a scalable and interoperable solution for automated service discovery and ranking in large service repositories. In this paper, we use the Correlated Topic Model (CTM) [START_REF] Blei | A Correlated Topic Model of Science[END_REF] to extract latent factors from web service descriptions.

After the CTM model is trained, the distribution of textual concepts for each topic is known and all the services in the dataset can be described as a distribution of topics (i.e. a vector s = {z 1 , z 2 , ..., z K } where each dimension z k reflects the probability of that service description being generated by sampling from topic k. Let θ (s) refer to the multinomial distribution over topics in the service description s and φ (j) refer to the multinomial distribution over concepts for the topic z j . We create K clusters where K is the number of generated topics (i.e. a cluster for each topic). The distribution over topics θ (s) for service s is used to determine which topic best describes the service s. More precisely, if a probability distribution θ (s) over a specific z j when given a web service s is high, then the service s can be affected to the cluster C j . If a service s has more than one topic, the service will be assigned to each of the clusters corresponding to these topics [START_REF] Aznag | Leveraging Formal Concept Analysis with Topic Correlation for Service Clustering and Discovery[END_REF]. To simplify, we use the multiple topics assignment strategy to assign a set of topics for each service by selecting a topK topics. Thus, a service could be assigned to multiple clusters (e.g., the three best fitting clusters). This will increase the scope of each search. Multiple cluster assignments achieve higher recommendation accuracy. However, it comes at the cost of increased number of comparisons and computations (see Section 4).

Semantic pattern extraction

In order to define the notion of semantic patterns, we need to introduce some definitions. A data mining context is denoted by D = (T , I, R) where T is a set of transactions (i.e., web services), I is a set of items (i.e., topics), and R ⊆ T × I is a binary relation between transactions and items. Each couple (t, i) ∈ R denotes the fact that the transaction t is related to the item i (e.g., t contains i). A transactional database is a finite and nonempty multi-set of transactions. Table 1 provides an example of such database consisting of 6 transactions (each one identified by its "Id") and 8 items (denoted A . . . H). In our context, services are transactions and topics are items. For each service, we assign the best topics (see Section 3.1). This assignment forms the binary relation R.

An itemset is a subset of I (note that we use a string notation for sets, e.g., AB for {A, B}). An itemset is sorted in lexicographic order and is also called pattern. A transaction t supports an itemset X iff ∀i ∈ X, (t, i) ∈ R. An itemset X is frequent if the number of transactions which support it, is greater than (or is equal to) a minimum threshold value, noted minsup. The set of all-frequent Table 1. Example of transactional database.

Id Items 1 A C E G 2 B C E G 3 A C E H 4 A D F H 5 B C F H 6 B C E F H H 3 4 5 6 1 2 3 4 5 6 C 1 2 3 5 6 A C E 1 3 C E 1 2 3 6 B C E 2 6 C E G 1 2 C E H 3 6 C H 3 5 6 A H 3 4 F H 4 5 6 B C 2 5 6 O A C E G 1 B C E G 2 A C E H 3 A B C D E F G H O B C E F H 6 B C F H 5 6 A D F H 4 A 1 3 4
Fig. 2. Example of concept lattice (Bd + is encircled for minsup=2).

itemsets is A semantic pattern is a maximal frequent itemset of topics. To each semantic pattern, the transactions (i.e., services) containing this pattern can be associated. The services of a semantic pattern are very interesting: they are semantically linked and maximal. Thus, the proposed system uses these services. The minimum support threshold, minsup, allows to fix the minimum number of services for each semantic pattern. In order to extract the semantic patterns and their associated services, we compute the frequent concept lattice. Then, the set of services corresponding to each semantic pattern is selected and stored in a special structure called MFI-tree.

S = {X ⊆ I, |{t ∈ T , ∀i ∈ X (t, i) ∈ R}| ≥ minsup}.
Concept lattice computation and positive border extraction Given D, there is a unique ordered set which describes the inherent lattice structure defining natural groupings and relationships among the transactions and their related items. This structure is known as a concept lattice or Galois lattice [START_REF] Ganter | Formal Concept Analysis: Mathematical foundations[END_REF]. Each element of the lattice is a couple (I, T ) composed of a set of items (i.e., topics, the intent) and a set of transactions (i.e., services, the extent). Each couple (called formal concept) must be a complete couple with respect to R, which means that the following mappings (noted f and g) hold. For T ⊆ T and I ⊆ I, we have:

(1) f (T ) = {i ∈ I|∀t ∈ T , (t, i ) ∈ R} and (2) g(I) = {t ∈ T |∀i ∈ I , (t, i ) ∈ R}. f (
T ) returns items common to all transactions t ∈ T , while g(I) returns transactions that have at least all items i ∈ I. The idea of maximally extending the sets is formalized by the mathematical notion of closure in ordered sets. The operators h 1 = f • g and h 2 = g • f are the Galois closure operators. Let X be an itemset, if h 1 (X)=X, then X is a closed itemset. A formal concept is composed of a closed itemset and of the set of transactions containing this closed itemset. The frequent concept lattice is formed using the formal concepts that have at least minsup transactions in their extent. The "bottom" concept (i.e., (I, ∅)) is kept. Due to the fact that the intents of the frequent formal concepts form the set of all-frequent closed itemsets [START_REF] Pasquier | Efficient Mining of Association Rules Using Closed Itemset Lattices[END_REF] and that the set of all-maximal frequent itemsets is a subset of frequent closed itemsets, we can easily find Bd + (S) (i.e., the set of semantic patterns) from the frequent concept lattice. The positive border corresponds to the frequent formal concepts just above the bottom. Figure 2 presents the concept lattice obtained using the example of Table 1 Service pattern extraction and MFI-tree construction The result of the previous step is the set of formal concepts corresponding to the Bd + (S) (i.e., the set of semantic patterns). The proposed system selects the extents of these formal concepts to form the sets of services which will be used by the online recommendation engine. These sets of services are considered as patterns. To facilitate the recommendation, we store these patterns of services in a variant of FP-tree (Frequent Pattern tree) called MFI-tree (Maximal Frequent Itemsets tree) [START_REF] Grahne | Fast Algorithms for Frequent Itemset Mining Using FP-Trees[END_REF]. This allows a space saving and a quick search of the patterns containing a given service by using indexes. Every branch of the tree represents a pattern. Compression is acheived by building the tree in such way that overlapping patterns share prefixes of the corresponding branch. The tree has a root labelled with "root". Children of the root are item prefix subtrees. Each node in the subtree has four fields: item-name, children-list, parent-link and node-link. All nodes with same item-name are linked together. The node-link points to the next node with same item-name. A header table is constructed for items in the MFI-tree. Each entry in the header table consists of two fields, item-name and head of a node-link. The node-link points to the first node with the same item-name in the MFI-tree. Let us take a new example (more complete than the first one) where we have extracted the semantic patterns and then found these patterns of services: {{1, 8}{1, 3, 5}{2, 3, 5}{3, 5, 7}{3, 5, 8}{2, 3, 6, 8}}. Figure 3 illustrates the construction of the tree. We get the first pattern {1, 8}. It is inserted into the tree directly (see Figure 3 (a)). We then insert {1, 3, 5} into the tree (see Figure 3 (b)). Figure 3 (c) presents the complete tree.

Web service recommendation task

From a service s, the proposed system find the services present with s in the patterns of services computed in the offline process. These services are ranked and recommended to the user. Algorithm 1 present the search of recommended services from a service s by using the MFI-tree constructed in the previous step. It returns the items (i.e., services) present in the patterns containing s. The idea of the algorithm is to use the header table of the tree to access directly to the different patterns containing the item s. For each node N corresponding to s (Step 2), we need to find the common prefix (P X) of the patterns (Steps 3 to 8). It corresponds to go up to the root node via the parent links. Then we find all the possible ends of the patterns (i.e., the suffixes SX) (Step 10). The items of the prefix and of the suffixes are merged (Steps 11 and 12) and will be returned at the end of the algorithm. Let us take an example: the service 5 and the tree of Figure 3 (c). For the first node corresponding to 5, P X={1, 3} and SX={}, we have R={1, 3}. For the second node, P X={2, 3} and SX={}, so we have R={1, 2, 3}. For the last node, P X={3} and SX={{7}, {8}}. The services R to recommend are {1, 2, 3, 7, 8}. Let us note that it is possible to recommend services from a set of services S by intersecting the set of recommended services obtained for each service s ∈ S.

Once the recommended services are discovered using Algorithm 1, these services are ranked in order of their similarity score to the service request. Thus, we obtain automatically an efficient ranking of the recommended services. In our approach, we use the proximity measure called Multidimentional Angle (also known as Cosine Similarity); a measure which uses the cosine of the angle between two vectors. We calculate the similarity between the service request and each recommended web service by computing the Cosine Similarity between a vector containing the service request distribution over topics q and a vector containing the recommended service's distribution of topics p. The multidimensional angle between a vector p and a vector q can be calculated using Equation 1where t is the number of topics.

Cos(p, q) = p.q p . q = t i=1 p i q i t i=1 p 2 i t i=1 q 2 i . ( 1
)
Algorithm 1 MFI-tree based web service recommendation algorithm Require:

-s : a service -T : the MFI-tree containing the patterns of services Ensure: R: the set of recommended services 1: N ← T.header- The multidimensional angle takes values in the interval [0, 1] where 0 indicates no similarity and 1 indicates identical vectors.

Evaluation

Web services corpus and data preprocessing

The experiments are performed out based on real-world web services obtained from the WSDL service retrieval test collection called SAWSDL-TC32 . The WSDL corpus consists of 1088 semantically annotated WSDL 1.0-based Web services which cover 9 different application domains. Each web service belongs to one out of nine service domains named as: Communication, Education, Economy, Food, Geography, Medical, Military, Travel and Simulation. The dataset contains 42 queries (i.e., requests). A service request is defined as a service that would perfectly match the request. Furthermore, a binary and graded relevance set for each query is provided which can be used in order to compute Information Retrieval (IR) metrics. The relevance sets for each query consists of a set of relevant services and each service s has a graded relevance value relevance(s) ∈ {1, 2, 3} where "3" denotes high relevance to the query and "1" denotes a low relevance. Table 2 lists the number of services and requests from each domain.

To manage efficiently web service descriptions, we extract all features that describe a web service from the WSDL document. Before representing web services as a TF-IDF (Text Frequency and Inverse Document Frequency) vectors, we need some preprocessing. The objective of this preprocessing is to identify the textual concepts of services, which describe the semantics of their functionalities. There are commonly several steps: Features extraction, Tokenization, Tag and stop words removal, Word stemming and Service Transaction Matrix construction (see [START_REF] Aznag | Correlated topic model for web services ranking[END_REF] for more details). After identifying all the functional terms, we calculate the frequency of these terms for all web services. We use the Vector Space Model (VSM) technique to represent each web service as a vector of these terms. In fact, it converts service description to vector form in order to facilitate the computational analysis of data. In IR, VSM is identified as the most widely used representation for documents and is a very useful method for analyzing service descriptions. The TF-IDF algorithm is used to represent a dataset of WSDL documents and convert it to VSM form. We use this technique, to represent a services descriptions in the form of Service Transaction Matrix. In the service matrix, each row represents a WSDL service description, each column represents a word from the whole text corpus (vocabulary) and each entry represents the TF-IDF weight of a word appearing in a WSDL document. TF-IDF gives a weight w ij to every term j in a service description i using the equation:

w ij = tf ij . log( n nj )
where tf ij is the frequency of term j in WSDL document i, n is the total number of WSDL documents in the dataset, and n j is the number of services that contain term j. The observed textual concepts are represented in a Service Transaction Matrix (STM).

Protocol and Evaluation Metrics

To compute topics, we use the STM as training data for our implementation of the CTM model (based on the Blei's implementation3 , which is a C implementation of CTM using Variational EM for Parameter Estimation and Inference).

We analyse the impacts of the parameters minsup (i.e., the minimum support threshold) and assign (i.e., number of topic assignments) on the quality of the recommendations. For some minsup values and for some assign values, we adopted the following protocol: For the offline part: (1) Computation of the semantic patterns (by using CHARM-L [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF] to generate the frequent concept lattice), (2) Extraction of the patterns of services, (3) Construction of the MFItree. The steps to simulate the online part are: For each query present in the dataset: (4) Search the recommended services by using Algorithm 1, (5) Ranking of the list of recommended services, (6) Evaluation of the quality of the first n recommended services.

In order to compare our web service recommendation system (labelled Topic-MFI ) to two existing systems, Step 4 is redone twice by replacing our system by a syntax-based approach powered by Apache Lucene4 and a method from the SAWSDL-MX2 Matchmaker5 hybrid semantic matchmaker for SAWSDL services, respectively.

In the test collection, we have the queries together with the correct/expected web services (see Section 4.1). Thus, we estimate how well is a recommendation method by discovering services corresponding to each query in the data. After that, we compare the returned list of services with the expected one. Finally, we evaluate the accuracy of the recommendation system by using standard measures used in IR. Generally, the top most relevant retrieved services are the main results which are selected and used by the user. Thus, we evaluated the quality of the first n recommended services by computing Precision at n (Precision@n) and Normalized Discounted Cumulative Gain (N DCG n ). These are standard evaluation techniques used in IR to measure the accuracy of a search and matchmaking mechanism.

In our context, P recision@n is a measure of the precision of the service discovery system taking into account the first n retrieved services. Therefore, P recision@n reflects the number of services which are relevant to the user query. The P recision@n for a list of retrieved services is given by Equation 2where the list of relevant services to a given query is defined in the collection.

P recision@n = |RelevantServices ∩ RetrievedServices| |RetrievedServices| . (2)
N DCG n uses a graded relevance scale of each retrieved service from the result set to evaluate the gain, or usefulness, of a service based on its position in the result list. This measure is particularly useful in IR for evaluating ranking results. The N DCG n for n retrieved services is given by Equation 3where DCG n is the Discounted Cumulative Gain and IDCG n is the Ideal Discounted Cumulative Gain.

N DCGn = DCGn IDCGn , DCGn = n i=1 2 relevance(i) -1 log2(1 + i) . (3)
The IDCG n is found by calculating the DCG n of the first n returned services. n is the number of retrieved services and relevance(s) is the graded relevance of the service in the i th position in the ranked list. The N DCG n values for all queries can be averaged to obtain a measure of the average performance of a ranking algorithm. N DCG n values vary from 0 to 1. N DCG n gives higher scores to systems which rank a search result list with higher relevance first and penalizes systems which return services with low relevance. In addition to these metrics, we also compute some statistics (the number of computed patterns and the average size of a pattern) and we measure the query response times. All experiments were performed on a personal computer with a Intel Core2Duo processor, 2.4GHz, and 6GB of RAM.

Results and Discussion

Figure 4 presents the comparaison of average Precision@n values over 42 queries obtained for our method with different values of minsup (1 to 6) and assign (2 to 10 topics assigned to each service). A low or a high value of assign does not give the best results. The worst precision is obtained with assign = 7. Our method gives the higher precision values with assign = 4 (for each minsup values). So, we investigated more precisely the system when the assign value is equal to 4. Table 3 shows the number of service patterns obtained and the average number of services in a pattern, for assign = 4 and minsup varying from 1 to 6. As we can expected, the more the minsup value is low, the more the number of patterns is high. The average size of a pattern is more interesting. For instance, if minsup is equal to 1, a pattern can contain only one service. Nevertheless, we can observe that the average number of services is higher than the minsup value. The services are often correlated. Our system is able to find these correlations and is not restricted to the minsup value.

Figure 5 (left) and (right) present the average P recision@n and N DCG@n values, respectively. These measures are obtained over all 42 queries for our method Topic-MFI, ApacheLucene and SAWSDL-MX2 Matchmaker. In both cases, the results show that Topic-MFI gives a higher average P recision@n and N DCG n for all 42 queries. In fact, our method perform better than all methods. The results show that ApacheLucene and SAWSDL-MX2 were unable to find some of the relevant web services that were not directly related to some of the requests through keywords or logic descriptions. This reflects that the retrieved services obtained by our method are specific to the user's query. ApacheLucene and SAWSDL-MX2 have a low N DCG n because, as shown in the P recision@n results, both approaches are unable to find some of the highly relevant services. The results obtained for our method reflect the accuracy of our recommendation system.

Table 4 presents the average query response times for ApacheLucene, SAWSDL-MX2 and our method (Topic-MFI ) for all 42 queries. As we can see, Topic-MFI gives a faster query response time than the other search methods. Our recommendation system is efficient and not time-consuming.

Conclusion

We have introduced a new content-based recommendation system leveraging probabilistic topic models and pattern mining. Its originality comes from the combination of the two domains for capturing the maximal common semantic of sets of services. For this purpose, we defined the notion of semantic patterns which are the maximal frequent itemsets of topics. To compute these patterns and the corresponding sets of services, we used frequent concept lattices. In order to save space and perform quick searches among the computed sets of services, the system stores them in a special structure, called MFI-tree. The recommendation engine uses this tree to find services from a specified service. The obtained services are ranked and recommended to the user. The experimental results obtained on real-world web services show that our system outperforms ApacheLucene and SAWSDL-MX2 Matchmaker. In future work, we will use the approximation of frequent itemset border [START_REF] Durand | Approximation of Frequent Itemset Border by Computing Approximate Minimal Hypergraph Transversals[END_REF][START_REF] Durand | Frequent Itemset Border Approximation by Dualization[END_REF] in order to extend our system and recommend supplementary services based on approximate semantic patterns.

Fig. 1 .

 1 Fig. 1. Overview of the proposed recommendation system.

Fig. 3 .

 3 Fig. 3. MFI-tree construction.

  . The bottom is (A B C D E F G H, ∅). With minsup=2, the frequent formal concepts are above the dashed line. The formal concepts corresponding to the Bd + (S) are encircled. So, the semantic patterns are {AH, . . . , BCF H} and the corresponding sets of services are {{3, 4}{1, 3}{1, 2}{2, 6}{3, 6}{5, 6}}. Let us remark that the concepts of Bd + (S) can have more than minsup transactions in their extent (see Section 4.3).

Fig. 4 .

 4 Fig. 4. Comparaison of average Precision@n values over 42 queries obtained for our method with different values of minsup and assign (# topics assigned to each service).

Fig. 5 .

 5 Fig. 5. (Left) Comparaison of average Precision@n values over 42 queries. (Right) Comparaison of average NDCGn values over 42 queries obtained for our method Topic-MFI and other baseline methods.

  S}[START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF]. Let us take the example of Table1, if minsup=2 then the itemset H is frequent because 4 transactions support it (3, 4, 5 and 6). BG is not frequent because only 2 supports it. CE is frequent but not maximal because CEH is also frequent. The set of MFIs is the positive border Bd + (S) and is equal to {AH, ACE, BCE, CEG, CEH, BCF H}.

The set of all maximal frequent itemsets (MFI), w.r.t. set inclusion, in D is the positive border of S, noted Bd + (S), and is equal to {X ∈ S | ∀Y ⊃ X, Y / ∈

table [

 [

		s]; // node N: head of node links for s
	2: while N != null do
	3:	Parent ← N.parent-link; // parent node of N
	4:	PX ← ∅; // common prefix
	5:	while Parent != null do
	6:	PX ← PX ∪ {Parent.item-name};
	7:	Parent ← Parent.parent-link;
	8:	end while
	9:	SX ← ∅; // set of patterns starting from N
	10:	findSuffixes(N, ∅, SX); // find patterns starting from N
	11:	merge(SX); // union of all the patterns contained in SX
	12:	R ← R ∪ PX ∪ SX; // add services to recommend
	13:	N ← N.node-link; // next node corresponding to s
	14: end while
	15: return R;

Table 2 .

 2 Number of services and queries for each domain.

	Domain	Services Queries Domain Services Queries
	Communication	58	2 Medical	73	1
	Economy	358	12 Military	40	1
	Education	285	6 Simulation	16	3
	Food	34	1 Travel	164	6
	Geography	60	10

Table 3 .

 3 Number and size of the patterns obtained for assign-4 (according to minsup).

	minsup # patterns of services Avg. size of a pattern
	1	307	3.54
	2	205	5.01
	3	159	6.37
	4	137	7.21
	5	111	8.71
	6	101	9.71

Table 4 .

 4 Average query response times.

	Method	Avg. query response time (ms)
	Topic-MFI	68
	ApacheLucene	1163
	SAWSDL-MX2	3045

http://www.w3.org/standards/webofservices

http://www.semwebcentral.org/projects/sawsdl-tc

http://www.cs.princeton.edu/ ~blei/ctm-c/index.html

http://lucene.apache.org/

http://projects.semwebcentral.org/projects/sawsdl-mx


Hafida Naim
email: hafida.naim@etu.univ-amu.fr

Mustapha Aznag
email: mustapha.aznag@univ-amu.fr

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Nicolas Durand
email: nicolas.durand@univ-amu.fr

Probabilistic Approach for Diversifying Web Services Discovery and Composition

Keywords: Web services, Discovery and ranking, Composition, Service Dependency Network, Diversity, Topic Models, Formal Concept Analysis

Due to the increasing number of available web services, discovering the best service that matches a user requirement is still a challenge. In most cases the discovery system returns a set of very similar services and sometimes it is unable to find results for some complex queries. Therefore, integrating web service discovery and composition, taking into account the diversity of discovered results, in a unified way is still a big issue for web services. In this paper, we propose a novel service ranking algorithm for diversifying web services discovery results in order to minimize the redundancy in the search results. This algorithm chooses a set of selected web services based on relevancy, service diversity and service density. We also propose a new method to generate service dependency network using the Formal Concept Analysis (FCA) framework. The generated graph is used to select the composition of discovered web services set. Experimental results show that our method performs better than others baseline approaches.

I. INTRODUCTION

Recently, many activities in web services have drawn a great deal of attention. As one key motive for the increasingly rapid evolution of web service is the ability to help users to discover the best services that match their requirements. In this regard, service discovery and composition have been intensively studied [START_REF] Rodriguez Mier | An Integrated Semantic Web Service Discovery and Composition Framework[END_REF], [START_REF] Lin | A history record-based service optimization method for QoS-aware service composition[END_REF]. Web Service Discovery (WSD) is the mechanism of finding the best web services that match service users' needs. Several approches have been developed to improve the general web services management process. Some of them have been developed to search for both semantic and non-semantic web services discovery [START_REF] Klusch | Hybrid Adaptive Web Service Selection with SAWSDL-MX and WSDL-Analyzer[END_REF]. There exist logicbased approaches, non-logic based approaches, and hybrid approaches. The key problem of the logic-based and hybrid approaches is the complexity of the discovery process which makes it an intractable process over large service datasets [START_REF] Mohebbi | A comparative evaluation of semantic web service discovery approaches[END_REF]. The non-logic-based semantic approaches [START_REF] Cassar | Probabilistic Matchmaking Methods for Automated Service Discovery[END_REF] aim to reduce the complexity of the discovery process by analysing the frequency of occurrence of some concepts and determine semantics which are implicit in service descriptions. These approaches generally use techniques from different research fields such as information retrieval (IR), data mining and linguistic analysis [START_REF] Mohebbi | A comparative evaluation of semantic web service discovery approaches[END_REF].

Recently, some web service portals and search engines as Biocatalogue 1 and Seekda!2 , WS-Portal3 [START_REF] Aznag | WS-Portal; An Enriched Web Services Search Engine[END_REF] offer different features to facilitate the WSD task. In general, the search engines discover several very similar services and sometimes fail to answer some complex queries. To deal with this problem, two important issues should be considered: [START_REF] Rodriguez Mier | An Integrated Semantic Web Service Discovery and Composition Framework[END_REF] how can one select matching services that satisfy a given request q when the returned web services are very similar, and (2) how to compose multiple services to satisfy q when selected services don't fulfill this query.

Since the discovered web service set may contain redundant and useless services, thereby decreasing the degree of the user's satisfaction. To avoid redundancy and at the same time maintain the quality of the discovered services, the diversity should be taken into account in discovery system. In this paper, we present a novel service ranking method for diversifying web services discovery results. Diversifying search results has already been investigated in the context of document search on the Web [START_REF] Bache | Text-based measures of document diversity[END_REF]. Our system selects dissimilar web services from a number of top-K ranked web services considering the relevance, diversity and density measures.

In case of complex request, there is sometimes no single web service that can fulfill this request. So, we need to combine multiple web services to build a new service that satisfies the individual users' needs. In this paper, we adress the problem of web services composition (WSC) as a service network search problem. In this regard, many techniques have been proposed taking advantage of graph structures [START_REF] Hashemian | A Graph-Based Approach to Web Services Composition[END_REF], [START_REF] Oh | Effective Web Service Composition in Diverse and Large-Scale Service Networks[END_REF]. To begin with, the work presented in [START_REF] Hashemian | A Graph-Based Approach to Web Services Composition[END_REF] introduces an approach that uses a particular formalism called interface automata. The authors store the repository of web services as a graph that contains services information from a particular point of view. In [START_REF] Oh | Effective Web Service Composition in Diverse and Large-Scale Service Networks[END_REF], Oh et al. proposed a novel web service benchmark tool to adress the composition problems. First, they formulated the WSC problem in terms of AI planning and network optimization problems to investigate its complexity. Then, they analyzed publicly available Web service sets using complex network analysis techniques. In our work, we model the dependencies between a set of web services as a network where nodes representing services and edges representing invocations in-between.

The main contributions of this paper are listed below:

• A method for re-ranking discovered web service search results using diversification measures to minimize the redundancy.

• A new algorithm to construct the dependency web service network based on the Formal Concept Analysis (FCA) formalism.

• A method to find and select the optimal composition of discovered web services set. The rest of the paper is organized as follows: Section II presents the overview of the proposed system. Section III introduces our probabilistic service discovery and ranking. Section IV discusses how we build the dependency web service network and how we generate the compositions of the discovered web service set. Section V is devoted to the experimental evaluation. Finally, the conclusion and future work can be found in Section VI.

II. OVERVIEW OF THE PROPOSED SYSTEM

In our approach, we assume all service descriptions were written in the WSDL and/or SAWSDL. Generally, every web service has a WSDL (Web Service Description Language) document that contains the description of the service. The WSDL document is an XML-based language provides the specifications necessary to use the web service by describing the communication protocol, the message format required to communicate with the service, the operations that the client can invoke and the service location. To manage efficiently web service descriptions, we extract all features that describe a web service from the WSDL document. We also extract from WSDL documents all operations and their input/output parameters. These parameters are used to generate the web services network that describe the relationships between web services. The generated network is used to identify the composition of selected services (see Section IV for more details).

In [START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF] we investigated the use of probabilistic topic models to extract topics from service descriptions. Topics (or latent factors) are a concept introduced by Probabilistic Topic Models [START_REF] Steyvers | Probabilistic topic models[END_REF]. These are a family of generative probabilistic models based on the assumption that documents are generated by a mixture of topics where topics are probability distributions on words. In our work, a topic t is associated with a group of textual concepts (i.e. words) and/or semantic concepts that can appear in service descriptions and can be expressed as a probability distribution over words. Topic models are used, in our context, as efficient dimension reduction techniques, which are able to capture semantic relationships between word-topic and topic-service interpreted in terms of probability distributions. Based on the extracted topics, a set of matched services can be returned by comparing the similarity between the query and the services related topic.

Figure 1 shows the overview of our approach with the different steps involved. The service discovery phase is responsible for retrieving the Top-R ranked web service set. First, we represent the query in topic space to discover the set of top-K implicit topics that are semantically associated to the query. Based on the selected topics, a set of web services can be returned by comparing the similarity between the query and the related web services to these topics. Then, we use the similarity scores to rank and select the top web services. In order to minimize the redundancy in the search results, we rerank the top-ranked web service taking into account relevance, diversity and density (see section III). Next, we perform a search over the service dependency network to find the optimal composition. Before this phase, the operation dependency network is constructed using the Formal Concept Analysis (FCA) formalism. Next, we deduct the service dependency network (see section IV-A). This step is done one times. The service dependency network takes as input the Top-R ranked web services set and returns a sub-graph containing all possible service compositions. Then, a selection process is performed over the graph to find the optimal composition for the results of the query (see Section IV-B). Finally, the Top-R ranked web service and their optimised composition are returned.

III. PROBABILISTIC WEB SERVICE MATCHMAKING AND RANKING

Service discovery and selection process aim to find web services with user required functionalities. Our service discovery mechanism works by computing the degree of similarity between a query and a service descriptions in the topic space.

The work described in this section extends our previous work on probabilistic web services discovery and ranking based on probabilistic topic models [START_REF] Aznag | Correlated Topic Model for Web Services Ranking[END_REF], [START_REF] Aznag | Leveraging Formal Concept Analysis with Topic Correlation for Service Clustering and Discovery[END_REF]. The main idea underlying the work proposed in this paper is to increase the diversity of all discovered web services in order to minimize the redundancy in the search results. Indeed, several existing approaches do not take into account the redundancy which results from very similar and near duplicated web services. Diversifying search results has already been investigated in the context of document search on the Web [START_REF] Bache | Text-based measures of document diversity[END_REF].

In this paper, we propose a novel method for re-ranking web services taking into account relevance, diversity and density of selected web services obtained from the matchmaking and selection process. The main steps of our probabilistic service matchmaking and ranking are described as follow:

(1) discovering implicit topics related to the user query, (2) discovering web services related to the selected topics, (3) ranking discovered web services set, and (4) re-ranking the top-ranked web services.

After training our probabilistic model, the distribution of each topic is known and all the services in the registry can be described as a distribution of topics. Let θ s refers to the multinomial distribution over topics in the service description s and φ t refers to the multinomial distribution over words for the topic t [START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF].

Let q = {w 1 , w 2 , . . . , w n } be a user query that contains a set of words w i . First, we compute the query-likelihood model for q; denoted θ q ; by representing it as distribution over topics. Thus, for each topic t we compute the semantic similarity between query q and topic t based on the probability distribution φ t using Equation 1. The purpose of this step is to select the set of top-K implicit topics that are semantically associated to q. The most related topics are the ones that maximize the θ t q .

θ t q = P (q|t) =

w i ∈q P (wi|t) (1)
where P (w i |t) is the probability of having word w i given the topic t.

Based on the related topics retrieved for q, we can discover easily the set of web services associated to these topics. After discovering the web services related to user query q, we can rank them by determining their relevances to query q. We use the generated probabilities θ and φ as the base criteria for computing the similarity between retrieved services and a user's query q. To this end, we model information retrieval as a probabilistic query to the topic model. We note this as P (q|s i ) where q is the set of words contained in the query. Thus, using the assumptions of the topic model, P (q|s i ) can be calculated by equation 2.

P (q|si) = w k ∈q P (w k |si) = w k ∈q T j=1 P (w k |tj)P (tj|si) (2)
Where P (w k |t j ) is the probability of having word w k given the topic t j and P (t j |s i ) is the probability that the topic t j describes the service s i .

The most relevant services are the ones that maximize the conditional probability of the query P (q|s i ). Consequently, relevant services are ranked according to their similarity score to the query. The set of relevant services returned in this step, essentially contains very similar services that match with the user query. However, the ranking criteria applied in this process considers only the relevance information and often suffers from returning too many redundant web services. As we have already mentioned, we need to capture the diversity of selected web services to minimize the redundancy in the retrieved set. Therefore we seek to increase the diversity of the returned services that match with the user query by explicitly maximizing the distance between new services and already selected services. Selecting relevant web services with high density will retrieve more relevant services in the subsequent round, which leads to a better discovery performance.

In our approach, the service ranking procedure first takes a number of top-K ranked web services S q = {s 1 , . . . , s K } retrieved in the previous step. Then the system iteratively selects web services from S q to form a representative set of selected services S * q by simultaneously considering the relevance, diversity and density measures. More specifically, each candidate service s i is associated with a ranking score RS that is a linear combination of these measures, as expressed in equation 3. Thus, we obtain automatically an efficient ranking of the retrieved services.

RS = argmax

s i ∈Sq [α.M rel (q|si) + (1 -α)(M den (si) + M div (si, S * q ))] (3)
Where M rel (q|s i ) = P (q|s i ), M den (s i ) = Density(s i ) and M div (s i , S * q ) = Diversity(s i , S * q ) are measures of relevance (i.e. semantic similarity between the user's query q and a selected web service s i ), density and diversity of each web service in initial top ranked set S q where α ∈ [0, 1] a weighting parameter. More specifically, the selection process described in Equation 3 will be executed iteratively until S * q contains a predefined K * web services. It is worth mentioning that our method bears a close resemblance in spirit to the Maximal Marginal Relevance (MMR) ranking algorithm [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF] which was originally proposed for extractive document summarization. The MMR ranking algorithm [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF] is a greedy algorithm for ranking documents based on relevance ranking score and at the same time avoiding redundancy. Our algorithm extends the MMR algorithm by adding an extra term, which reflects the web service density and diversity.

In the following, we will explain how we calculate the density and diversity measures in our context. Density and diversity are one of the important factors in the defined selection process. There are several metrics to compute the distance between the semantic of two distributions θ x and θ y (i.e. in our case; θ x and θ y are the probability distributions over topics). In this paper, we consider the Kullback Leibler (KL) Divergence [START_REF] Steyvers | Probabilistic topic models[END_REF] defined as follows:

KL(θx, θy) = T i=1 θ i x log 2 θ i x θ i y (4)
Where θ i x = P (i | x) represents the proprability of the topic i given the service x. KL is not symetric and KL = 0 when θ i x = θ i y for all i. Distance between individual web services is measured by symmetric-KL divergence. Symmetric-KL divergence measures the degree of overlap between a given service and all other selected services.

We measure the density performance of the top K ranked web services in the initial retrieval results obtained in the matching/ranking process. In our work, we approximate the density in a region around a particular web service by measuring the average distance from that service to all the other services. Generally, large average Symmetric-KL divergence indicates that the web service is in a low service density region. Thus we use negative average Symmetric-KL divergence as described in equation 5 to approximate service density performance measure, which reflects the closeness of this service to the other services.

Density(si) = -1 |Sq| s j ∈Sq [KL(θs i , θs j ) + KL(θs j , θs i )] (5)
where |S q | is the number of selected web services in the initial retrieval results. A web service having a higher value of Density(s) is deemed to be closer to the others services in S q and thus to be more representative and less likely to be an outlier.

In order to diversify the selected web services, we compute the diversity measure of a candidate service with respect to the set S * q of already selected services, which is expressed as follows (i.e. Equation 6).

Diversity(si, S * q ) = argmax

s j ∈S * q 1 2
[KL(θs i , θs j )+KL(θs j , θs i )] (6)

IV. LATTICE BASED WEB SERVICES COMPOSTION

The web service composition is the fact of composing a set of available web services to fully satisfy a given request that cannot be satisfied by individual services. Formally, each web service ws can be defined as ws = (S in , S out ) where S in = {in 1 , in 2 , . . .} is its input parameters wheras S out = {out 1 , out 2 , . . .} represents its set output parameters. We suppose that the whole set of input parameters S in must be provided in order to invoke ws which in turn has to return the output parameters S out . Given a request q = {q in , q out } defined by its initial input parameters q in and its desired output parameters q out . When q can be satisfied just by composing a set of available web services as no individual web service can fulfill it. The Web Service Composition (WSC) problem is then defined as finding a set of web services {ws 1 , ws 2 , . . . , ws n } and compose them in a sequential or parallel way, such that: (1) ws i is invoked sequentially from 1 to n and (2) q out ⊆ (q in ∪ S 1 out ∪ S 2 out ∪ . . . ∪ S n out ). On one hand, The real-world composition problems are far more complex and hard to solve as the growth of web services. On the other hand, a composite Web service has to collaborate and communicate in order to fulfill a given request. This coordination between services requires also taking into account their dependencies. Thus, the real challenge has become to make easy investigating the real-world Web services composition. Networks constitute a convenient way to represent a collection of WS, allowing visualizing, analyzing and taking advantage of the relationships of dependency or similarity observed between them. They can be considered as complex networks and some authors previously used this approach to model web service collections in other contexts [START_REF] Oh | Effective Web Service Composition in Diverse and Large-Scale Service Networks[END_REF]. The composition problem therefore can be considered as a search problem in Service Dependency Network.

To model the dependencies between a set of web services in the form of networks, different entities can be used as nodes and links. First, nodes can be defined from the three levels of granularity (parameters, operations and web services) [START_REF] Oh | Effective Web Service Composition in Diverse and Large-Scale Service Networks[END_REF]. Second, links can indicate the parameter matching and operation invocation.

Definition IV-.1: Operation dependency network: An operation dependency network consists of a set of nodes representing operations and directed edges representing invocations in-between. There are two modes of invocation to indicate the possible interaction between two operations. The invocations are respectively denoted by full and partial-invocation. An operation f i partially invokes the operation f j if there is at least one output parameter of f i similar to an input parameter of f j . An operation f i fully invokes the operation f j if and only if for each input parameter of f j , there exists a similar output parameter of f i .

Definition IV-.2: Service Dependency Network: A web services dependency network is a directed graph G = (S, V ) where: S is a set of services: S = {s 1 , s 2 , . . . , s n } and V = {(s i , s j ) ∈ S * S), ∃f i ∈ s i , ∃f j ∈ s j : f i → f j }. f i ∈ s i indicates that the service s i offers the operation f i . f i → f j indicates that the operation f j depends on the operation f i . A web service dependency network can be defined from operation dependency network. Service networks are also distinguished according to the mode of invocation (full or partial invocation). In partial invocation, a directed edge is created between two services s 1 and s 2 if there is at least an operation of s 1 that partially invokes an operation of s 2 . In the case of full invocation, an arc (or directed edge) is created between two services s 1 and s 2 if there is at least an operation of s 1 which fully invokes an operation of s 2 .

A. Lattice based web service network building

In order to construct the web service dependency network, we have to build the operation dependency network. Therefore, we use the Formal Concept Analysis (FCA) formalism [START_REF] Missaoui | Algebraic operators for querying pattern bases[END_REF]. Our goal is to organize the web services operations into concept lattices according to their input/output parameters. In our approach, FCA takes as input a set of web services operations and its input or output parameter represented as a formal context and produces the set of all the formal concepts which form a concept lattice. A formal context is denoted by K = (O, P, I) where O is a set of objects (i.e. operations), P is a set of attributes (i.e. I/O parameters), and I is a binary relation between O and P (I ⊆ O ×P ). (o, p) ∈ I denotes the fact that object o ∈ O is in relation through I with attribute p ∈ P (i.e. Also read as o has p). In our context, a concept lattice defines a hierarchical representation of objects and attributes, in which a certain concept inherits all the extents (objects) of its descendants and all the intents (attributes) of its ascendants.

In our work, we use CHARM-L [START_REF] Zaki | Efficient Algorithms for Mining Closed Itemsets and Their Lattice Structure[END_REF] to build a concept lattice corresponding to web services and their topics. CHARM-L is an efficient algorithm for generating the concept lattice. The operation dependency network process consists of several steps:

• Construct binary contexts BC IN and BC OU T using dependencies between operations and their input/output parameters. end if 13: end for 14: return Set of directed edges constructed.

Based on the operation dependency network, we use the directed edge to build the web service dependency network as follow: For partial invocation case, a directed edge is created between two services s 1 and s 2 if there is at least an operation of s 1 that partially invokes an operation of s 2 . Similarly, for full invocation case, a directed edge is created between two services s 1 and s 2 if there is at least an operation of s 1 that fully invokes an operation of s 2 .

B. Finding optimal k web service compositions

The first step of the composition graph construction is the calculation of the relevant services. Based on the Top-K diversified ranked web services retrieved by our probabilistic service matchmaking and ranking (i.e. Section III), a set of discovered web services and their compositions can be returned by finding the service dependency sub-graph containing all possible service compositions. Once the sub-graph is retrieved, the next step is to reduce the graph size in order to improve the optimal composition. In [START_REF] Li; Yu | X: Scalable diversified ranking on large graphs[END_REF], Mei et al. proposed a new diversified ranking measure (i.e. DivRank) on large graphs, which captures both relevance and diversity based on the MMR ranking algorithm [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF]. Similary, we propose to extend DivRank algorithm by adding an extra term, which reflects the web services diversity and density as described in Section III.

We propose to use the expansion ratio to evaluate the diversity of Web services on service dependency sub-graph generated for the initial top-K ranked services. We consider the following definitions.

Definition IV-B.1: Expanded Set: Let S be the subset of nodes in the web service dependency network G = (V, E), the expanded set of S is N (S) such that |V | . We aim to find the L nodes (denoted by S) in a generated web service sub-graph that have the highest ranking scores RS (i.e. Equation 3) and the largest expansion ratio |N (S)| |V | . Formally, our goal is to maximize the following comprehensive ranking measure:

N (S) = S v ∈ (V -S)∃u ∈ S, (u, v) ∈ E.
H(S) = (1 -λ) s∈S RS(s) + λ |N (S)| |V | (7)
Where RS(s) denotes the score of node s (i.e. Equation 3), and λ ∈ [0, 1] is a tunable parameter that is used to tradeoff the score and the diversity in graph. The first term in Equation 7is the sum of scores over the selected nodes, which reflects the relevance, diversity and density of selected services. The second term is the expansion ratio of the selected nodes.

In general, larger expansion ratio indicates better diversity. Consequently, the Top-k diversified and optimal web services on a web service graph are the ones that maximize Equation 7.

V. EVALUATION A. Web services corpus

Our experiments are performed out based on real-world web services obtained from the WSDL service retrieval test collection called SAWSDL-TC3 4 . The WSDL corpus consists of 1088 semantically annotated WSDL 1.1-based Web services which cover 9 different application domains. Each web service belongs to one out of nine service domains named as: Communication, Education, Economy, Food, Geography, Medical, Military, Travel and Simulation. The dataset contains different queries (i.e. 42 requests). A service request is defined as a service that would perfectly match the request. Furthermore, a binary and graded relevance set for each query is provided which can be used in order to compute Information Retrieval (IR) metrics. Table I Before applying the proposed approach, we deal the WSDL corpus. The objective of this preprocessing is to identify the textual concepts of services, which describe the semantics of their functionalities. WSDL corpus processing consists of several steps: Features extraction, Tokenization, Tag and stop words removal, Word stemming and Service Transaction Matrix construction (see [START_REF] Aznag | Correlated Topic Model for Web Services Ranking[END_REF] for more details). The observed textual concepts are represented in a Service Transaction Matrix (STM). We use the STM as training data for our implementation of the CTM model (based on the Blei's implementation 5 , which is a C implementation of CTM using Variational EM for Parameter Estimation and Inference).

B. Web services discovery and ranking evaluation

Topic-RDD MMR Alpha Pr@5 Pr@10 Pr@15 Pr@5 Pr@10 Pr@15 0.00 In order to evaluate the accuracy of our approach, we compute two standard measures used in Information Retrieval: Precision at n (Precision@n) and Normalised Discounted Cumulative Gain (N DCG n ). These are standard evaluation techniques used in IR to measure the accuracy of a search and matchmaking mechanism. For this experiment, we use the service descriptions collected from the test collection. As described previously, the services are divided into nine domains and some service requests are provided together with a relevant response set for each query. The relevance sets for each query consists of a set of relevant services and each service s has a graded relevance value relevance(s) ∈ {1, 2, 3} where 3 denotes high relevance to the query and 1 denotes a low relevance.

1) Precision@n: In our context, P recision@n is a measure of the precision of the service discovery system taking into account the first n retrieved services. Therefore, P recision@n reflects the number of services which are relevant to the user query. The precision@n for a list of retrieved services is given by Equation 8:

P recision@n = |RelevantServices ∩ RetrievedServices| |RetrievedServices| (8)
Where the list of relevant services to a given query is defined in the test collection.

2) Normalized Discounted Cumulative Gain: N DCG n uses a graded relevance scale of each retrieved service from the result set to evaluate the gain, or usefulness, of a service based on its position in the result list. This measure is particularly useful in Information Retrieval for evaluating ranking results. The N DCG n for n retrieved services is given by Equation 9.

N DCGn = DCGn IDCGn (9)
5 http://www.cs.princeton.edu/~blei/ctm-c/index.html

Where DCG n is the Discounted Cumulative Gain and IDCG n is the Ideal Discounted Cumulative Gain. The IDCG n is found by calculating the DCG n of the first n returned services. The DCG n is given by Equation 10.

DCGn = n i=1 2 relevance(i) -1 log2(1 + i) ( 10
)
Where n is the number of retrieved services and relevance(s) is the graded relevance of the service in the ith position in the ranked list. The N DCG n values for all queries can be averaged to obtain a measure of the average performance of a ranking algorithm. N DCG n values vary from 0 to 1. We evaluated the effectiveness of our probabilistic service matchmaking and ranking based on the relevance, diversity and density measures (labelled Topic-RDD) by calculating the P recision@n and N DCG n . The sample queries (i.e. 42 queries) provided in the dataset are all in the form of SAWSDL documents and contain the semantic requirements together with a text description of the queried functionality. Our method Topic-RDD proposed in this paper is compared with a syntax-based approach powered by Apache Lucene6 and also method from the SAWSDL-MX2 Matchmaker7 hybrid semantic matchmaker for SAWSDL services [START_REF] Klusch | Hybrid Adaptive Web Service Selection with SAWSDL-MX and WSDL-Analyzer[END_REF]. Our method is also compared with a baseline ranking algorithm Maximal Marginal Relevance (MMR) [START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF] (labelled MMR) which takes into account the diversity in search results set in the context of feedback documents retrieving. MMR measure is defined as follow:

M M R def = argmax s i ∈R\S [α.Sim(q|si) -(1 -α) max s i ∈R Sim(si, sj)] (11)
Where R is the initial ranked web services set and S is the subset of services in R already selected; R \ S is the set difference. α is weighting parameter. Sim(q, s) = P (q|s) (i.e. Equation 2) is the similarity metric used in service retrieval and relevance ranking between services and a query. Generally, the top most relevant retrieved services are the main results which are selected and used by the user. The Topic-RDD MMR Alpha NDCG@5 NDCG@10 NDCG@15 NDCG@5 NDCG@10 NDCG@15 0.00 averaged P recision@n and N DCG n were measured for up to the first 15 retrieved services from the complete list of results. In Information Retrieval, N DCG n gives higher scores to systems which rank a search result list with higher relevance first and penalizes systems which return services with low relevance.

For our method Topic-RDD and MMR algorithm, the 42 queries are represented in a vector of topics using Equation 1and then matched to the services in topic space using a mechanism described in Section III. For SAWSDL-MX2, the search queries are submitted using the SAWSDL-MX user interface. For the ApacheLucene approach, the text descriptions taken from the query template are used as the query string.

In our experiments, we analyse the impacts of the parameter α ∈ [0, 1] (i.e. Equation 3) which is leveraged to tradeoff the web servicres relevance, density and diversity. The average P recision@n and N DCG@n values are obtained over all 42 queries for Topic-RDD and MMR taking into account different values of α. Setting α = 1, the system uses only the relevance measure to select the web services that match with user's query; if α = 0, the algorithm selects web services only based on its diversity and density performance measures. The results are shown in Tables II and III respectively and show that our method gives a higher precision when the three measures (relevance, diversity and density) are combined to select best web services that match with user's query. The comparison of average P recision@n (i.e. Table II) shows that our probabilistic service discovery and ranking performs better than the MMR algorithm for all values of α. As can be seen from these results, our method gives a higher precision when α = 0.75.

The average P recision@n and N DCG@n values are also obtained over all 42 queries for ApacheLucene, SAWSDL-MX2 Matchmaker. The results are shown in Figure 2 and 3 respectively. In both cases, the results show that our method Topic-RDD gives a higher average P recision@n and N DCG n for all 42 queries. In fact, our method perform better than all methods. The results show that ApacheLucene and SAWSDL-MX2 were unable to find some of the relevant web services that were not directly related to some of the requests through keywords or logic descriptions. This reflects that the retrieved services obtained by our method are specific to the user's query. ApacheLucene and SAWSDL-MX2 have a low N DCG n because, as shown in the P recision@n results, both approaches are unable to find some of the highly relevant services. Our method based on the probabilistic model used the information captured in the latent factors to match web services based on the service relevance, density and diversity. The results obtained for our method reflect the accuracy of our ranking system. In order to evaluate the structure of web services dependency networks extracted from the SAWSDL-TC3 collection, we compute several properties defined as follow:

C. Service dependency network structure evaluation

• Density: is defined as the number of links divided by the number possible. If self-loops are excluded, then the number possible is n(n-1)/2. If self-loops are allowed, then the number possible is n(n+1)/2. • Diameter: the maximum distance between any pair of nodes in the graph. • Degree: is the number of links connected to a node. The average degree represent the average value of degrees in the whole network.

• Transitivity: a network transitivity corresponds to its density of triangles, where a triangle is a structure of three completely connected nodes.

Figure 4 show the exact service dependency network from SAWSDL-TC3. The different values obtained for principal network properties are shown in Table IV. The exact service dependency network exhibits the same global structure as the approximate service dependency network (i.e. table IV). We have the same web service nodes whether we use partial or full invocation mode. The number of vertices is 1088; this value corresponds to the number of wsdl files in the collection test SAWSDL-TC3. Network nodes are distributed among large, small components, and a set of isolated nodes. In the exact service dependency network, there is less directed edges (or arcs) between web service nodes than in the approximate service dependency network. Indeed, directed edges represent the existence of fully or partially invocable operations between web service nodes. Partially invocable operations include a set of fully invocable operations. We can observe also that the approximate service dependency network has the highest transitivity. This is due to the fact that this network has the highest number of directed edges. The exact service dependency network is characterized by its lower density. This is way it can be efficient to be minded first to search for composition. Note also that the diameter tells us about the number of operations required in large compositions. It is defined as the greatest distance between any pair of nodes in a graph. In this paper, we proposed a probabilistic approach for discovery of web services and their compositions in order to minimize the redundancy and increase the user's satisfaction. A diversified web service ranking algorithm is proposed to find the top-k diversified web service ranked set based on their relevance, diversity and density. In our approach, we use the probabilistic topic models to extract topics from semantic service descriptions. The generated topics are used as the base criteria for computing the relevance, service diversity and service density measures. We also proposed a method to construct the web service dependency network based on the Formal Concept Analysis formalism. The service dependency network is used to select the composition of discovered web services set. An algorithm for finding top-k optimal web services compositions is also proposed in this paper. Experimental results on a real world web service dataset show that the proposed approach improves the web service recommendation performance in terms of precision. The results show that our method gives a higher precision when the three measures (i.e. relevance, diversity and density) are combined to select best web services that match with user's query.

In future work, we will propose a method to evaluate and rank community detection algorithms. To achieve this goal we will consider a probabilistic topic based approach to define a new measure called semantic divergence of communities. The proposed method for generating web services network will be used to construct the services graph that will be used as input to communities construction.

Fig. 1 .

 1 Fig. 1. An overview of our proposed system.

  from selected operation op to each operation in opSet 12:

Definition IV-B. 2 :

 2 Expanded Ratio: The expansion of set S is defined as |N (S)| where N (S) is the Expanded Set and |N (S)| is its cardinality of N (S). The expansion ratio is defined as σ = |N (S)|

Fig. 2 .

 2 Fig. 2. Comparison of average P recision@n values over 42 queries.

Fig. 3 .

 3 Fig. 3. Comparison of average N DCGn values over 42 queries.

Fig. 4 .

 4 Fig. 4. Exact service dependency network (Full invocation)

  : for each op om ∈ O = {o1, . . . , oM } do

	Algorithm 1 Operation dependency network building
	Require:
	-	O = {o1, . . . , oM } Set of service operations and their
		I/O parameters.
	-	CLIN : Concept Lattice operation/input parameters.
	-	CLOUT : Concept Lattice operation/output parameters.
	-	SearchType: Exact or approximate search.
	Ensure:
	-	A set of directed edges retrieved.

• Build Concept Lattices CL IN and CL OU T from BC IN and BC OU T respectively. • Construct operation dependency network by performing the operation search in CL IN and CL OU T (i.e. Algorithm 1). 1

  lists the number of services and requests from each domain.

	#	Domain	Services	Queries
	1	Communication	58	2
	2	Economy	358	12
	3	Education	285	6
	4	Food	34	1
	5	Geography	60	10
	6	Medical	73	1
	7	Military	40	1
	8	Simulation	16	3
	9	Travel	164	6
		Total	1088	42
		TABLE I
	NUMBER OF SERVICES AND QUERIES FOR EACH DOMAIN

TABLE II COMPARISON

 II OF AVERAGE PR@N VALUES OF OUR METHOD TOPIC-RDD AND BASELINE MMR ALGORITM[START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF] OVER ALL 42 QUERIES.

		0.748	0.750	0.726	0.686	0.695	0.710
	0.10	0.748	0.750	0.726	0.686	0.695	0.710
	0.25	0.748	0.750	0.726	0.686	0.698	0.712
	0.50	0.748	0.750	0.729	0.705	0.717	0.715
	0.75	0.748	0.752	0.731	0.705	0.719	0.712
	0.90	0.748	0.750	0.726	0.700	0.714	0.712
	1.00	0.724	0.714	0.699	0.724	0.714	0.699

  VALUES OF OUR METHOD TOPIC-RDD AND BASELINE MMR ALGORITHM[START_REF] Carbonell | The use of MMR, diversity-based reranking for reordering documents and producing summaries[END_REF] OVER ALL 42 QUERIES.

		0.537	0.578	0.599	0.435	0.478	0.580
	0.10	0.540	0.579	0.599	0.435	0.478	0.580
	0.25	0.540	0.579	0.598	0.435	0.479	0.581
	0.50	0.540	0.580	0.599	0.440	0.487	0.586
	0.75	0.544	0.582	0.598	0.437	0.484	0.581
	0.90	0.525	0.565	0.598	0.443	0.484	0.584
	1.00	0.542	0.597	0.642	0.542	0.597	0.642
				TABLE III
	COMPARISON OF AVERAGE NDCG@N

https://www.biocatalogue.org/

http://webservices.seekda.com/ (the portal is no longer available.)

http://wsportal.aznag.net/

http://www.semwebcentral.org/projects/sawsdl-tc

http://lucene.apache.org/

http://projects.semwebcentral.org/projects/sawsdl-mx