W. Yuan et al Knowledge-Based Systems 23(2010)232-238 The organization of this paper is as follows: in Section 2, we prediction. However, existing works of tars did not propose any introduce the most popular TARS model in details and analyze its nechanism to set MTPD. They just randomly choose some value limitations;in Section3, we verify the small-worldness of the trust for this extremely important parameter. For example, in [1].the networks; in Section 4, we present a novel TARS model which is authors randomly set the value of MTPD as 1,2,3 and 4 to conduct based on the small-world topology of the trust network; the last different experiments of TARs. They did not verify whether these section concludes this paper and points out our future research. values are the suitable values. And they did not consider the rela- tionship between the value of MTPD and the scale of TArS. On one 2. Related works hand, if the value of MTPD is set too small, TARS might lose some valuable recommendations On the other hand, the computational A number of researches [1, 6-9 have focused complexity of constructing trust networks for TARS is O(kdmax),in the recommender system with the trust-awareness which k is the number of trusts stated per user, and dmax is the y Mas lue of MTPD, so if the value of MTPD is set too big, the computa- 1, 2, 10, 11 is the most popular one. In addition, their model has already been used in a practical application named Moleskingit timized value of MTPD for TARS should have some relationship 2. Due to its popularity their TARS model is used as the bas with the topology of the trust network. We therefore analyze the e the conventional of analysis in this research. The conventional TARS model specifi- TARS model based on the topology of the trust network trust matrix and the rating matrix. The output is the predicted 3. Finding small-world properties in trust networks ratings on the items for different users. The trust matrix is the trust between two users. The rating matrix records the users'rat- small-world networt in emr collection of the trust relations between the users of the recom Based on five trust ks extracted from the real online mender system. Each element of the trust matrix describes the ites, we verify in thi n that the trust network is the ings on the items. Each element of the rating matrix is the rating given by a user on a particular ite 3. 1. Definition of small-world networks The rating prediction mechanism of the conventional tARS model is similar as that of CF. The difference is that CF weights each The small-world network is a kind of network between the reg- recommendation based on the active users similarity with the re ular network and the random network. The regular network is ommender, while TARs weights each recommendation based highly clustered yet has long distance between two randomly se- the active user's trust on the recommender lected nodes. The random network is not clustered yet has short distances between nodes the small-world network is defined as he network that has [13: (1) Large clustering coefficient, which Pai=rat (1) is much larger than that of its corresponding random network. and(2)short average path length, which is almost as short as that where pai is the predicted rating on the item i for the active user a, of its corresponding random network, in which a network's corre- Ta is the active user's average rating on its rated items, r is the rec- sponding random network refers to the random network that has ommender u's average rating on its rated items, rui is the recom- the same number of nodes and same number of edges per node mender u,s recommendation on the item i, and k is the number of as this network. The relationship between the regular network, recommenders. Wa. u is the weight of the recommender u with re- the random network and the small-world network is summarized spect to the active user a, it is calculated as in Table 1. We further list the explanations of the notations used in this section in table 2 The clustering coefficient C represents the cliquishness of a typ ical neighborhood [13, i.e., how close the node and its neighbors where dmax is the maximum trust propagation distance(MTPD)be- are to be a complete network. The clustering coefficient of a net tween users of the recommender system. The value of MTPD is pre- work is the mean of the clustering coefficient of each node, in set by the administrator of TARS. dau is the active user a's trust which the clustering coefficient of a node is the fraction of the propagation distance to the recommender u. In TARS, the trust allowable edges and the edges that actually exist between the propagation distance refers to the number of hops in the shortest neighbors of this node [13] trust propagation path from the trustor to the trustee. As shown in the prediction mechanism of the conventional C n>c-i∑mm aber of connected neighbor pairs).(3) TARS model, MTPD is the fundamental parameter for the rating k(k-1) ot TPUT Estimated NxN Metre Trust [NxNI M: items User NxN NXm] Pure Collaborative Filtering Fig. 1. Trust-aware recommender system architecture 1.The organization of this paper is as follows: in Section 2, we introduce the most popular TARS model in details and analyze its limitations; in Section 3, we verify the small-worldness of the trust networks; in Section 4, we present a novel TARS model which is based on the small-world topology of the trust network; the last section concludes this paper and points out our future research. 2. Related works A number of researches [1,6–9] have focused on extending the recommender system with the trust-awareness. Among these works, the TARS model proposed by Massa and Avesani [1,2,10,11] is the most popular one. In addition, their model has already been used in a practical application named Moleskiing.it [12]. Due to its popularity, their TARS model is used as the basis of analysis in this research. The conventional TARS model specifi- cally refers to their model in this research. The architecture of TARS is shown in Fig. 1. The inputs are the trust matrix and the rating matrix. The output is the predicted ratings on the items for different users. The trust matrix is the collection of the trust relations between the users of the recom￾mender system. Each element of the trust matrix describes the trust between two users. The rating matrix records the users’ rat￾ings on the items. Each element of the rating matrix is the rating given by a user on a particular item. The rating prediction mechanism of the conventional TARS model is similar as that of CF. The difference is that CF weights each recommendation based on the active user’s similarity with the rec￾ommender, while TARS weights each recommendation based on the active user’s trust on the recommender: pa;i ¼ ra þ Pk u¼1wa;u ru;i ru Pk u¼1wa;u ; ð1Þ where pa,i is the predicted rating on the item i for the active user a, ra is the active user’s average rating on its rated items, ru is the rec￾ommender u’s average rating on its rated items, ru,i is the recom￾mender u’s recommendation on the item i, and k is the number of recommenders. wa,u is the weight of the recommender u with re￾spect to the active user a, it is calculated as wa;u ¼ dmax da;u þ 1 dmax ; ð2Þ where dmax is the maximum trust propagation distance (MTPD) be￾tween users of the recommender system. The value of MTPD is pre￾set by the administrator of TARS. da,u is the active user a’s trust propagation distance to the recommender u. In TARS, the trust propagation distance refers to the number of hops in the shortest trust propagation path from the trustor to the trustee. As shown in the prediction mechanism of the conventional TARS model, MTPD is the fundamental parameter for the rating prediction. However, existing works of TARS did not propose any mechanism to set MTPD. They just randomly choose some value for this extremely important parameter. For example, in [1], the authors randomly set the value of MTPD as 1, 2, 3 and 4 to conduct different experiments of TARS. They did not verify whether these values are the suitable values. And they did not consider the rela￾tionship between the value of MTPD and the scale of TARS. On one hand, if the value of MTPD is set too small, TARS might lose some valuable recommendations. On the other hand, the computational complexity of constructing trust networks for TARS is Oðk dmax Þ, in which k is the number of trusts stated per user, and dmax is the va￾lue of MTPD, so if the value of MTPD is set too big, the computa￾tional complexity of TARS increases exponentially. Intuitively, the optimized value of MTPD for TARS should have some relationship with the topology of the trust network. We therefore analyze the characteristics of the trust network and optimize the conventional TARS model based on the topology of the trust network. 3. Finding small-world properties in trust networks Based on five trust networks extracted from the real online sites, we verify in this section that the trust network is the small-world network. 3.1. Definition of small-world networks The small-world network is a kind of network between the reg￾ular network and the random network. The regular network is highly clustered yet has long distance between two randomly se￾lected nodes. The random network is not clustered yet has short distances between nodes. The small-world network is defined as the network that has [13]: (1) Large clustering coefficient, which is much larger than that of its corresponding random network, and (2) short average path length, which is almost as short as that of its corresponding random network, in which a network’s corre￾sponding random network refers to the random network that has the same number of nodes and same number of edges per node as this network. The relationship between the regular network, the random network and the small-world network is summarized in Table 1. We further list the explanations of the notations used in this section in Table 2. The clustering coefficient C represents the cliquishness of a typ￾ical neighborhood [13], i.e., how close the node and its neighbors are to be a complete network. The clustering coefficient of a net￾work is the mean of the clustering coefficient of each node, in which the clustering coefficient of a node is the fraction of the allowable edges and the edges that actually exist between the neighbors of this node [13]: C ¼ 1 n Xn i¼1 Ci ¼ 1 n Xn i¼1 ð Þ number of connected neighbor pairs kið Þ ki 1 : ð3Þ Fig. 1. Trust-aware recommender system architecture [1]. W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238 233