# Time-Aware IoE Service Recommendation on Sparse Data

Authors: Lianyong Qi; Xiaolong Xu; Wanchun Dou; Jiguo Yu; Zhili Zhou; Xuyun Zhang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

With the advent of “Internet of Everything” (IoE) age, an excessive number of IoE services are emerging on the web, which places a heavy burden on the service selection decision of target users. In this situation, various recommendation techniques are introduced to alleviate the burden, for example, Collaborative Filtering- (CF-) based recommendation. Generally, CF-based recommendation approaches utilize similar friends or similar services to achieve the recommendation goal. However, due to the sparsity of user feedback, it is possible that a target user has no similar friends and similar services; in this situation, traditional CF-based approaches fail to produce a satisfying recommendation result. Besides, recommendation accuracy would be decreased if time factor is overlooked, as IoE service quality often varies with time. In view of these challenges, a time-aware service recommendation approach namedSer_Rectime is proposed in this paper. Concretely, we first calculate the time-aware user similarity; afterwards, indirect friends of the target user are inferred by Social Balance Theory (e.g., “enemy’s enemy is a friend” rule); finally, the services preferred by indirect friends of the target user are recommended to the target user. At last, through a set of experiments deployed on dataset WS-DREAM, we validate the feasibility of our proposal.


---

## Body

## 1. Introduction

With the wide adoption of various smart devices and connection technologies, human society is gradually transforming into an “Internet of Everything” (IoE) one [1–5]. In the age of IoE, the links among users, devices, or other things could be built easily, which significantly improves people’s quality of life and also brings many challenging open problems that need to be addressed [6–11].With the advent of IoE age, an excessive number of IoE services with different functionalities or qualities are emerging on the web, which places a heavy burden on the service selection decision of target users [12–14]. In this situation, various recommendation techniques are put forward to help alleviate the service selection burden, for example, Collaborative Filtering- (CF-) based recommendation [15–19]. Generally, CF-based recommendation approaches (including user-based CF, item-based CF, and hybrid CF) utilize the similar friends or similar services of target users to achieve the recommendation goal. However, in certain situations, the available user-service rating data generated from historical service invocations is really sparse [20]. Therefore, it is probable that a target user cannot find his/her similar friends and similar services of target services (here, target services mean the services preferred by target users). In this situation, traditional CF-based recommendation approaches cannot return a satisfying recommendation result, which brings a great challenge for the robustness of service recommendation approaches. Besides, the quality of an IoE service often varies with time, due to the unstable network environment [21]. For example, the response time of a ticket-order service often becomes larger when Christmas day is approaching. Therefore, recommendation accuracy would be decreased if the time factor is not taken into consideration.In view of the above two challenges, a novel time-aware service recommendation approach, that is,Ser_Rectime, is put forward in this paper, to make robust and accurate service recommendation for target users when the historical user-service rating data is sparse. Concretely, in Ser_Rectime, we first calculate the time-aware user similarity; afterwards, we look for the enemies (antonym of “friend”) of the target user and further determine the “indirect friends” of target user by Social Balance Theory [22] (e.g., “enemy’s enemy is a friend” rule); finally, the services preferred by indirect friends of target user are recommended to the target user.The contributions of our paper are threefold.(1)
Time factor is considered in user similarity calculation to adapt to the dynamic quality variation of IoE services, which makes the subsequent recommendation result more objective and accurate.(2)
Social Balance Theory is introduced for service recommendation on sparse data so that the recommendation robustness is improved.(3)
A wide range of experiments are designed and deployed on a real web service quality set WS-DREAM [23], so as to further validate the feasibility of our proposal.The remainder of our paper is organized as follows. In Section2, we first formalize the CF-based service recommendation problem and afterwards demonstrate the motivation of our paper. In Section 3, a novel time-aware service recommendation approach named Ser_Rectime is brought forth. A set of experiments are deployed in Section 4 and evaluations are presented in Section 5. Finally, in Section 6, we summarize the paper and point out our future research directions.


## 2. Formalization and Motivation

In this section, we first formalize the CF-based service recommendation problem. And afterwards, an example is presented to demonstrate the motivation of our paper intuitively.


### 2.1. Formal Specification

Generally, the CF-based service recommendation problem could be specified with a four-tupleCF-Ser-Rec(U,WS,→,usertarget), where(1)
U={user1,…,userm} denotes the user set in user-service invocation network and m is the number of users;(2)
WS={ws1,…,wsn} denotes the web service set in user-service invocation network and n is the number of web services;(3)
→={(useri→Ti-jRi-jwsj)∣1≤i≤m,1≤j≤n} denotes the historical invocation record set, that is, useri→Ti-jRi-jwsj, which means that useri invoked wsj in the past and the rating of wsj by useri is Ri-j. Here, for simplicity, the well-known {1∗,2∗,3∗,4∗,5∗} rating system is adopted to depict Ri-j. Also, each invocation record owns a timestamp Ti-j that indicates the service invocation time (here, we assume the timestamp format is “yyyy.mm.dd”);(4)
usertarget denotes the target user that requires service recommendation and usertarget∈U holds.With the above formalization, CF-based service recommendation problem could be specified as follows: according to the historical invocation record set “→” between users (in U) and web services (in WS), find out the services that were never invoked but may be preferred by target user usertarget and recommend them to usertarget.


### 2.2. Motivation

In this subsection, the paper motivation is clarified more intuitively with the example shown in Figure1. In Figure 1, there are three users {Tom,Alice,Bob} (Tom is the target user) in set U and six web services {ws1,ws2,ws3,ws4,ws5,ws6} in set WS; historical user-service invocation record set → (including rating data and timestamp) is also presented in Figure 1.Figure 1
Time-aware service recommendation when target user has no similar friends and similar services.Then according to the Adjusted Cosine Similarity [24] (i.e., ACS∈[-1,1]; here, the reason that we utilize ACS for similarity calculation is that user-service rating data is often discrete and the rating scales of different users often vary), we can calculate the similarity between target user Tom and other two users (i.e., Alice and Bob). Concretely, Sim(Tom,Alice)=-0.2747 and Sim(Tom,Bob)=Null (as no services were rated by both Tom and Bob). Therefore, we can conclude that target user Tom has no similar friends, so according to the traditional user-based CF recommendation approaches, no qualified services are recommended to Tom.Likewise, the similarities between target services (i.e.,ws1 and ws2) and other services (i.e., ws3, ws4, ws5, and ws6) could also be obtained. Concretely, Sim(ws1,ws3) = Sim(ws1,ws4) = Sim(ws2,ws3) = Sim(ws2,ws4)=-1 and Sim(ws1,ws5) = Sim(ws1,ws6) = Sim(ws2,ws5) = Sim(ws2,ws6)=Null (as no users invoked any pair of services above simultaneously). Therefore, a conclusion could be drawn that target user Tom’s preferred services (i.e., ws1 and ws2) have no similar services, so according to the traditional item-based CF recommendation approaches, no qualified services are recommended to Tom.Therefore, in this situation, traditional CF-based service recommendation approaches (e.g., user-based CF, item-based CF, or hybrid CF) cannot make accurate service recommendation for target user. Besides, as Figure1 shows, the timestamps of various invocation records are often different, so the service recommendation accuracy and fairness would be decreased if we overlook the time factor in recommendation process. In view of the above two challenges, a novel service recommendation approach named Ser_Rectime is put forward in Section 3.  Ser_Rectime cannot only find out the indirect friends of a target user so as to improve the recommendation robustness in sparse-data environment, but also consider time factor in recommendation so as to ensure the fairness and accuracy of recommendation results.


## 2.1. Formal Specification

Generally, the CF-based service recommendation problem could be specified with a four-tupleCF-Ser-Rec(U,WS,→,usertarget), where(1)
U={user1,…,userm} denotes the user set in user-service invocation network and m is the number of users;(2)
WS={ws1,…,wsn} denotes the web service set in user-service invocation network and n is the number of web services;(3)
→={(useri→Ti-jRi-jwsj)∣1≤i≤m,1≤j≤n} denotes the historical invocation record set, that is, useri→Ti-jRi-jwsj, which means that useri invoked wsj in the past and the rating of wsj by useri is Ri-j. Here, for simplicity, the well-known {1∗,2∗,3∗,4∗,5∗} rating system is adopted to depict Ri-j. Also, each invocation record owns a timestamp Ti-j that indicates the service invocation time (here, we assume the timestamp format is “yyyy.mm.dd”);(4)
usertarget denotes the target user that requires service recommendation and usertarget∈U holds.With the above formalization, CF-based service recommendation problem could be specified as follows: according to the historical invocation record set “→” between users (in U) and web services (in WS), find out the services that were never invoked but may be preferred by target user usertarget and recommend them to usertarget.


## 2.2. Motivation

In this subsection, the paper motivation is clarified more intuitively with the example shown in Figure1. In Figure 1, there are three users {Tom,Alice,Bob} (Tom is the target user) in set U and six web services {ws1,ws2,ws3,ws4,ws5,ws6} in set WS; historical user-service invocation record set → (including rating data and timestamp) is also presented in Figure 1.Figure 1
Time-aware service recommendation when target user has no similar friends and similar services.Then according to the Adjusted Cosine Similarity [24] (i.e., ACS∈[-1,1]; here, the reason that we utilize ACS for similarity calculation is that user-service rating data is often discrete and the rating scales of different users often vary), we can calculate the similarity between target user Tom and other two users (i.e., Alice and Bob). Concretely, Sim(Tom,Alice)=-0.2747 and Sim(Tom,Bob)=Null (as no services were rated by both Tom and Bob). Therefore, we can conclude that target user Tom has no similar friends, so according to the traditional user-based CF recommendation approaches, no qualified services are recommended to Tom.Likewise, the similarities between target services (i.e.,ws1 and ws2) and other services (i.e., ws3, ws4, ws5, and ws6) could also be obtained. Concretely, Sim(ws1,ws3) = Sim(ws1,ws4) = Sim(ws2,ws3) = Sim(ws2,ws4)=-1 and Sim(ws1,ws5) = Sim(ws1,ws6) = Sim(ws2,ws5) = Sim(ws2,ws6)=Null (as no users invoked any pair of services above simultaneously). Therefore, a conclusion could be drawn that target user Tom’s preferred services (i.e., ws1 and ws2) have no similar services, so according to the traditional item-based CF recommendation approaches, no qualified services are recommended to Tom.Therefore, in this situation, traditional CF-based service recommendation approaches (e.g., user-based CF, item-based CF, or hybrid CF) cannot make accurate service recommendation for target user. Besides, as Figure1 shows, the timestamps of various invocation records are often different, so the service recommendation accuracy and fairness would be decreased if we overlook the time factor in recommendation process. In view of the above two challenges, a novel service recommendation approach named Ser_Rectime is put forward in Section 3.  Ser_Rectime cannot only find out the indirect friends of a target user so as to improve the recommendation robustness in sparse-data environment, but also consider time factor in recommendation so as to ensure the fairness and accuracy of recommendation results.


## 3. Time-Aware Service Recommendation Approach:Ser_Rectime

In this section, a novel time-aware recommendation approach, that is,Ser_Rectime, is introduced to deal with the service recommendation problem on sparse data. The main idea of our proposal is as follows: first, we calculate the time-aware similarity between target user and other users based on the historical user-service rating records; second, according to the derived user similarity and Social Balance Theory, we infer the indirect friends of target user; third, the services preferred by indirect friends of target user are recommended to the target user. Concretely, the three steps of time-aware service recommendation approach (Ser_Rectime) are as follows.Step 1 (time-aware user similarity calculation).
Calculate the similaritySim(usertarget,useri) between usertarget and other users useri∈U. If Sim(usertarget,useri)≤P (P is similarity threshold), then useri is considered as an enemy of usertarget.Step 2 (determining indirect friends of target user).
According to the enemies (derived in Step  1) of target user and Social Balance Theory, determine target user’s indirect friends.Step 3 (service recommendation).
Select the services preferred by the indirect friends (derived in Step  2) of target user and recommend them to the target user.The three steps are explained as follows:Step 1 (time-aware user similarity calculation).
In this step, we calculate the similarity between target userusertarget and other users useri(useri∈U), that is, Sim(usertarget,useri). As user-service rating data is often discrete and rating scores of a service by different users are often varied, Adjusted Cosine Similarity is recruited here for user similarity calculation. Concretely, Sim(usertarget,useri) could be obtained based on (1)Simusertarget,useri=∑wsj∈IRtarget-j-Rtarget¯∗Ri-j-Ri¯∑wsj∈ItargetRtarget-j-Rtarget¯2∗∑wsj∈IiRi-j-Ri¯2.
Here, setI denotes the common services that were rated by both usertarget and useri; sets Itarget and Ii denote the service set rated by usertarget and useri, respectively; Rtarget-j and Ri-j denote ratings of service wsj by usertarget and useri, respectively; while Rtarget¯ and Ri¯ represent usertarget’s and useri’s average rating values. Then according to (1), we can calculate the similarity between target user and any other user.
Next, we improve the user similarity formula in (1) by introducing four kinds of weight coefficients.(i)
Weight for Service Intersection Size. As formula (1) indicates, Itarget and Ii denote the service set rated by usertarget and useri, respectively. Generally, for usertarget and useri, the larger their service intersection (i.e., set I in formula (1)) is, the more convincing their similarity is. So in order to depict this correlation, weight Wser-intersection (in formula (2)) is assigned to user similarity Simusertarget,useri:(2)Wser-intersection=12∗Itarget∩IiItarget+Itarget∩IiIi.(ii)
Weight for Invocation Time. Due to the dynamic and unstable network environment, the IoE service quality is often varied with time; therefore, two neighboring service invocations with close invocation time often contribute more to the user similarity. In view of this observation, similar to work [4], weight Wtime in formula (3) is assigned to user similarity Simusertarget,useri. In (3), α(α≥0) is a parameter, while Ttarget-j and Ti-j represent the invocation time of service wsj by usertarget and useri, respectively(3)Wtime=e-αTtarget-j-Ti-j.(iii)
Weight for Invocation Load. Service invocation time cannot reflect all the time-related information in similarity calculation. For example, user1 and user2 invoked the same ticket-booking service on 22-12-2015 and 24-12-2015, respectively. Although their service invocation time is close, the user experienced service quality may vary significantly as heavy service load is inevitable when Christmas day is approaching. So in order to depict the effect of service load on user similarity, weight Wload in formula (4) is assigned to user similarity Simusertarget,useri. In (4), Loadtarget-j and Loadi-j denote the service loads when usertarget and useri invoked service wsj, respectively.(4)Wload=1-Loadtarget-j-Loadi-jmax⁡Loadtarget-j,Loadi-j.(iv)
Weight for Service Version. In the life cycle of a web service, service provider may publish a series of service versions with updated service qualities. Therefore, if two users invoked an identical web service that belongs to different versions, it would not make much sense to compare their experienced service qualities. In view of this observation, weight Wversion is suggested as follows:(5)Wversion=1usertarget,useriinvoked same service of same version0else.
With the above analyses, we can update the user similaritySimusertarget,useri in (1) to be time-aware user similarity Simtimeusertarget,useri in (6). Then based on (6), we can calculate the time-aware similarity between target user and any other user:(6)Simtimeusertarget,useri=Wser-intersection∗∑wsj∈IWtime∗Wload∗Wversion∗Rtarget-j-Rtarget¯∗Ri-j-Ri¯∑wsj∈ItargetRtarget-j-Rtarget¯2∗∑wsj∈IiRi-j-Ri¯2.
Furthermore, according to the derived user similarity, the enemy set of target user, that is,Enemy_set (usertarget), could be obtained based on (7). Here, parameter P(-1≤P≤-0.5) is a predefined user similarity threshold for enemy relationship:(7)useri∈Enemy_setusertargetifSimtimeusertarget,useri≤P∉Enemy_setusertargetelse.Step 2 (determining indirect friends of target user).
In Step  1, we have obtained the enemy set of target user, that is,Enemy_set(usertarget). Next, in this step, we will introduce how to get the indirect friends of target user, that is, Indirect_friend_set(usertarget), based on the obtained Enemy_set(usertarget) and Social Balance Theory. First of all, we introduce Social Balance Theory briefly.
Social Balance Theory [22] was first put forward by psychologist F. Heider in 1958. The theory investigates the stable social relationships among involved three parties (i.e., P, O, and X in Figure 2). Concretely, according to Figure 2, we introduce the four stable social relationships, respectively, in a more intuitive manner.(a)
Friend’s Friend Is a Friend. If X is a friend of O and O is a friend of P, then we can infer that X is probably an indirect friend of P (see Figure 2(a)).(b)
Enemy’s Enemy Is a Friend. If X is an enemy of O and O is an enemy of P, then we can infer that X is probably an indirect friend of P (see Figure 2(b)).(c)
Friend’s Enemy Is an Enemy. If X is an enemy of O while O is a friend of P, then we can infer that X is probably an indirect enemy of P (see Figure 2(c)).(d)
Enemy’s Friend Is an Enemy. If X is a friend of O while O is an enemy of P, then we can infer that X is probably an indirect enemy of P (see Figure 2(d)).
Next, with the above four rules in Social Balance Theory, we introduce how to obtain the indirect friend set of target user, that is,Indirect_friend_set(usertarget), based on the derived Enemy_set(usertarget) in Step  1.
Concretely, for eachuseri∈Enemy_set(usertarget), we first calculate his/her similarities with other users based on (6); afterwards, we determine useri’s enemies userk (i.e., userk∈Enemy_set(useri)) based on (7) and useri’s friends userg (i.e., userg∈Friend_set(useri)) based on (8). In (8), parameter -P denotes the user similarity threshold for friend relationship. To ease the understanding of readers, the relationships among usertarget, useri, userk, and userg are presented in Figure 3.(8)userg∈Friend_setuseriifSimtimeuseri,userg≥-P∉Friend_setuserielse.
Then according to “enemy’s enemy is a friend” rule in Figure2(b), we can infer that userk is probably an indirect friend of usertarget, and the probability could be calculated based on (9). If Probabilityfriend(usertarget,userk)≥-P, then userk is regarded as a qualified indirect friend of target user and put into set Indirect_friend_set(usertarget) (see Figure 3(b)). Likewise, according to “enemy’s friend is an enemy” rule in Figure 2(d), it can be inferred that userg is probably an indirect enemy of usertarget, and the probability can be obtained based on (10). If Probabilityenemy(usertarget,userg)≥-P, then userg is regarded as a qualified indirect enemy of target user and put into set Enemy_set(usertarget) (see Figure 3(d))(9)Probabilityfriendusertarget,userk=Simtimeusertarget,useri∗Simtimeuseri,userk,(10)Probabilityenemyusertarget,userg=Simtimeusertarget,useri∗Simtimeuseri,userg.
Next, for eachuserx∈Indirect_friend_set(usertarget), we calculate his/her similarity with other users (∈(U-usertarget-Indirect_friend_set(usertarget)-Enemy_set(usertarget))) based on (6) and further determine userx’s enemies usery based on (7) and userx’s friends userz based on (8). Then according to “friend’s enemy is an enemy” rule in Figure 2(c), usery is regarded as an indirect enemy of target user and put into Enemy_set(usertarget) (see Figure 3(c)) if the probability in (11) is larger than −P. Likewise, according to “friend’s friend is a friend” rule in Figure 2(a), userz is considered as an indirect friend of target user and put into Indirect_friend_set(usertarget) (see Figure 3(a)) if the probability in (12) is larger than -P.(11)Probabilityenemyusertarget,usery=Probabilityfriendusertarget,userx∗Simtimeuserx,usery,(12)Probabilityfriendusertarget,userz=Probabilityfriendusertarget,userx∗Simtimeuserx,userz.
Repeat (a)–(d) process in Figure3 until set Indirect_friend_set(usertarget) stays stable. Then we obtain the indirect friends of target user, that is, Indirect_friend_set(usertarget).Figure 2
Four stable relationships amongP, X, and O according to Social Balance Theory (the blue arrows between P and X denote the inferred relationships).
(a) (b) (c) (d)Figure 3
Relationships amongusertarget, useri, userk, userg, userx, usery, and userz.Step 3 (service recommendation).
In Step  2, we have obtained target user’s indirect friend setIndirect_friend_set(usertarget). Next, in this step, we select the services preferred (i.e., with 4∗ or 5∗ rating) by indirect friends of target user and recommend them to the target user. More formally, for each element userx∈Indirect_friend_set(usertarget), if his/her rating over web service wsj (1≤j≤n), that is, Rx-j∈{4∗,5∗}, holds, then wsj is put into the recommended service set, that is, Rec_Ser_Set. Finally, all the web services in set Rec_Ser_Set are recommended to usertarget.With above Step  1–Step  3 of our proposedSer_Rectime approach, a set of IoE services (in set Rec_Ser_Set) are recommended to the target user. More formally, the pseudocode of Ser_Rectime(U,WS,→,usertarget) is presented in Algorithm 1 (please note that algorithm Ser_Rectime(U,WS,→,usertarget) is abbreviated as Ser_Rectime in the whole paper).Algorithm 1: S e r _ R e c t i m e   ( U , W S , → , u s e r t a r g e t ).
Inputs: ( 1 )   U={user1,…,userm}: a set of users in user-service invocation & rating network; ( 2 )  WS={ws1,…,wsn}: a set of web services in user-service invocation & rating network; ( 3 )  →={(useri→Ti-jRi-jwsj)∣1≤i≤m,1≤j≤n}: a set of historical user-service rating records; ( 4 )  usertarget: target user who requires service recommendation. Output: Rec_Ser_Set: service set recommended to usertarget ( 1 )  Set user similarity threshold P  (-1≤P≤-0.5) ( 2 )  for  each useri∈U  do // Step  1 ( 3 ) calculate Simtime(usertarget,useri) based on (1)–(6) ( 4 ) if  Simtime(usertarget,useri)≤P ( 5 )  then  put useri into set Enemy_set(usertarget) ( 6 ) end  if ( 7 )  end  for ( 8 )  for  each useri∈Enemy_set(usertarget)  do // Step  2 ( 9 ) determine useri’s friend userg based on (6) and (8) ( 10 ) if  probability in (10) is larger than -P ( 11 ) then  put userg into Enemy_set(usertarget) ( 12 ) end  if ( 13 ) determine useri’s enemy userk based on (6) and (7) ( 14 ) if  probability in (9) is larger than -P ( 15 ) then  put userk into Indirect_friend_set(usertarget) ( 16 ) end  if ( 17 )  end  for ( 18 )  for  each userx∈Indirect_friend_set(usertarget)  do ( 19 ) determine userx’s enemy usery based on (6) and (7) ( 20 ) if  probability in (11) is larger than -P ( 21 ) then  put usery into Enemy_set(usertarget) ( 22 ) end  if ( 23 ) determine userx’s friend userz based on (6) and (8) ( 24 ) if  probability in (12) is larger than -P ( 25 ) then  put userz into Indirect_friend_set(usertarget) ( 26 ) end  if ( 27 )  end  for ( 28 )  repeat Line (8)–Line (27) until Indirect_friend_set(usertarget) stays stable ( 29 )  Rec_Ser_Set=∅ // Step  3 ( 30 )  for  each userx∈Indirect_friend_set(usertarget)  do ( 31 ) for  each wsj∈WS  do ( 32 )  if  Rx-j∈{4∗,5∗} ( 33 )  then  put wsj into set Rec_Ser_Set ( 34 )  end  if ( 35 ) end  for ( 36 )  end  for ( 37 )  return  Rec_Ser_Set


## 4. Experiment

In this section, a set of experiments are designed and tested to validate the feasibility of our proposedSer_Rectime approach, in terms of recommendation accuracy, recall, and efficiency.


### 4.1. Experiment Dataset and Deployment

The experiment is based on a real service quality dataset WS-DREAM [23]. WS-DREAM consists of 4532 IoE services on the web, and 142 distributed users from Planet-Lab are employed for evaluating the real quality (e.g.,response time andthroughput) of services in 64 time intervals (time interval = 15 minutes).Our paper focuses on the user-service rating-based recommendation, while available user-service rating data is really rare on the web; therefore, in the experiment, we need to transform the service quality data in WS-DREAM into corresponding user-service rating data (essentially, objective service quality data and subjective user-service rating data both reflect the service running quality; therefore, we argue that the transformation from former data to latter data makes sense for the service recommendation simulation here). Concretely, the transformation process is as follows: we determine the minimal and maximal quality values (denoted bymin and max, resp.) of a service observed by an identical user, and afterwards we divide the range [min,max] into five subranges in an arithmetic progression manner, each corresponding to a rating value. For example, if the minimal and maximal throughput values of a service wsj observed by useri are 10 kbps and 60 kbps, respectively, then we can get five subranges after division, that is, [10, 20) kbps, [20, 30) kbps, [30, 40) kbps, [40, 50) kbps, and [50, 60] kbps. Furthermore, if the throughput value of wsj observed by useri is 44 kbps in WS-DREAM, then the transformed user-service rating, that is, Ri-j=4∗, holds. For each service invoked by a user, we randomly select a time interval from all the 64 intervals and transform the service quality corresponding to the selected time interval into a user-service rating with a timestamp (i.e., the selected time interval). In the experiment, only a quality dimension, that is,throughput, is considered.Besides, our paper only discusses the time-aware service recommendation in sparse-data environment where target user has no similar friends and similar services. Therefore, we select appropriate data from WS-DREAM to simulate the above sparse recommendation situations. Furthermore, for each recruited target user, his/her 80% ratings are randomly selected for training while the remaining 20% ratings for testing.Also, we compare our proposal with related works, for example, WSRec [25], MCCP [26], and SBT-SR [27], in terms of recommendation accuracy and recall. Concretely, accuracy and recall are measured by Mean Absolute Error (i.e., MAE; the smaller the better) in (13) and Recall (the larger the better) in (14). In (13), Rec_Ser_Set denotes the recommended service set for target user; |X| denotes the size of set X; Rtarget-x and Rtarget-x# represent target user’s real and predicted ratings over service wsx, respectively. While in (14), symbols Preferred_Ser_Set and Rec_Ser_Set denote the service set really preferred (with 4∗ or 5∗ rating) by target user and the service set recommended to target user, respectively.(13)MAE=∑wsx∈Rec_Ser_SetRtarget-x-Rtarget-x#Rec_Ser_Set,(14)Recall=Preferred_Ser_Set∩Rec_Ser_SetPreferred_Ser_Set.The experiments were conducted on a Dell laptop with 2.80 GHz processors and 2.0 GB RAM. The software configuration is Windows XP + JAVA 1.5. Each experiment was carried out 10 times and the average results were adopted finally.


### 4.2. Experiment Results and Analyses

Concretely, four profiles are designed, tested, and compared. Here,m and n denote the number of users and number of services in the historical user-service invocation network.(Profile 1) Recommendation Accuracy Comparison. In this profile, we compare the recommendation accuracy of Ser_Rectime with the other three approaches, that is, WSRec, MCCP, and SBT-SR. Concretely, parameters wu=wi=0.5 hold in WSRec; α=0.8 holds in MCCP; user similarity threshold P=-0.5 holds in both SBT-SR and Ser_Rectime. Besides, in Ser_Rectime, α=0.09 holds in (3) and Wload=Wversion=1 holds (in WS-DREAM, a service was invoked by a user 64 times within successive 16 hours; therefore, we assume that the service load and version do not vary much). Finally, m is varied from 20 to 100 in all the four approaches.The experiment result is presented in Figure4. As Figure 4 shows, the recommendation accuracy of WSRec is low, as it only adopts the average ratings of target user and target services without considering the valuable user-service relationships hidden in historical service invocation records. The accuracy of MCCP is improved by considering the user-service relationships; however, it is not very suitable for service recommendation when target user has no similar friends and similar services, as MCCP is essentially a kind of similar user-based service recommendation approach. The recommendation accuracy of SBT-SR is high as “enemy’s enemy is a friend” rule of Social Balance Theory is recruited to find the “indirect friends” of target user. Furthermore, our proposed Ser_Rectime outperforms SBT-SR as Ser_Rectime not only considers Social Balance Theory, but also takes time factor into consideration for looking for the really similar “indirect friends” of target user. Besides, as shown in Figure 4, recommendation accuracy values of MCCP, SBT-SR, and Ser_Rectime all increase with the growth of m approximately; this is because more valuable user-service relationship information would be discovered and recruited for service recommendation when there are many users as well as their invocation records.Figure 4
Recommendation accuracy comparison with respect tom.(Profile 2) Recommendation Recall Comparison. In this profile, we compare the recommendation recall values of four approaches. The parameter settings are the same as those in profile 1. Concrete experiment results are shown in Figure 5.Figure 5
Recommendation recall comparison with respect tom.As Figure5 shows, the recall of WSRec is low as the “average” idea adopted in WSRec often leads to a low recommendation hit rate. The recommendation recall values of the remaining three approaches all increase with the growth of m; this is because when there are many available historical users, more useful user-service relationships could be mined and recruited in service recommendation; hence, more qualified recommendation results are returned finally. However, the recall of MCCP is still not high as few really similar friends of target user could be found in the recommendation situations that we discuss in this paper (i.e., the sparse recommendation situations when target user has no similar friends and similar services).While both SBT-SR andSer_Rectime approaches achieve good performances in recommendation recall, as Social Balance Theory is recruited to find out the indirect friends of target user even if the target user has no similar friends and similar services. Furthermore, our proposed Ser_Rectime approach often outperforms SBT-SR in recall. This is because only “enemy’s enemy is a friend” rule of Social Balance Theory is recruited in SBT-SR, while in Ser_Rectime, all four rules in Figure 2 are considered, which improves the recommendation hit rate to some extent.(Profile 3) Execution Efficiency Comparison with respect to m. In this profile, we test the execution efficiency of four approaches with respect to the number of users, i.e., m. Here, m is varied from 20 to 100; the number of services, that is, n=1000, holds; besides, P=-0.5, α=0.09, and Wload=Wversion=1 hold. The experiment result is shown in Figure 6.Figure 6
Time cost comparison with respect tom.As Figure6 shows, time cost of WSRec is the best, as WSRec only adopts the average ratings of target user and target services, without complex computation. The time costs of the remaining three approaches all increase with the growth of m quickly, as more similarity computation cost is required to determine the similar friends or dissimilar enemies of a user when the number of users increases. Furthermore, Ser_Rectime often requires more computation time as multiple iteration processes are probable for finding all the indirect friends of target user. However, as Figure 6 indicates, the execution efficiency of Ser_Rectime is often acceptable (at “minute” level).(Profile 4) Execution Efficiency Comparison with respect to n. In this profile, we test the execution efficiency of four approaches with respect to the number of services, that is, n. Here, n is varied from 200 to 1000; the number of users, that is, m=100, holds; besides, P=-0.5, α=0.09, and Wload=Wversion=1 hold. The concrete experiment result is shown in Figure 7.Figure 7
Time cost comparison with respect ton.As Figure7 shows, similar to profile 3, the time cost of WSRec is the best due to the adopted average idea. Besides, the time costs of the remaining three approaches all increase with the growth of m approximately linearly, as each service is considered at most once in each user similarity calculation process. However, as can be seen from Figure 7, the service recommendation process of Ser_Rectime approach could be generally finished in polynomial time.


## 4.1. Experiment Dataset and Deployment

The experiment is based on a real service quality dataset WS-DREAM [23]. WS-DREAM consists of 4532 IoE services on the web, and 142 distributed users from Planet-Lab are employed for evaluating the real quality (e.g.,response time andthroughput) of services in 64 time intervals (time interval = 15 minutes).Our paper focuses on the user-service rating-based recommendation, while available user-service rating data is really rare on the web; therefore, in the experiment, we need to transform the service quality data in WS-DREAM into corresponding user-service rating data (essentially, objective service quality data and subjective user-service rating data both reflect the service running quality; therefore, we argue that the transformation from former data to latter data makes sense for the service recommendation simulation here). Concretely, the transformation process is as follows: we determine the minimal and maximal quality values (denoted bymin and max, resp.) of a service observed by an identical user, and afterwards we divide the range [min,max] into five subranges in an arithmetic progression manner, each corresponding to a rating value. For example, if the minimal and maximal throughput values of a service wsj observed by useri are 10 kbps and 60 kbps, respectively, then we can get five subranges after division, that is, [10, 20) kbps, [20, 30) kbps, [30, 40) kbps, [40, 50) kbps, and [50, 60] kbps. Furthermore, if the throughput value of wsj observed by useri is 44 kbps in WS-DREAM, then the transformed user-service rating, that is, Ri-j=4∗, holds. For each service invoked by a user, we randomly select a time interval from all the 64 intervals and transform the service quality corresponding to the selected time interval into a user-service rating with a timestamp (i.e., the selected time interval). In the experiment, only a quality dimension, that is,throughput, is considered.Besides, our paper only discusses the time-aware service recommendation in sparse-data environment where target user has no similar friends and similar services. Therefore, we select appropriate data from WS-DREAM to simulate the above sparse recommendation situations. Furthermore, for each recruited target user, his/her 80% ratings are randomly selected for training while the remaining 20% ratings for testing.Also, we compare our proposal with related works, for example, WSRec [25], MCCP [26], and SBT-SR [27], in terms of recommendation accuracy and recall. Concretely, accuracy and recall are measured by Mean Absolute Error (i.e., MAE; the smaller the better) in (13) and Recall (the larger the better) in (14). In (13), Rec_Ser_Set denotes the recommended service set for target user; |X| denotes the size of set X; Rtarget-x and Rtarget-x# represent target user’s real and predicted ratings over service wsx, respectively. While in (14), symbols Preferred_Ser_Set and Rec_Ser_Set denote the service set really preferred (with 4∗ or 5∗ rating) by target user and the service set recommended to target user, respectively.(13)MAE=∑wsx∈Rec_Ser_SetRtarget-x-Rtarget-x#Rec_Ser_Set,(14)Recall=Preferred_Ser_Set∩Rec_Ser_SetPreferred_Ser_Set.The experiments were conducted on a Dell laptop with 2.80 GHz processors and 2.0 GB RAM. The software configuration is Windows XP + JAVA 1.5. Each experiment was carried out 10 times and the average results were adopted finally.


## 4.2. Experiment Results and Analyses

Concretely, four profiles are designed, tested, and compared. Here,m and n denote the number of users and number of services in the historical user-service invocation network.(Profile 1) Recommendation Accuracy Comparison. In this profile, we compare the recommendation accuracy of Ser_Rectime with the other three approaches, that is, WSRec, MCCP, and SBT-SR. Concretely, parameters wu=wi=0.5 hold in WSRec; α=0.8 holds in MCCP; user similarity threshold P=-0.5 holds in both SBT-SR and Ser_Rectime. Besides, in Ser_Rectime, α=0.09 holds in (3) and Wload=Wversion=1 holds (in WS-DREAM, a service was invoked by a user 64 times within successive 16 hours; therefore, we assume that the service load and version do not vary much). Finally, m is varied from 20 to 100 in all the four approaches.The experiment result is presented in Figure4. As Figure 4 shows, the recommendation accuracy of WSRec is low, as it only adopts the average ratings of target user and target services without considering the valuable user-service relationships hidden in historical service invocation records. The accuracy of MCCP is improved by considering the user-service relationships; however, it is not very suitable for service recommendation when target user has no similar friends and similar services, as MCCP is essentially a kind of similar user-based service recommendation approach. The recommendation accuracy of SBT-SR is high as “enemy’s enemy is a friend” rule of Social Balance Theory is recruited to find the “indirect friends” of target user. Furthermore, our proposed Ser_Rectime outperforms SBT-SR as Ser_Rectime not only considers Social Balance Theory, but also takes time factor into consideration for looking for the really similar “indirect friends” of target user. Besides, as shown in Figure 4, recommendation accuracy values of MCCP, SBT-SR, and Ser_Rectime all increase with the growth of m approximately; this is because more valuable user-service relationship information would be discovered and recruited for service recommendation when there are many users as well as their invocation records.Figure 4
Recommendation accuracy comparison with respect tom.(Profile 2) Recommendation Recall Comparison. In this profile, we compare the recommendation recall values of four approaches. The parameter settings are the same as those in profile 1. Concrete experiment results are shown in Figure 5.Figure 5
Recommendation recall comparison with respect tom.As Figure5 shows, the recall of WSRec is low as the “average” idea adopted in WSRec often leads to a low recommendation hit rate. The recommendation recall values of the remaining three approaches all increase with the growth of m; this is because when there are many available historical users, more useful user-service relationships could be mined and recruited in service recommendation; hence, more qualified recommendation results are returned finally. However, the recall of MCCP is still not high as few really similar friends of target user could be found in the recommendation situations that we discuss in this paper (i.e., the sparse recommendation situations when target user has no similar friends and similar services).While both SBT-SR andSer_Rectime approaches achieve good performances in recommendation recall, as Social Balance Theory is recruited to find out the indirect friends of target user even if the target user has no similar friends and similar services. Furthermore, our proposed Ser_Rectime approach often outperforms SBT-SR in recall. This is because only “enemy’s enemy is a friend” rule of Social Balance Theory is recruited in SBT-SR, while in Ser_Rectime, all four rules in Figure 2 are considered, which improves the recommendation hit rate to some extent.(Profile 3) Execution Efficiency Comparison with respect to m. In this profile, we test the execution efficiency of four approaches with respect to the number of users, i.e., m. Here, m is varied from 20 to 100; the number of services, that is, n=1000, holds; besides, P=-0.5, α=0.09, and Wload=Wversion=1 hold. The experiment result is shown in Figure 6.Figure 6
Time cost comparison with respect tom.As Figure6 shows, time cost of WSRec is the best, as WSRec only adopts the average ratings of target user and target services, without complex computation. The time costs of the remaining three approaches all increase with the growth of m quickly, as more similarity computation cost is required to determine the similar friends or dissimilar enemies of a user when the number of users increases. Furthermore, Ser_Rectime often requires more computation time as multiple iteration processes are probable for finding all the indirect friends of target user. However, as Figure 6 indicates, the execution efficiency of Ser_Rectime is often acceptable (at “minute” level).(Profile 4) Execution Efficiency Comparison with respect to n. In this profile, we test the execution efficiency of four approaches with respect to the number of services, that is, n. Here, n is varied from 200 to 1000; the number of users, that is, m=100, holds; besides, P=-0.5, α=0.09, and Wload=Wversion=1 hold. The concrete experiment result is shown in Figure 7.Figure 7
Time cost comparison with respect ton.As Figure7 shows, similar to profile 3, the time cost of WSRec is the best due to the adopted average idea. Besides, the time costs of the remaining three approaches all increase with the growth of m approximately linearly, as each service is considered at most once in each user similarity calculation process. However, as can be seen from Figure 7, the service recommendation process of Ser_Rectime approach could be generally finished in polynomial time.


## 5. Evaluations

In this section, we first analyze the time complexity of our proposedSer_Rectime approach. Afterwards, related works and comparison analyses are presented to further clarify the advantages and application scope of our proposal. Finally, we point out our future research directions.


### 5.1. Complexity Analyses

Suppose there arem users and n services in the historical user-service invocation network.Step 1.
According to (1)–(6), the time-aware similarity between target user and any other user could be calculated, whose time complexity is O(n). Afterwards, a user is judged to be an qualified enemy of target user or not based on (7), whose time complexity is O(1). As there are totally m users in set U, the time complexity of this step is O(m∗(n+1))=O(m∗n).Step 2.
In this step, we utilize the four rules (see Figure3) in Social Balance Theory iteratively, so as to find all the indirect friends of target user. And, in the worst case, the similarity between any two users in set U needs to be calculated. As there are m users in set U, the time complexity of this step is O(m2∗n).Step 3.
For each derived indirect friend (at mostm-1 indirect friends) of target user, we select his/her preferred services (at most n services) and recommend them to the target user. As the time complexity of preferred-service-judgment process is O(1), the time complexity of this step is O(m∗n).With the above analyses, we can conclude that the total time complexity of our proposedSer_Rectime approach is O(m2∗n).


### 5.2. Related Works and Comparison Analyses

With the advent of IoE age, an excessive number of IoE services are emerging on the web, which places a heavy burden on the service selection decision of target users. In this situation, various recommendation techniques, for example, CF-based recommendation [28] and content-based recommendation [29], are put forward to help the target users find their interested IoE services.A two-phaseK-means clustering approach is brought forth in [30] to make service quality prediction and service recommendation. However, this clustering-based approach often requires a dense historical user-service invocation matrix, and hence cannot deal with the service recommendation problem on sparse data very well. In [31], a CF-based recommendation approach is put forward, which realizes service recommendation based on the similar friends of target user. However, when the target user has no similar friends, the recommendation accuracy is decreased significantly. A bidirectional (i.e., user-based CF + item-based CF) service recommendation approach named WSRec is brought forth in [25], for high-quality recommendation results. However, when a target user has no similar friends and similar services, WSRec can only make a rough prediction and recommendation, by considering both the average rating from target user and the average rating of the service that is ready to be predicted. In [26], a MCCP approach is put forward to capture and model the preferences of various users over different services; however, only similar friends of target user are recruited for service quality prediction and recommendation, which drops some valuable user-service relationship information hidden in the historical user-service invocation records.In order to mine and introduce more user-service relationship information into recommendation, a service recommendation approach SBT-SR is proposed in our previous work [27]. By utilizing “enemy’s enemy is a friend” rule in Social Balance Theory, some indirect friends of target user could be found and utilized for further recommendation, which improves the accuracy and recall of recommendation in sparse-data environment. However, SBT-SR has two shortcomings: first, service invocation time is not considered in SBT-SR, which may decrease the recommendation accuracy as service quality is often dynamic and varied with time; second, SBT-SR only employs “enemy’s enemy is a friend” rule for service recommendation, while overlooks other valuable rules in Social Balance Theory, for example, “friend’s friend is a friend” rule, “friend’s enemy is an enemy” rule, and “enemy’s friend is an enemy” rule. In view of the above two shortcomings, a novel time-aware service recommendation approach named Ser_Rectime is put forward in this paper, to deal with the recommendation problem in sparse-data environment. Ser_Rectime considers not only the service invocation time but also the four rules of Social Balance Theory, so that the recommendation accuracy and recall could be ensured. Finally, through a set of experiments deployed on a real web service quality dataset WS-DREAM, we validate the feasibility of Ser_Rectime in terms of recommendation accuracy, recall, and efficiency.


### 5.3. Further Discussions

In this paper, we put forward a time-aware similarity for service recommendation. Generally, the proposed time-aware similarity could also be applied in other similarity-based application domains, such as content searching [32–36], information detection [37–45], and quality optimization [46–50]. However, there are still several shortcomings in our paper, which are discussed as follows:(1)
The time cost of our proposedSer_Rectime approach increases fast when the number of users grows. Therefore, the execution efficiency of Ser_Rectime needs to be improved, especially when a huge number of users are present in the historical user-service invocation records.(2)
In this paper, we have investigated the time-aware user similarity. However, besides service invocation time, many other factors, for example, user-service location information, also play an important role in user similarity calculation. In the future, we will improve our proposal by combining the time and location factors together.


## 5.1. Complexity Analyses

Suppose there arem users and n services in the historical user-service invocation network.Step 1.
According to (1)–(6), the time-aware similarity between target user and any other user could be calculated, whose time complexity is O(n). Afterwards, a user is judged to be an qualified enemy of target user or not based on (7), whose time complexity is O(1). As there are totally m users in set U, the time complexity of this step is O(m∗(n+1))=O(m∗n).Step 2.
In this step, we utilize the four rules (see Figure3) in Social Balance Theory iteratively, so as to find all the indirect friends of target user. And, in the worst case, the similarity between any two users in set U needs to be calculated. As there are m users in set U, the time complexity of this step is O(m2∗n).Step 3.
For each derived indirect friend (at mostm-1 indirect friends) of target user, we select his/her preferred services (at most n services) and recommend them to the target user. As the time complexity of preferred-service-judgment process is O(1), the time complexity of this step is O(m∗n).With the above analyses, we can conclude that the total time complexity of our proposedSer_Rectime approach is O(m2∗n).


## 5.2. Related Works and Comparison Analyses

With the advent of IoE age, an excessive number of IoE services are emerging on the web, which places a heavy burden on the service selection decision of target users. In this situation, various recommendation techniques, for example, CF-based recommendation [28] and content-based recommendation [29], are put forward to help the target users find their interested IoE services.A two-phaseK-means clustering approach is brought forth in [30] to make service quality prediction and service recommendation. However, this clustering-based approach often requires a dense historical user-service invocation matrix, and hence cannot deal with the service recommendation problem on sparse data very well. In [31], a CF-based recommendation approach is put forward, which realizes service recommendation based on the similar friends of target user. However, when the target user has no similar friends, the recommendation accuracy is decreased significantly. A bidirectional (i.e., user-based CF + item-based CF) service recommendation approach named WSRec is brought forth in [25], for high-quality recommendation results. However, when a target user has no similar friends and similar services, WSRec can only make a rough prediction and recommendation, by considering both the average rating from target user and the average rating of the service that is ready to be predicted. In [26], a MCCP approach is put forward to capture and model the preferences of various users over different services; however, only similar friends of target user are recruited for service quality prediction and recommendation, which drops some valuable user-service relationship information hidden in the historical user-service invocation records.In order to mine and introduce more user-service relationship information into recommendation, a service recommendation approach SBT-SR is proposed in our previous work [27]. By utilizing “enemy’s enemy is a friend” rule in Social Balance Theory, some indirect friends of target user could be found and utilized for further recommendation, which improves the accuracy and recall of recommendation in sparse-data environment. However, SBT-SR has two shortcomings: first, service invocation time is not considered in SBT-SR, which may decrease the recommendation accuracy as service quality is often dynamic and varied with time; second, SBT-SR only employs “enemy’s enemy is a friend” rule for service recommendation, while overlooks other valuable rules in Social Balance Theory, for example, “friend’s friend is a friend” rule, “friend’s enemy is an enemy” rule, and “enemy’s friend is an enemy” rule. In view of the above two shortcomings, a novel time-aware service recommendation approach named Ser_Rectime is put forward in this paper, to deal with the recommendation problem in sparse-data environment. Ser_Rectime considers not only the service invocation time but also the four rules of Social Balance Theory, so that the recommendation accuracy and recall could be ensured. Finally, through a set of experiments deployed on a real web service quality dataset WS-DREAM, we validate the feasibility of Ser_Rectime in terms of recommendation accuracy, recall, and efficiency.


## 5.3. Further Discussions

In this paper, we put forward a time-aware similarity for service recommendation. Generally, the proposed time-aware similarity could also be applied in other similarity-based application domains, such as content searching [32–36], information detection [37–45], and quality optimization [46–50]. However, there are still several shortcomings in our paper, which are discussed as follows:(1)
The time cost of our proposedSer_Rectime approach increases fast when the number of users grows. Therefore, the execution efficiency of Ser_Rectime needs to be improved, especially when a huge number of users are present in the historical user-service invocation records.(2)
In this paper, we have investigated the time-aware user similarity. However, besides service invocation time, many other factors, for example, user-service location information, also play an important role in user similarity calculation. In the future, we will improve our proposal by combining the time and location factors together.


## 6. Conclusions

In this paper, a novel time-aware service recommendation approach, that is,Ser_Rectime, is put forward, to handle the service recommendation problems in sparse-data environment where target user has no similar friends and similar services. Instead of looking for similar friends in traditional CF-based service recommendation approaches, in Ser_Rectime, we first look for dissimilar enemies of target user based on time-aware user similarity and further determine the indirect friends of target user based on Social Balance Theory. Afterwards, the services preferred by indirect friends of target user are recommended to the target user. Finally, through a set of experiments deployed on a real web service quality dataset WS-DREAM, we validate the feasibility of our proposal in terms of recommendation accuracy, recall, and efficiency.In the future, we will improve the recommendation effect of our proposal by considering more user-service location information. Moreover, distributed or parallel recommendation approaches will be investigated in the future to improve the recommendation efficiency.



---

*Source: 4397061-2016-12-14.xml*