236 w. Yuan et al/ Knowledge-Based Systems 23(2010)232-4 Table 6 Our proposed rating prediction algorithm. Between two random users Parameter: a(active user). i (item). dmax( the maximum tru distance), n(size of the trust network), k(average degrees of the trust Phase 1: MTPD calculation Phase 2: Recommender searcher Phase 3: Recommender weighting Phase 4: Rating calculation average path length of the trust network is a value between the ac- tive users' average trust propagation distances to the recommend ers and the active users' maximum trust propagation distances to he recommenders in addition due to small-worldness of the trust network, the active users' maximum trust propagation distances to the recommenders are short -within limited number of hops. So the maximum trust propagation distance from the active user to Fig.5. The distributions of the trust propagation distances between different users the recommender can not be significantly greater than the average of tARS path length of the trust network. aspired by the above observations, we heuristically choose 4. 1 Our proposed TARS model average path length of the trust network as the value of MTPD TARS. We therefore propose our TARS model by improving For different sized TARS, it is hard to directly point out the value ventional one based on the small-worldness of the trust networks of MTPD between two randomly selected users. However, since the The rating prediction algorithm of our proposed TARS model is ust network of TARS is the small-world network, it is easy to get shown in Table 6 the approximate average trust propagation distance between two Our proposed TARS model consists of four phases ndomly selected users of the trust network: it is similar to the The first phase is the MTPD calculation. In this phase, we use the average path length of the trust network's corresponding random average path length of the trust network used in TARS as the value network. We only need to know the size and the average degree of MTPD. Due to small-worldness of the trust network, this value of the trust network. Since the value of mTPD is unknown and approximately equals to the average path length of this trust net- the average path length of the trust network is the only available work's corresponding random network information about the distance between two users. it is interesting explore whether there is some relationship between these tw dnax=[≈ values. For this purpose, we compare the trust propagation dis tances from the active users to the recommenders with that be- where [ I represents the ceiling of selected value, e.g. [Ll is the tween two randomly select users. ceiling of the average path length of the trust network. The value We use the epinions dataset for the experiments of TARS. This of L is calculated by Eq (5). For the simulation data used in this re- dataset is chosen since the inputs of TaRS are the trust data and search, we get dmax"[L]=[Ll-[4.711-5 for TARS ng data, while other datasets shown in Section 3.2.1 only The second phase is the recommender searching In this phase ave the trust data, and only the epinions dataset has these data TARS searches all valid recommenders based on our selected simultaneously. The Epinions trust network, which is given in Sec- MTPD. A recommender is valid if (1) there is at least one trust tion 3. 2.1, acts as the trust data of the tars inputs. The ratings propagation path from the active user to the recommender in the ven by the users of Epinions on various items act as the rating data. trust network, and (2)the trust propagation distance from the ac- The rating data is given in the"epinions dataset". It consists of tive user to the recommender is no longer than [Ll 20, 157 users'ratings on 139, 633 items. Each user averagely rated The third phase is the recommender weighting In this phase. 32.94 items, and each item got around 4.76 ratings. Note that not the valid recommenders are weighted based on the relationship all users in the trust network are involved in the rating matrix between the active users' trust propagation distances to the rec since some users do not give any ratings on the items E.g. only ommenders and our selected MTPD. We use the similar weight around 40% users of Epinions are involved in rating matrix. The val- mechanism as the conventional TARS model, as shown in Eq (2 ues of ratings in the rating matrix are integers from 1 to 5, in which The difference is that our model explicitly points out the value of 1 means the user likes the item least, and 5 means the user likes MTPD, which is calculated by eq.(6). The weighting mechanism the item most. The ratings are predicted on each user's predicted of our model is items, in which all other users' ratings on this item are regarded as the recommendations The comparison of the trust propagation distances between dif- erent users of TARS is given in Fig. 5. It shows that a user tends to las shorter trust propagation distance with the recommender than The last phase is the rating calculation. In this phase ith a randomly selected user, and the maximum trust propaga- the ratings by aggregating the recommendations by the valid ion distance from the active user to the recommender is shorter recommenders Each recommendation is weighted with respect to than that between two randomly selected users. Therefore, the the weight of the recommender, which is calculated by Eq(7).The aggregation mechanism used in our model is the same as the con- ventional tars model, which is also the one used in ce as shown http://www.trustletorg/wiki/downloaded_epinions_dataset.4.1. Our proposed TARS model For different sized TARS, it is hard to directly point out the value of MTPD between two randomly selected users. However, since the trust network of TARS is the small-world network, it is easy to get the approximate average trust propagation distance between two randomly selected users of the trust network: it is similar to the average path length of the trust network’s corresponding random network. We only need to know the size and the average degrees of the trust network. Since the value of MTPD is unknown and the average path length of the trust network is the only available information about the distance between two users, it is interesting to explore whether there is some relationship between these two values. For this purpose, we compare the trust propagation dis￾tances from the active users to the recommenders with that be￾tween two randomly select users. We use the Epinions dataset for the experiments of TARS. This dataset is chosen since the inputs of TARS are the trust data and the rating data, while other datasets shown in Section 3.2.1 only have the trust data, and only the Epinions dataset has these data simultaneously. The Epinions trust network, which is given in Sec￾tion 3.2.1, acts as the trust data of the TARS inputs. The ratings gi￾ven by the users of Epinions on various items act as the rating data. The rating data is given in the ‘‘epinions dataset”.7 It consists of 20,157 users’ ratings on 139,633 items. Each user averagely rated 32.94 items, and each item got around 4.76 ratings. Note that not all users in the trust network are involved in the rating matrix since some users do not give any ratings on the items. E.g. only around 40% users of Epinions are involved in rating matrix. The val￾ues of ratings in the rating matrix are integers from 1 to 5, in which 1 means the user likes the item least, and 5 means the user likes the item most. The ratings are predicted on each user’s predicted items, in which all other users’ ratings on this item are regarded as the recommendations. The comparison of the trust propagation distances between dif￾ferent users of TARS is given in Fig. 5. It shows that a user tends to has shorter trust propagation distance with the recommender than with a randomly selected user, and the maximum trust propaga￾tion distance from the active user to the recommender is shorter than that between two randomly selected users. Therefore, the average path length of the trust network is a value between the ac￾tive users’ average trust propagation distances to the recommend￾ers and the active users’ maximum trust propagation distances to the recommenders. In addition, due to small-worldness of the trust network, the active users’ maximum trust propagation distances to the recommenders are short – within limited number of hops. So the maximum trust propagation distance from the active user to the recommender can not be significantly greater than the average path length of the trust network. Inspired by the above observations, we heuristically choose the average path length of the trust network as the value of MTPD for TARS. We therefore propose our TARS model by improving the con￾ventional one based on the small-worldness of the trust networks. The rating prediction algorithm of our proposed TARS model is shown in Table 6. Our proposed TARS model consists of four phases: The first phase is the MTPD calculation. In this phase, we use the average path length of the trust network used in TARS as the value of MTPD. Due to small-worldness of the trust network, this value approximately equals to the average path length of this trust net￾work’s corresponding random network: dmax ¼ d e L LR l m ¼ lnðnÞ lnðkÞ  ; ð6Þ where de represents the ceiling of selected value, e.g. dLe is the ceiling of the average path length of the trust network. The value of LR is calculated by Eq. (5). For the simulation data used in this re￾search, we get dmax = dLedLR e = d4.71e = 5 for TARS. The second phase is the recommender searching. In this phase, TARS searches all valid recommenders based on our selected MTPD. A recommender is valid if (1) there is at least one trust propagation path from the active user to the recommender in the trust network, and (2) the trust propagation distance from the ac￾tive user to the recommender is no longer than dLe. The third phase is the recommender weighting. In this phase, the valid recommenders are weighted based on the relationship between the active users’ trust propagation distances to the rec￾ommenders and our selected MTPD. We use the similar weighting mechanism as the conventional TARS model, as shown in Eq. (2). The difference is that our model explicitly points out the value of MTPD, which is calculated by Eq. (6). The weighting mechanism of our model is wa;u ¼ d eL da;u þ 1 d eL  L R l m da;u þ 1 LR l m : ð7Þ The last phase is the rating calculation. In this phase, we predict the ratings by aggregating the recommendations given by the valid recommenders. Each recommendation is weighted with respect to the weight of the recommender, which is calculated by Eq. (7). The aggregation mechanism used in our model is the same as the con￾ventional TARS model, which is also the one used in CF, as shown in Eq. (1). 1 2 3 4 5 6 7 8 9 10 11 0 0.1 0.2 0.3 0.4 0.5 Path Length Probability Between two random users Active user to recommender Fig. 5. The distributions of the trust propagation distances between different users of TARS. Table 6 Our proposed rating prediction algorithm. Algorithm: Our proposed rating prediction algorithm Input: T (trust matrix), R (rating matrix) Parameter: a (active user), i (item), dmax (the maximum trust propagation distance), n (size of the trust network), k (average degrees of the trust network) Output: pa,i (a’s predicted rating on i) Phase 1: MTPD calculation Phase 2: Recommender searching Phase 3: Recommender weighting Phase 4: Rating calculation 7 http://www.trustlet.org/wiki/Downloaded_Epinions_dataset. 236 W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238