Service discovery has been adopted in distributed environments and recently in social networks. Existing approaches for service discovery are often based on matching techniques, which only capture common quality of service (QoS) criteria while ignoring the contribution of the social aspect. The discovery problem increases when the number of available services is important and no means to distinguish between two or many providers offering the same service. To overcome this issue, we propose a trust measure defined as the combination of two dimensions namely trust in sociability and trust in expertise. The problem is growing when no central control can be fixed due to the distributed nature of social networks. To cope with centrality related issues, we propose an agent-based service discovery approach in which each user in the social network is assigned an autonomous and non malicious agent equipped with a bounded set of services with their advertised QoS values. Endowed with a limited view of the social network, the agent acts locally on behalf of its user to discover trustworthy providers with good services. The search propagation process within the social network is ensured by means of a distributed referral system where agents cooperate and evaluate referrals based on a distributed knowledge and a decentralized decision-making.
Current research in service discovery (see [PKPS02, SPAS03, RKM04] for example) are based on semantic and/or structural matching techniques between service requester needs and web services description i.e., functional and non-functional properties and follow a centralized service registries used by Universal Description, Discovery, and Integration (UDDI). However, with the emergence and rapid proliferation of media and social applications especially social networks (SNs), agents show the willingness to use their SNs to find services as well as to share services with others. Some studies [GA05, MSW+11] have shown that SNs acts as a rich source for gathering information and services. Then, if we wish to rely on SNs for service discovery, we need to figure out how to capitalize on retrieved information to determine trustworthy providers with good services. Due to its limited view, a single agent is not able to discover relevant providers locally, and it needs some assistance from its acquaintances or acquaintances’ acquaintances to locate them i.e., analyzing SN structure. Agents interact by exchanging messages while evaluating the nature of the relationship and follow the relevant path to find trustworthy providers. The theory of Six Degrees of Separation claims that it is possible to reach anyone through a chain of acquaintances that has no more than five intermediaries. Humans are particularly good for finding these short paths [SJ05]. However, it is not that obvious in practice and especially in distributed environments such as SNs. Previous works [YS03, MHDC10, BBB10] don’t consider the semantic aspect of relationships between agents and deal with a single-relation social network. However, the present work considers different relationship types between agents such as friendship, family relationship or, business relationship. Thus, our service discovery approach is established in a Multi-Relation Social Network (MRSN). In this paper we propose an agent-based and trust-oriented service discovery approach using a distributed referral system in multi-relation social networks that addresses the following challenges.
First, one of our main concerns in service discovery is the trust aware. A requester agent prefers commonly providers that not only propose needed services but also that can be trusted before using their services. If the requester knows that discovered services are offered by trustworthy providers, he will be more confident. For instance, when searching for babysitting service in a MRSN, the requester agent would grant more trust to a family member rather than a friend, still less to a colleague to look after his child. Such trust consideration influences the agent’s decision making when choosing a counterpart to interact with. In this case, trust should be added as an additional step after traditional phases in services discovery. So that once a requester agent has discovered which providers perform the requested service, trust may be useful to rank them in terms of trustworthiness for that service. In this work, we take the stance that trust is compositional, the overall evaluation on an agent is obtained as a result of the combination of different measures. Concretely, trustworthiness towards providers and their offered services is built upon two dimensions: trust in sociability and trust in expertise. High sociability gives an indication about service provider confidence and high expertise gives rise to good services. More specifically, trust in sociability is computed to evaluate the level of trust a requester may have in a provider. Based on the analysis of the MRSN graph and the extracted information, three measures are computed: the centrality degree of a provider which gives an indication about it social power (viz. social position), the proximity in the SN between the provider and the requester (viz. social proximity ), and the ties between them based on the comparison of their profiles and social acquaintances (viz. social similarity ). All of theses measures take into account the semantic aspect of the relationships between agents. Trust in expertise is computed to evaluate the level of trust a requester may have in a service based on the number and ratio of successful past use of the service (viz. usability and reliability ) as well as requester’s feedbacks (viz. quality rate).
Second, for a given query, locating trustworthy providers with good services is often beyond the local view of the requester agent. It requires the involvement of its social acquaintances (i.e., neighbors in the MRSN graph) and even includes the involvement of the acquaintances’ acquaintances. Agents can help each others to find good services by recommending trustworthy providers that have been useful to them in the past. Furthermore, the distributed nature of the environment and the network topology contains other aspects that need to be taken into account. To propagate the search in SN, we rely on a referral system. A referral system is a multi-agent system (MAS) in which agents represent users and act on behalf of them to discover trustworthy providers with good service. Endowed with a limited view of the environment, agents cooperate by giving, pursuing and evaluating referrals [YS03]. In both [YS03] and [YVS99], the referral system is used for searching SN but these approaches present the following limits: they assume a centralized decision-making wherein the requester’s agent collects all possible referrals and decides to continue the search by contacting some of the suggested referrals.
In this work, we distribute the searching process by spreading out the query among cooperative agents with respect to the SN topology. Unlike approaches in [YS03, YVS99], we do not consider a fixed central agent. Conversely, agents cooperate to locate trustworthy recommenders 1 and providers with good services based on a distributed knowledge about their acquaintances’ expertise. Cooperation is established with a decentralized decision-making. The remainder of the paper is organized as follows. In the next section we present related work on service discovery with trust, and on agent-based models in distributed environments. Section 3 defines the main concepts used in this work and presents an example to illustrate our problem. In Section 4, we describe our trust model developed to evaluate the trustworthiness of providers and their offered services. Afterwards, we presents in section 5 our agent-based referral approach along with a description of our distributed search algorithm. Section 6 discuss implementation and evaluation aspects of our work. Section 7 gives the conclusion and the ongoing work.
1Recommenders are agents that do not have useful services but may be well connected and help by proposing pertinent referrals.
To propagate the search in a SN, our approach uses a referral system. A referral system is a MAS where agents are capable of giving and following referrals [YS03]. In [YVS99, YS03], a referral system is used for searching SNs with a centralized decision-making. The requester’s agent collects all possible referrals and decides to continue the search by contacting some of the suggested referrals. However, due to the distributed characteristic of the SN, it is not possible to gather all information by a single agent and make thereafter a correct trust evaluation. To address that, a later work [SJ05] introduces decentralized search algorithms in networks using homophily and degree disparity. Their algorithms have been designed for searching peer-to-peer distributed networks. However, despite enhancements in decision making and searching, some SN features are missing as for example the multirelation aspect of SNs or the trust consideration between agents. Our work is similar to the work presented in [ESAA04, HYY+13]. Both are based on a structured peer-to-peer system. In [HYY+13] authors propose Chord4S, a Chord-based decentralized service discovery approach that supports service description distribution and discovery in a P2P manner. A service query can be submitted to any node, and this node, if it does not store the required service description, is able to route the query to an appropriate node for resolution. This proposal do not address trust related issues, there is no mechanism for assessing the quality of the returned services nor the trustworthiness of the providers. The discovery process is based only on the functionality of the Web services which is not sufficient in many cases where several providers may offer functionally equivalent services. To address that, Emekci et al. propose in [ESAA04] a Chord-based structured peer-to-peer framework for Web service discovery in which services are located based on their functionalities and their behavior. Once the qualifying services are discovered, they are ranked based on a reputation model. This model is defined as the combination of two measures which are the quality of the offered service and the trustworthiness in its provider. Both quality and trust measures are computed as the average of their respective ratings over last 6 months. However, this reputation model is simple and elementary. Authors did not precise how providers are evaluated nor what type of quality of service is considered. Moreover, they did not take into account the semantic aspect of the relationships between peers.
To discover trustworthy providers with good services, many approaches have investigated trust as far as expertise is concerned [LHZ+12, LCM12]. Trust in expertise is concerned with the evaluation of past interactions between users and services. For instance, Li et al. [LHZ+12] capitalizes on users’ feedbacks including ratings, opinions and relevant comments after use to compute service reputation. Another recent work [LCM12] proposes an approach for using quality of past experiences as a criterion for web service selection, including an analysis of the different influence factors that may affect the perceived quality of the end-user. In spite of the added value of these retrieved information to evaluate trust between agents, trust in expertise dimension is insufficient to make a significant evaluation. Usually, in MAS the trust between two agents is based on another dimension called the trust in sociability. In this regard, we can find some interesting approaches that study trust from this point of view. We retain the works of Castelfranchi et al. [CF98] and Sabater et al. [SS02]. In [CF98], authors claim that the notion of trust is crucial in agent’s theory and in MAS. An agent must trust another agent to delegate a task. Trust model is based on the expertise of the counter party regarding the task (viz. core trust) and on its willingness to achieve this task (viz. reliance). In [SS02], Sabater et al. propose a model for reputation called REGRET which takes into account, the social dimension. In another work [BBB10], Bansal et al. evaluate providers’ trustworthiness based on the centrality degree that gives an indication on their prestige in the network. However, this is a poor definition of trust, since it just uses a single measure, the centrality degree. In this work, we evaluated trust in providers based on sociability as well as expertise. Moreover, we do not consider a fixed central agent but we promote agents to cooperate in order to locate trustworthy providers with good services based on a distributed knowledge concerning acquaintances’ expertise. Cooperation is established with a decentralized decision-making. We distributed the referral system by spreading out the query among agents with respect to the SN topology. 3
This section presents an example to illustrate our mechanism. This example will be used all along the paper. We describe in further detail the overall concepts used in this work, i.e., social networks, services, user needs, and software agents. 3.1
To better illustrate the service discovery issues and how they are dealt by our proposed solution, let us consider a case study on a travel scenario. Figure 1 presents a SN of a user namely Bob. Bob is modeled by agent a0. In this SN, there are web services from on-line travel agencies as well as freelance service providers. Providers may offer more than one service at the same time. Bob, the requester is a researcher and has to travel oversees frequently. To do this, he formulates a query containing required services as well as constraints (for example, price and total duration). The normal routine in his travel includes transportation from home to the airport, flight to the destination city, transportation from the airport to the hotel, hotel accommodation, and sight seeing the places in the available free time. Moreover, Bob may express his preferences over relationship types (for example, in figure 1 he would grant more trust to a friend members than to a partner, still less to a public one) and fixes a threshold for the trust. We consider a particular kind of complex networks, the multi-relation social network (MRSN) which takes into account the semantic aspect of the relationship linking two nodes. The relationships can be of different types. For example, if we consider two types, R1 can be a friend relationship and R2 can be a partner relationship. A multi-relation social network (MRSN) is modeled by an undirected graph, where nodes represent agents and, an edge between two nodes indicate a symmetric social relationship between the agents 2.
Definition 1 Given a set V of agents and a set R of types of symmetric relationships with R = {R1, R2, ..., Rr}, a multi-relation social network (MRSN) is a connected undirected graph G = (V, E), in which each Ei ⊂ E = {E1, E2, . . . , Er} is the set of edges with respect to the i-th relationship. In other words, an edge (ak, aj ) ∈ Ei represents a social relationship of type Ri between ak and aj .
In the MRSN graph, the notion of neighborhood of an agent can be expressed as follows: Definition 2 Given an M RSN graph G = (V, E), the neighborhood of an agent ak regarding a type of relationship Ri ∈ {R1, R2, ..., Rr}, denoted NRi (ak), is defined as NRi (ak) = {aj ∈ V | (ak, aj ) ∈ Ei}.
For example, the neighborhood of agent Bob in figure 1 according to friend relationship is Nfriend(a0) = {a3, a6}. In the MRSN, each agent ak cooperate with a subset of agents, called SAk, that represents ak’s local view in the MRSN such as SAk = ∪ NRi (ak). For instance, in figure 1, SA0 = {a2, a3, a4, a5, a6, a7} is the social
Ri acquaintance of agent a0. 3.2.2
A service is described in terms of functionality, inputs and outputs.
Definition 3 A service s is a triplet (in, out, f ) where in is a set of inputs required to use the service, out is a set of outputs provided at the completion of the service and f is a functionality describing the provided capacity. For example, consider a flight service offered by the agent a4 in figure 1. This service is described as follow: in= {departure, arrival, check in, check out}, out= {online invoice, price} and, f= {Flight Booking}.
3.2.3
A user communicates his needs by expressing a set of requirements and constraints on the requested services. Definition 4 A query Q is a quadruple (F, C, U, α) where F = {s1, s2, ..., sl} are required services, C = {c1, c2, ..., cr} is a set of constraints given over services, U : R → N is an utility function expressing user’s preferences over relationship types, and α ∈ [0, 1] is a trust threshold.
To illustrate the user query, let us consider the previous example. Suppose that Bob, the requester, has the intention to leave from Berlin to Paris to attend a conference on the May 5th until May 11th. He requires a 3-star hotel at least which is max 20 mn walking distance from the conference venue. Bob prefers to travel with friends rather than with partners still less by public transports and he requires service providers with a trust value greater than 0.7. In this example, the user query is defined by F= {Transportation service, Hotel service}, and C= {Hotel 3-star, Hotel location: ”max 20 mn walking distance”}. His preferences over relationship types are expressed as follows: Rfriend Rpartner Rpublic. These preferences are modeled in the query by the utility function such as: U (f riend) = a, U (partner) = b, and U (public) = c, with a ≥ b ≥ c. For example, if the requester prefers twice more the first relationship to the second one, than the utility of the second relationship will be double the value of the first one (i.e. b = 2a). This means that the utility of friend type edge is twice the utility of the partner type edge. This allows to favor paths that uses the minimum number of different kind of relationships regarding the requester’s preferences. If we suppose that a = 1, Bob’s preferences become U (f riend) = 1, U (partner) = 2 and U (public) = 4, and his trust threshold α = 0.7. 3.2.4
In the MRSN graph, each user is assigned an autonomous agent ak endowed with a bounded set of services with their advertised QoS values and acts on behalf of him to discover trustworthy providers with good services.
An agent ak is defined as a 3-modules structure <RM, CM, KM> with: • RM = <M C, T C> is the reasoning module with M C the matching component and, T C the trust component. • CM is the communication module whose role is to structure the messages built by the agent and handles the received ones. • KM = <Sk, P ITk> is the knowledge module with Sk = {sk1, . . . , skm} a set of offered services and P ITk a Personal Interaction Table. Each record in the P ITk (see table 1) contains the following elements: an acquaintance agent aj ∈ SAk, the profile P rj of aj , the social acquaintances set SAj of aj and the set of services Sj provided by aj .
Acquaintance
Profile • Agents have limited view in the SN, they know only agents that belong to their social acquaintance set. • Agents perform decentralized decision-making for contacting other agents. • Agents do not act maliciously and don’t lie while exchanging message, they have the inhered good will to fulfill user’s needs. 4
Trustworthiness is evaluated over two dimensions: sociability and expertise. High sociability indicates relevant providers and good recommenders, and high expertise gives rise to good services.
Trust in sociability (ST) evaluates the social trustworthiness that an agent ak may have towards an agent aj . Based on the analysis of the MRSN graph and the extracted information, three measures are computed (see [LEHP12] for more details).
• Social Position Measure (SPo). The social position of an agent aj is computed based on its centrality degree in order to give an indication about its social power (see formula in table 2). • Social Proximity Measure (SPr). It is a distance metric between a pair of agents, defined by the average cost of their path (see formula in table 2). • Social Similarity Measure (SSi). The social similarity between two agents is computed based on their profiles and the MRSN graph. SSi(ak, aj ) is an aggregation of two measures: – Profile Similarity (PS). In SNs, a profile consists of a set of items structured into a set of fields, each field containing one or several values (e.g. gender=[female], music-likes=[folk, jazz, pop]). In the former, the field is called a single-valued field and in the latter a multi-valued field. The aim of P S is to compare values of fields in requester profile to those in provider profile in order to determine how much requester and provider are similar (see formula in table 2). – Neighborhood Similarity Measure (NS). The neighborhood similarity between two agents is computed based on the comparison of their social acquaintances within the MRSN graph (see formula in table 2). We define the overall measure of social similarity, SSi(ak, aj ) as the product of the two above measures: SSi(ak, aj ) = N S(ak, aj ) × P S(ak, aj ).
After computing these measures, a vector Mj associated with each agent aj is defined as Mj = (SP o(ak), SP r(ak, aj ), SSi(ak, aj )). Considering the vectors of all acquaintances, a matrix M = (Mjt, aj ∈ SAk and 1 ≤ t ≤ 3) is built. ST (ak, aj ), is then computed using a Simple Additive Weighting technique: 3 t=1 where λt ∈ [0, 1] and t3=1 λt = 1. λt represents the weight of the tth social measure; and M = (Mjt, aj ∈ SAk and 1 ≤ t ≤ 3) is the matrix of vectors obtained after the scaling phase which transforms every measure value of Mjt vector into a value Mjt between 0 and 1. 4.2
A good agent should not only be socially trustworthy but also sufficiently expert. Inspired from [LCM12], we define trust in expertise ET of an agent aj based on three attributes: • Usability : is the percentage of successful use of an agent’s service sjl compared to the other services it offers: U s(sjl) = lmN=1bsNubcscuescsc(esssjl()sjl) where N bsuccess(sjl) is the number of successful executions of sjl. This means that the more the service sjl is sought for in the social network the more aj is recognized as an expert in this field.
Trust measure
SP o SP r P S N S
SP r(ak, aj ) = ld=1 U((dal,al+1)) where U ((al, al+1)) is the cost of the edge (al, al+1) ∈ path given by the utility function U regarding the requester agent preferences.
P S(ak, aj ) = |I1| × i∈I βi . Si(ak, aj ) where Si(ak, aj ) is the similarity between the ith items of ak and aj using Burnaby measure [Bur70], I is the set of items in profiles and βi is a weight attributed to the item i reflecting its importance in the profile description.
|iR=|1 wi . δi(ak, aj ) N S(ak, aj ) = with δi(ak, aj ) = 1+j1aci
1 yi+zi where wi = U(Ri) and jaci = xi+yi+zi is the Jaccard distance between ak and aj according to the relationship Ri such as xi = |NRi (ak) ∩ NRi (aj )|, yi = |NRi (ak)| − xi, zi = |NRi (aj )| − xi.
Nbsuccess(sjl) where N binvoc is the number of invocations of sjl.
Nbinvoc(sjl) • Reliability : is the probability that a service sjl is operational at the time of invocation: Re(sjl) = • Quality rating : is the quality of a service sjl. Once a service sjl is successfully used by an agent ak, an evaluation ν ∈ [0, 1] is attributed by the user to this service. We designate by Evalx(ak, sjl) the average of the quality rating of sjl for x uses.
Evalx(ak, sjl) =
1 Evalx−1(ak,sjl)∗(x−1)+ν x if x = 0 otherwise
Trust in expertise ET (ak, aj ) measures, the ability of aj to meet the expectations of ak. It’s an overall score established on the basis of the three aforementioned attributes and over the m services offered by aj .
ET (ak, aj ) = lm=1(U s(sjl) × Re(sjl) × Evalx(ak, sjl)) m 4.3
The global trust T rust(ak, aj ) that an agent ak has for an agent aj is a weighted sum that depends on the expertise as well as on the sociability of aj .
T rust(ak, aj ) = w × ST (ak, aj ) + (1 − w) × ET (ak, aj ) 5
In this paper, our goal is to search user’s required services through a distributed trust-based service discovery. In the following, we present our original search mechanism based on a distributed referral approach. 5.1
In [YS03] and [YVS99], a referral approach is used with a centralized decision-making : when an agent receives a request for expertise either it tries to match it against its own functionalities, or generates a list of possible referrals using its user contact file, i.e., social acquaintances. The query originator’s agent collects all possible referrals, and decides to continue or not the search by contacting some of the suggested referrals. In this work, we propose a distributed version of the referring process where, each agent acts autonomously and decides locally to continue or not the search by propagating the query in its social acquaintance without coming back to the requester agent. Some agents may be good providers and some others may be bad providers but may be well connected and thus, may recommend good referrals. In our approach, we consider three different roles that an agent may take: requester, provider/referral or, recommender. 5.2
Before describing the algorithm, let us give some hypotheses. Recall that each agent ak offers a set of services Sk = {sk1, . . . , skm} and has a set of social acquaintances SAk. Additionally, each agent ak encompasses the following variables: • A status variable, denoted statusk, that represents the role taken by an agent during the search process.
It takes its value in the set {⊥, Req, P rov, Rec, Stop} with Req for requester, P rov for provider, Rec for recommender, and Stop for stopper. Initially, the status of all agents equals ⊥ except for the requester agent ar whose status is equal to Req. • A distance variable, denoted distk, that represents the distance of an agent to the requester agent ar.
Initially, this variable equals 0 for the requester agent ar and +∞ for all other agents. • A counter variable, denoted countk, that serves to count the number of messages received from its acquaintances. Initially, this variable equals 0 for all agents. • A set of trustworthy agents, denoted LT Ak, representing the set of potential providers belonging to the social acquaintances SAk of ak. Initially, LT Ak is an empty set for all agents. • A set of trustworthy agents, denoted LRAk, representing the set of potential referrals belonging to the social acquaintances SAk of ak. Initially LRAk is an empty set for all agents.
The message structure is adapted form ACL syntax: <perf ormative, receiver, content>. 5.3
The distributed search is presented in Algorithm 1. It ensures the propagation of search via navigation in the SN. The inputs are G a MRSN graph and Q = (F, C, U, α) (see Def 4) a query transmitted by a requester to its agent. As the output of the algorithm, each agent knows its status regarding the query (provider, recommender or stopper) and its distance to the requester agent in the provider-recommender chain. A provider-recommender chain is a sequence of agents in G starting from the requester agent ar and leading to a provider in which all agents are either providers or recommenders.
The algorithm is composed of four procedures and begins with an initiator, the requester agent ar, acquiring the requester role (statusr = Req), setting its distance to itself to 0, and starting the discovery process by sending an Request message to all its acquaintances (see lines 2 to 5). After that, ar waits 3 for an Inform message from each of its acquaintances (see line 6). Once ar received all Request messages (one message per acquaintance), it determines using its T C, a subset of trustworthy agents LT Ak from the set of its SAk (see line 8) and sends them a Propagate message (see lines 10 to 13).
The behavior of an agent ak is event-driven: the reception of a message triggers the execution of a procedure depending on the received message. An agent ak that receives an Request message, sends an Inform message containing information about its profile P rk, offered services Sk with their advertised QoS values and its social acquaintance SAk (see line 21 to 23). An agent ak that receives an Inform message from an acquaintance aj , increments its message counter and upgrades aj ’s record in P ITk as means to upkeep its beliefs regarding aj ’s current offered services with their QoS values, profile and, its social acquaintance SAj (see lines 24 to 27).
An agent ak that receives a Propagate message, compares the received distance value with its current distance value. If the received value is less than its current distance value, then ak sets distk to the new value which represents its distance in the provider-recommender chain to the requester agent ar (see lines 29 to 30). After that, ak sends an Request message to all its acquaintances and waits for an Inform message from each of its acquaintances (see lines 31 to 34).
3As agents have the good will to help, we suppose that all acquaintances answer. If not, we consider that there is a failure in the system which is out of scope of this paper. 1: procedure Propagation(F , C, U , α) 2: if (statusk == Req) then 3: for all aj ∈ SAk do 4: send(Request, aj ); 5: end for 6: wait (countk == |SAk|); 7: countk ← 0; 8: LT Ak ← {aj ∈ SAk / T rust(ak, aj ) > fα(distk)}; 9: end if 10: if (statusk == Req) or (statusk == P rov) then 11: for all aj ∈ LT Ak do 12: send(P ropagate, aj , F , U , α, distk); 13: end for 14: end if 15: if (statusk == Rec) then 16: for all aj ∈ LRAk do 17: send(P ropagate, aj , F , U , α, distk); 18: end for 19: end if 20: end procedure 21: procedure Receive(Request, aj ) 22: send(Inf orm, aj , P rk, Sk, SAk); 23: end procedure 24: procedure Receive(Inf orm, aj , P r, S, SA) 25: countk ← countk + 1; 26: P ITk.put(aj , P r, SA, S); 27: end procedure
The Inform message
The Propagate message The Propagate message Algorithm 1 Distributed Trust-based Search Algorithm variables: statusk ∈ {⊥, Req, P ro, Rec, Stop}, distk ∈ {0, . . . , n}, countk ∈ {0, . . . , |SAk|}, LT Ak a set of trustworthy potential providers, LRAk a set of trustworthy potential referrals .
SAk set of social acquaintance agents
The Request message
In order to find other potential providers in G LRAk ← {aj ∈ SAk / T rust(ak, aj ) > fα(distk) and ∃ s ∈ P ITk.get(aj ), / s ≡ s ⊂ F ∧(skl |= C}; if (LRAk = ∅) then statusk ← Rec;
Propagation(F , C, U , α); In order to find other potential providers in G
Once an agent ak received all Inform messages (one message per acquaintance), it checks its set of services Sk and based on its M C, it verifies if one of its services fits user’s needs F given its constraints C (see line 36). In both cases, ak computes its trust threshold and trust value towards all its acquaintances using its T C. The computation of ak trustworthiness towards an acquaintance aj , T rust(ak, aj ) is an aggregated value over aj ’s expertise and sociability (see Section 4). The computation of ak’s trust threshold is done based on the following observation: if we consider that the agent requester ar is a point of reference in the graph, the longer the providerrecommender chain is, the less trustworthy the contacted agents are. Therefore, we have to adapt the value of trust threshold (α) initially fixed by ar to the current search depth (current length of the provider-recommender chain). For this, we define a function denoted fα(distk) which adjusts the threshold value of ak depending on −distk its distance distk to ar in the provider-recommender chain as follows: fα(distk) = (1 − α) × (1 − e D ) + α, where D is the graph diameter.
Once ak has computed its trustworthiness towards all its acquaintances and its trust threshold, it determines a subset of trustworthy agents. There are two possible cases, the first is that ak has a service skl ∈ Sk that offers the same capacity as a requested service s ∈ F , then ak determines the LT Ak subset. To be in this subset, an acquaintance aj has to have a trust value T rust(ak, aj ) greater than fα(distk) (see line 37). Thereafter, ak gets the provider role (statusk = P ro) and executes the Propagation procedure (see lines 38 to 39) that sends a Propagate message to all acquaintances in LT Ak (see lines 10 to 12). In a second case, ak does not provide the desired service, it determines the subset of agents LRAk which are not only trustworthy (T rust(ak, aj ) > fα(distk)) but also that offers a desired service (∃ s ∈ P ITk.get(aj ), / s ≡ s ∈ F ) (see line 41). If ak has no potential referrals (i.e. either they are not enough trusty to be recommended or they do not offer at least one requested service), then ak stops the query propagation and takes the stopper role (statusk = Stop) (see line 45 to 46). Otherwise, ak gets the recommender role (statusk = Rec) and executes the Propagation procedure (see lines 42 to 44) that sends a Propagate message to all acquaintances in LRAk (see lines 15 to 18). This way of progressive spreading is the original mechanism of referral systems in which the propagation of the search is ensured via navigation in the graph. In this case, although ak does not provide any desired service, it can participate in the discovery process while leading to relevant agents.
Let us consider our travel scenario in which we apply the algorithm. Recall that required services are F= { Transportation service, Hotel service}, a0 who is the requester agent, launches the discovery process in the SN graph by contacting trustworthy agents of its SA0 (a2 and a7 are not trustworthy). An agent who is able to participate to the query achievement is considered as a provider (a4 and a5) whereas, all intermediate agents leading to providers are called recommenders. In this example, a3 and a6 are recommenders since they do not have useful services but they are well connected and lead to relevant providers (for example, a3 recommends a1). As described above, each contacted agent propagates the query within its social acquaintance using the same mechanism and only agents which are sufficiently trustworthy and with useful service(s) are detected.
At the end of this search process we obtain an annotated graph as shown in figure 2 wherein providers are recognized (checked nodes). Note that some agents which have services to respond to the user query, a10 and a12, are not discovered since they are not enough trusty to be recommended. We have developed a prototype using Java 1.7 and the Jade4 multi-agent platform. The MRSN graph data was stored in a GML format5. All experiments were run on a 3.1GHz Core(TM) i5-2400 running windows 7, with a 8Go of RAM. Simulations were done over 11 MRSN graph randomly generated. The number of agents varies from 500 to 10000. Each graph contains 3 types of relationship and the requester preferences over relationships types are equal to U (R1) = 1, U (R2) = 2, U (R3) = 4. We run each simulation with four initial values of α, i.e., α = 0, 0.2, 0.4, 0.6. We average the obtained results over 5 instances of each graph. Services were also randomly distributed among agents thus, each agent in the graph may be a potential provider depending on the requested service. For sake of simplicity, we suppose for all experiments that the requester agent needs only one service s at a time. We evaluate our algorithm by computing the percentage of discovered providers (see Fig 3 a and b).
We investigate the impact of trust threshold on the discovery process (Fig 3.a). We compute the percentage of discovered providers while varying trust threshold as depicted in figure 3.a. For α = 0, almost all providers are discovered. This is equivalent to an exhaustive search that takes into account only the functional aspect of the provider and ignores its social aspect. As expected, the number of discovered providers decreases while the threshold increases. For high values of α, agents explore less search space in the MRSN which reduces the number of discovered providers. 6.2
We study how the number of discovered providers is scattered in the MRSN in terms of provider-recommender chain length for a given requester agent query (Fig 3.b). Using the trust measure, we compute the percentage of discovered providers (averaged over all graph instances) for different ranges of length. Now, let us look at figure 3.b; this figure displays the providers’ dispersion for different trust threshold. For each threshold value, the average number of discovered providers tends to level off once the length reach a certain point. There is a trade-off between the chain length and the number of discovered providers: there is seven times more chances to find a trustworthy provider in a chain length equal to 7 than in chain length equal to 3 (from 14% to 80%). We noticed also that for values of α greater than 0.4, trustworthy providers are discovered relatively far away from the requester. This indicates that many of discovered providers are weakly connected to the service requester and require a long chain of recommenders to be reached. These results help us to fix the length of the providerrecommender chain as a parameter. Setting a maximum length to 6 gives us the possibility to control the scope of search which would substantially limit the computation costs. 7
In this work, we have presented a distributed approach for trust-based service discovery to satisfy user’s needs in social networks. We propose to evaluate trustworthiness towards service providers and their services over two dimensions namely sociability and expertise. The discovery process is done by a distributed referral system that spreads out the query among agents with respect to the SN topology. As future work, we plan to compare our service discovery approach with a non trust-based one. By means of simulation, we plan to evaluate the impact
of our social trust at agent-decision making during interaction and thereafter the quality of the underlying service discovery. We also would like to investigate the composition of provider-recommender chain by keeping within each service provider the identity of its acquaintances that recommend them. Finally, we intend to explore the extension of our model to perform a service composition built upon a coalition formation of trust-based discovered services. The idea is to achieve complex user’s needs through a service composition where discovered agents communicate and coordinate within an organizational structure. [PKPS02] [RKM04]
F. Lalanne, A. Cavalli, and S. Maag. Quality of experience as a selection criterion for web services. In Signal Image Technology and Internet Based Systems, Eighth International Conference on, pages 519–526, 2012.