Knowledge-Based Systems 23(2010)232-238 Contents lists available at Science Direct Knowledge-Based Systems ELSEVIER journalhomepagewww.elsevier.com/locate/knosys Improved trust-aware recommender system using small-worldness f trust networks Weiwei Yuan, Donghai Guan Young-Koo Lee a,, Sungyoung Lee Sung Jin Hur b Republic of Kore b Electronics and Telecommunications Research Institute(ETRI), Republic of Korea ARTICLE INFO A BSTRACT The trust network is a social network where nodes are inter-linked by their trust relations. It has bee idely used in various applications, however, little is known about its structure due to its highly dy Received in revised form 23 November 2009 pted 31 December 2009 nature. Based on five trust networks obtained from the real online sites, we contribute to verify that the Available online 6 January 2010 rust network is the small-world network: the nodes are highly clustered, while the distance between two randomly selected nodes is short. This has considerable implications on using the trust network in the trust-aware applications. We choose the trust-aware recommender system as an example of such applications and demonstrate its advantages by making use of our verified small-world nature of the 2010 Elsevier B.V. All rights reserved. Recommender system 1 Introduction its trust on any user of the trust network. This irregular growth leads to the complex structure of the trust network. Since the topology of The trust-aware recommender system (TARS)is the trust network is the important information to optimize TArs. mender system that suggests the worthwhile informat this research motives to make clear the structure of the trust net sers on the basis of trust, in which trust is the measu work. Furthermore based on the topology of the trust network, we less to believe in a user based on its competence an motive to optimize the conventional TARS model within a specific context at a given time. tars has re The contributions of this paper are mainly in two-fold proposed for use since it is able to solve the well-known data arseness problem of the collaborative filtering(CF)(1, 2]. This is We conduct experiments to verify the small-world topol- because trust is transitive. It means. if a trusts b and b trusts C.a ogy of the trust network, which can facilitate its usage in trusts c to some extend so even if there is no direct trust between arious trust-aware applications. Though the trust network the active users and the recommenders the active users can build has been assumed to be a small-world network by some up some indirect trust relationships with the recommenders via existing works 3-5, to the best of our knowledge, no the trust propagations. This contributes to the high rating predic one has verified its small-worldness experimentally or the- tion coverage of TARS. Moreover, the rating prediction accuracy etically. By analyzing five trust networks extracted from of TARS is no worse than the classical CF 1 e real online sites, we contribute to verify that the trust Despite of its high rating prediction accuracy and high rating pre- network is the small-world network: on one hand. the diction coverage, the conventional TARS model suffers from the nodes of the trust network are highly clustered, which is problem that it is not optimized: its computational complexity can similar to the regular network; on the other hand, the dis- be exponentially more expensive by achieving similar rating predi- tance between two randomly selected nodes of the trust cation accuracy and rating prediction coverage, and its rating predic network is short which is similar to the random network. tion coverage can be significantly worse by achieving similar rating We propose a novel TARS model which can effectively predication accuracy. This is because little is known about the topol- vercome the weakness of the conventional tars model ogy of the trust networks used in TARS. The trust network is highly This is achieved by leveraging our verified small-worldness ynamic: a user can join the trust network at anytime by stating ntal results clear show that. our proposed model is superior to the conventional one since it is able to achieve the maximum rating prediction accuracy and the maximum rating prediction coverage vith the minimum computat 0950-7051/s-see front matter o 2010 Elsevier B V. All rights reserved o:10.1016/ knosys2009.12004
Improved trust-aware recommender system using small-worldness of trust networks Weiwei Yuan a , Donghai Guan a , Young-Koo Lee a,*, Sungyoung Lee a , Sung Jin Hur b aDepartment of Computer Engineering, Kyung Hee University, Yongin, Republic of Korea b Electronics and Telecommunications Research Institute (ETRI), Republic of Korea article info Article history: Received 2 July 2009 Received in revised form 23 November 2009 Accepted 31 December 2009 Available online 6 January 2010 Keywords: Trust Trust network Small-world network Recommender system abstract The trust network is a social network where nodes are inter-linked by their trust relations. It has been widely used in various applications, however, little is known about its structure due to its highly dynamic nature. Based on five trust networks obtained from the real online sites, we contribute to verify that the trust network is the small-world network: the nodes are highly clustered, while the distance between two randomly selected nodes is short. This has considerable implications on using the trust network in the trust-aware applications. We choose the trust-aware recommender system as an example of such applications and demonstrate its advantages by making use of our verified small-world nature of the trust network. 2010 Elsevier B.V. All rights reserved. 1. Introduction The trust-aware recommender system (TARS) is the recommender system that suggests the worthwhile information to the users on the basis of trust, in which trust is the measure of willingness to believe in a user based on its competence and behavior within a specific context at a given time. TARS has recently been proposed for use since it is able to solve the well-known data sparseness problem of the collaborative filtering (CF) [1,2]. This is because trust is transitive. It means, if A trusts B and B trusts C, A trusts C to some extend. So even if there is no direct trust between the active users and the recommenders, the active users can build up some indirect trust relationships with the recommenders via the trust propagations. This contributes to the high rating prediction coverage of TARS. Moreover, the rating prediction accuracy of TARS is no worse than the classical CF [1]. Despite of its high rating prediction accuracy and high rating prediction coverage, the conventional TARS model suffers from the problem that it is not optimized: its computational complexity can be exponentially more expensive by achieving similar rating predication accuracy and rating prediction coverage, and its rating prediction coverage can be significantly worse by achieving similar rating predication accuracy. This is because little is known about the topology of the trust networks used in TARS. The trust network is highly dynamic: a user can join the trust network at anytime by stating its trust on any user of the trust network. This irregular growth leads to the complex structure of the trust network. Since the topology of the trust network is the important information to optimize TARS, this research motives to make clear the structure of the trust network. Furthermore, based on the topology of the trust network, we motive to optimize the conventional TARS model. The contributions of this paper are mainly in two-fold: – We conduct experiments to verify the small-world topology of the trust network, which can facilitate its usage in various trust-aware applications. Though the trust network has been assumed to be a small-world network by some existing works [3–5], to the best of our knowledge, no one has verified its small-worldness experimentally or theoretically. By analyzing five trust networks extracted from the real online sites, we contribute to verify that the trust network is the small-world network: on one hand, the nodes of the trust network are highly clustered, which is similar to the regular network; on the other hand, the distance between two randomly selected nodes of the trust network is short, which is similar to the random network. – We propose a novel TARS model which can effectively overcome the weakness of the conventional TARS model. This is achieved by leveraging our verified small-worldness of trust networks. Experimental results clear show that: our proposed model is superior to the conventional one since it is able to achieve the maximum rating prediction accuracy and the maximum rating prediction coverage with the minimum computational complexity. 0950-7051/$ - see front matter 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.knosys.2009.12.004 * Corresponding author. E-mail address: yklee@khu.ac.kr (Y.-K. Lee). Knowledge-Based Systems 23 (2010) 232–238 Contents lists available at ScienceDirect Knowledge-Based Systems journal homepage: www.elsevier.com/locate/knosys
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 recommender system. Each element of the trust matrix describes the trust between two users. The rating matrix records the users’ ratings 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 recommender, 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 recommender u’s average rating on its rated items, ru,i is the recommender u’s recommendation on the item i, and k is the number of recommenders. wa,u is the weight of the recommender u with respect 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) between users of the recommender system. The value of MTPD is preset 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 relationship 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 value of MTPD, so if the value of MTPD is set too big, the computational 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 regular network and the random network. The regular network is highly clustered yet has long distance between two randomly selected 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 corresponding 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 typical neighborhood [13], i.e., how close the node and its neighbors are to be a complete network. The clustering coefficient of a network 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
w. Yuan et al/ Knowledge-Based Systems 23(2010)232-4 Table 3 he comparison between the regular network, the random network and the small- Description of the trust networks used in this research world network. Number of nodes Number of edges per node egular Small-world network Average path length Short obots 1646 5412 Table 2 Notations used in the small-worldness verification foundation, Robots and Advogato respectively. These networks Symbol are extracted from the trust network datasets released trustlet org verage degree of the nodes in the network Epinions consists of 49, 288 users and 487, 183 trust statements. The data is extracted from epinions. com from November to Clustering coefficient of node December of 2003. Epinions. com is a recommender system that rec ommends items based on other users'ratings. In addition to th Average path length of the network ings on the items, the users are required to explicitly express their Average path length of the random network trust on other users. the trustor evaluates its trust on the trustee as 1 if the trustor consistently finds the ratings given by the trustee are valuable, otherwise, the trustor evaluates its trust on the trustee 0 Advogato consists of 5412 users and 54, 012 trust statements. The data is extracted from advogato. org on June 1, 2009. Advoga to. org is an online community site dedicated to free software devel- opment. On advogato. com users can certify each other as several evels: Observer, Apprentice, journeyer or Master [19. Masters are supposed to be excellent programmers who work full-time on free software, Journeyers contribute significantly, but not necessarily full-time, Apprentices contribute in some way, but are still acquiring Fig. 2. A network with 4 nodes and 7 edges. the skills needed to make more significant contributions, and observers are users without trust certification. these certifications are regarded as the trust statements of advogato We use the network shown in Fig. 2 as an example to explain Kaitiaki consists of 64 users and 154 trust statements The data the calculation of Eq (3) Node A has 3 neighbors, i.e. B, C and D, is extracted from kaitiaki. org on September 1, 2008. The trust so at most 6 edges can exist between A's neighbors. Four edges statements of Kaitiaki are weighted at four different levels: Kaitiro, actually exist in As neighborhood: BC, CB, CD and DB. So we get Te Hunga Manuhiri, Te Hunga Kainga, Te Komiti Whakahaere CA-4/6-2/3, and similarly CB-1/2, Cc=1/2 and Cp=2/3. The Squeakfoundation consists of 461 users and 2697 trust statements clustering coefficient of the network is: C=(CA+CB+Cc+ Cp) The data is extracted from squeak. org on November 1,2008.The 4=7/12 trust statements of Squeakfoundation are weighted at three different The clustering coefficient of a random network with n nodes levels: Apprentice, Journeyer, and Master Robots consists of 1646 d k edges per node is calculated as [13: users and 3456 trust statements the data is extracted from robot snet on March 1, 2009. The trust statements of Robots are weighted (4) at three different levels: Apprentice, Journeyer, and Master. Kai- (4) tiaki. org. squeak. org and robots. net are all web community sites The average path length L is defined as the number of edges in which use the same software which powers the Advogato web com- the shortest path between two averaged over all pairs of munity site, mod virgule. These three datasets are much smaller nodes [13]. The average path ler dom network with n than the Advogato dataset. nodes and k edges per node is ca as13: The characteristics of our explored trust networks are summa- rized in Table 3. All users involved in these trust networks act as LR (5) the trustors, the trustees or both. 3. 2. Experimental results 3.2. Experimental verifications on the small-woridness of trust Experiments are held on the above trust networks to verify their networks small-worldness Firstly, we verify that trust networks have large cluste le experimentally verify the small-woridness of the trust ficients. Using Eqs. (3)and (4), we get the clustering coeffic networks using data extracted from the real applications. The our explored five trust networks and their corresponding ring eot experimental verification methodology is used since it is the most networks, which are summarized in Table 4. Comparing the popular way to verify the small-world topology of various net works 13-18 2http://www.epinions.cor 3. 2.1. Experimental setup Five trust networks are used in this research to verify the http://www.kaitiaki.co.nz http://www.squeak.org/foundatio all-worldness. They are named as Epinions, Kaitiaki, squeak 6http://robots.net
We use the network shown in Fig. 2 as an example to explain the calculation of Eq. (3). Node A has 3 neighbors, i.e., B, C and D, so at most 6 edges can exist between A’s neighbors. Four edges actually exist in A’s neighborhood: BC, CB, CD and DB. So we get CA = 4/6 = 2/3, and similarly CB = 1/2, CC = 1/2 and CD = 2/3. The clustering coefficient of the network is: C = (CA + CB + CC + CD)/ 4 = 7/12. The clustering coefficient of a random network with n nodes and k edges per node is calculated as [13]: CR ¼ k n : ð4Þ The average path length L is defined as the number of edges in the shortest path between two nodes, averaged over all pairs of nodes [13]. The average path length of a random network with n nodes and k edges per node is calculated as [13]: L R ¼ lnðnÞ lnðkÞ : ð5Þ 3.2. Experimental verifications on the small-worldness of trust networks We experimentally verify the small-worldness of the trust networks using data extracted from the real applications. The experimental verification methodology is used since it is the most popular way to verify the small-world topology of various networks [13–18]. 3.2.1. Experimental setup Five trust networks are used in this research to verify the small-worldness. They are named as Epinions, Kaitiaki, Squeakfoundation, Robots and Advogato respectively. These networks are extracted from the trust network datasets released at trustlet.org1 . Epinions consists of 49,288 users and 487,183 trust statements. The data is extracted from epinions.com2 from November to December of 2003. Epinions.com is a recommender system that recommends items based on other users’ ratings. In addition to the ratings on the items, the users are required to explicitly express their trust on other users. The trustor evaluates its trust on the trustee as 1 if the trustor consistently finds the ratings given by the trustee are valuable, otherwise, the trustor evaluates its trust on the trustee as 0. Advogato consists of 5412 users and 54,012 trust statements. The data is extracted from advogato.org3 on June 1, 2009. Advogato.org is an online community site dedicated to free software development. On advogato.com users can certify each other as several levels: Observer, Apprentice, Journeyer or Master [19]. Masters are supposed to be excellent programmers who work full-time on free software, Journeyers contribute significantly, but not necessarily full-time, Apprentices contribute in some way, but are still acquiring the skills needed to make more significant contributions, and observers are users without trust certification. These certifications are regarded as the trust statements of Advogato. Kaitiaki consists of 64 users and 154 trust statements. The data is extracted from kaitiaki.org4 on September 1, 2008. The trust statements of Kaitiaki are weighted at four different levels: Kaitiro, Te Hunga Manuhiri, Te Hunga Käinga, Te Komiti Whakahaere. Squeakfoundation consists of 461 users and 2697 trust statements. The data is extracted from squeak.org5 on November 1, 2008. The trust statements of Squeakfoundation are weighted at three different levels: Apprentice, Journeyer, and Master. Robots consists of 1646 users and 3456 trust statements. The data is extracted from robots.net6 on March 1, 2009. The trust statements of Robots are weighted at three different levels: Apprentice, Journeyer, and Master. Kaitiaki.org, squeak.org and robots.net are all web community sites which use the same software which powers the Advogato web community site, mod virgule. These three datasets are much smaller than the Advogato dataset. The characteristics of our explored trust networks are summarized in Table 3. All users involved in these trust networks act as the trustors, the trustees or both. 3.2.2. Experimental results Experiments are held on the above trust networks to verify their small-worldness. Firstly, we verify that trust networks have large clustering coef- ficients. Using Eqs. (3) and (4), we get the clustering coefficients of our explored five trust networks and their corresponding random networks, which are summarized in Table 4. Comparing the Table 3 Description of the trust networks used in this research. Number of nodes Number of edges per node Epinions 49,288 9.88 Kaitiaki 64 2.41 Squeakfoundation 461 5.85 Robots 1646 2.1 Advogato 5412 9.98 Table 1 The comparison between the regular network, the random network and the smallworld network. Regular network Small-world network Random network Clustering coefficient Large Large Small Average path length Long Short Short Table 2 Notations used in the small-worldness verification. Symbol Explanation n Size of the network k Average degree of the nodes in the network ki Degree of node i Ci Clustering coefficient of node i C Clustering coefficient of the network CR Clustering coefficient of the random network L Average path length of the network LR Average path length of the random network D A C B Fig. 2. A network with 4 nodes and 7 edges. 1 http://www.trustlet.org/wiki/Datasets. 2 http://www.epinions.com/. 3 http://www.advogato.org/. 4 http://www.kaitiaki.co.nz/. 5 http://www.squeak.org/Foundation/. 6 http://robots.net/. 234 W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238
W. Yuan et al Knowledge-Based Systems 23(2010)232-238 Table stering coefficients of the trust networks and their corresponding random The average path lengths of the trust networks and their corresponding random networks 241 3.77×10-2 attak 1.27×10-2 285 3.94 9.9 Advogato 5412 998 023 84x10 Advogato 5412 3.80 0.4 r Kaitiaki 一 Squeakfoundation FilmAcror adver Human Brain Squeakfoundation Epinions Human ath Length Clustering Coefficient Ratio(Log Scale Fig 3. The distribution of the trust networks path lengths. Fig 4. The small-world characteristics of the trust networks and some well-known nts of the trust networks with those of their cor- the trust networks with those of their corresponding random net larger(higher order of magnitude) clustering works, it is obvious that the trust networks have similar (the same coefficients than their corresponding random networks. This satis fies the first condition of the smal -world networks definition random networks. This satisfies the second condition of the Secondly, we verify that trust networks have short average path small-world networks definition. networks We further compare the trust networks with some well-known tational expensive, so an accepted procedure is to measure it over a small-world networks documented in the literature: the world random sample of nodes(20) The average path lengths for the lar- Wide Web [14), the human language network [16 the e-mail net ger networks(Epinions and Advogato)in Table 3 are measured on work [15]. the human brain network[17, 18 the film actors net a random sample of 5% The average path lengths for the smaller work [13]. the power grid network [13]. and the C. elegans etworks( Kaitiaki, Squeakfoundation and robots )in Table 3 are network [13]. The comparison on the small-world characteristics networks'average path lengths are given in Fig 3. It shows that sent the ratios of the selected networks and their corresponding the trust networks have very small number of direct trusts, i.e. centrated around where the average path length ratio equals to ting can build up their trust relationships with others within several 1. This means that the selected networks have similar average path hops. Another important observation is that very small number of the trust propagations has long distance, e.g. the probabilities clustering coefficient ratios of the networks are greater than 10 hat the path lengths are longer than 8 hops (if any) are less than This means that the selected networks have much larger clustering 1%. The path lengths of most trust propagations are from 2 hops coefficients than their corresponding random networks. The com- to 6 hops. In more details: (1)the maximum path length of Epi- parison clearly show that the trust networks have the same prop ions is 11 hops, and its average path ler ngth is 3.96 hops: (2)the erties as other well-known small-world networks: they are highly naximum path length of Kaitiaki is 5 hops, and its average path clustered yet have small average path lengths. We therefore draw length is 2.16 hops: (3)the maximum path length of Squeakfoun- the conclusion that the trust network is the small-world network. dation is 6 hops, and its average path length is 2.85 hops: (4)the maximum path length of Robots is 11 hops, and its average path 4. Improving TARS using small-worldness of trust networks length is 3.94 hops: (5) the maximum path length of Advogate 9 hops, and its average path length is 3. 8 hops. Using our verified small-world topology of the trust networks Using Eq (5, we get the average path lengths of our explored we propose a novel TARS model which optimizes the conventional five trust networks'corresponding random networks, which are model by suggesting the values of MTPD. Our proposed method is summarized in Table 5. Comparing the average path lengths of straightforward and requires little c
clustering coefficients of the trust networks with those of their corresponding randomly networks, it is obvious that the trust networks have much larger (higher order of magnitude) clustering coefficients than their corresponding random networks. This satis- fies the first condition of the small-world network’s definition. Secondly, we verify that trust networks have short average path lengths. For large networks, measuring all-pair distances is computational expensive, so an accepted procedure is to measure it over a random sample of nodes [20]. The average path lengths for the larger networks (Epinions and Advogato) in Table 3 are measured on a random sample of 5%. The average path lengths for the smaller networks (Kaitiaki, Squeakfoundation and Robots) in Table 3 are measured on all pairs of nodes. The distributions of the five trust networks’ average path lengths are given in Fig. 3. It shows that the trust networks have very small number of direct trusts, i.e., where the path length equals to 1. By propagating trust, users can build up their trust relationships with others within several hops. Another important observation is that very small number of the trust propagations has long distance, e.g. the probabilities that the path lengths are longer than 8 hops (if any) are less than 1%. The path lengths of most trust propagations are from 2 hops to 6 hops. In more details: (1) the maximum path length of Epinions is 11 hops, and its average path length is 3.96 hops; (2) the maximum path length of Kaitiaki is 5 hops, and its average path length is 2.16 hops; (3) the maximum path length of Squeakfoundation is 6 hops, and its average path length is 2.85 hops; (4) the maximum path length of Robots is 11 hops, and its average path length is 3.94 hops; (5) the maximum path length of Advogato is 9 hops, and its average path length is 3.8 hops. Using Eq. (5), we get the average path lengths of our explored five trust networks’ corresponding random networks, which are summarized in Table 5. Comparing the average path lengths of the trust networks with those of their corresponding random networks, it is obvious that the trust networks have similar (the same order of magnitude) average path lengths as their corresponding random networks. This satisfies the second condition of the small-world network’s definition. We further compare the trust networks with some well-known small-world networks documented in the literature: the World Wide Web [14], the human language network [16], the e-mail network [15], the human brain network [17,18], the film actors network [13], the power grid network [13], and the C. elegans network [13]. The comparison on the small-world characteristics of these networks is presented in Fig. 4, in which the axes represent the ratios of the selected networks and their corresponding random networks. Note that most small-world networks are concentrated around where the average path length ratio equals to 1. This means that the selected networks have similar average path lengths as their corresponding random networks. In addition, most clustering coefficient ratios of the networks are greater than 10. This means that the selected networks have much larger clustering coefficients than their corresponding random networks. The comparison clearly show that the trust networks have the same properties as other well-known small-world networks: they are highly clustered yet have small average path lengths. We therefore draw the conclusion that the trust network is the small-world network. 4. Improving TARS using small-worldness of trust networks Using our verified small-world topology of the trust networks, we propose a novel TARS model which optimizes the conventional model by suggesting the values of MTPD. Our proposed method is straightforward and requires little computational efforts. Table 4 The clustering coefficients of the trust networks and their corresponding random networks. n kCCR Epinions 49,288 9.88 0.22 2 104 Kaitiaki 64 2.41 0.24 3.77 102 Squeakfoundation 461 5.85 0.44 1.27 102 Robots 1646 2.1 0.22 1.28 103 Advogato 5412 9.98 0.23 1.84 103 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 Robot Advogato Kaitiaki Squeakfoundation Epinions Fig. 3. The distribution of the trust networks’ path lengths. Table 5 The average path lengths of the trust networks and their corresponding random networks. n kLLR Epinions 49,288 9.88 3.96 4.71 Kaitiaki 64 2.41 2.16 4.73 Squeakfoundation 461 5.85 2.85 3.47 Robots 1646 2.1 3.94 9.98 Advogato 5412 9.98 3.80 3.74 1 10 100 1000 10000 0.1 1 10 Clustering Coefficient Ratio (Log Scale) Average Path Length (Log Scale) WWW Human Language E-mail Human Brain C. elegans Film Actors Power Grid Epinions Kaitiaki Squeakfoundation Robots Advogato Fig. 4. The small-world characteristics of the trust networks and some well-known small-world networks. W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238 235
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 distances from the active users to the recommenders with that between 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 Section 3.2.1, acts as the trust data of the TARS inputs. The ratings given 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 values 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 different 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 propagation 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 active users’ average trust propagation distances to the recommenders 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 conventional 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 network’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 research, 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 active 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 recommenders 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 conventional 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
W. Yuan et al Knowledge-Based Systems 23(2010)232-238 Recommender Coverage MTPD Fig. 6. The MAE of TARS: the MAE of the conventional TARS model can be any of the Fig. 7. The rating coverage and the recommender coverage of TARS: the coverages nine dots, while the rectangular dot represents the MAE of our proposed modeL f the conventional TArS model can be any of the nine dots, while the rectangular dots represent the coverages of our proposed model 4. 2. Experimental results dots shown in Fig. 7 represent the rating coverage and the recom- three aspects to verify its effectiveness. These three aspects inclugx mender coverage of our proposed model, in which [L is selected as examine he performance of our proposed TARS model the value of MTPD. The experimental results show that:(1)If the rating prediction accuracy, the rating prediction coverage and MTPD is set to be smaller than our suggested value, both the rating the computational complexity The data used for simulations are coverage and the recommender coverage of TARS decrease, in those shown in Section 4.1 which the recommender coverage decreases significantly. (2)If The rating prediction accuracy is measured by the error of the MTPD is set to be greater than our suggested value, the rating co predicted ratings of TARS. Specifically, we calculate the mean abso- erage and the recommender coverage of TARS do not significantly lute error(MAe)since it is very appropriate and useful for evaluat ing prediction accuracy in offline tests [1]. To calculate MAE, the coverage of Tars are both very high, more than 99%, by using our predicted rating is compared with the real rating and the difference ggested value of MTPD in absolute value)is the prediction error, this error is then aver- The computational complexity of constructing the trust net ged over all predictions to obtain the overall MAe. By predicting work for TARS is o(k ma ), as mentioned in Section 2. Therefore, if the rating on each rated item of our explored experimental data, MTPD (represented by dmax )is set to be smaller than our suggested value, the computational complexity of constructing trust net we report the MAE of TARS with different values of MiPd in works for TARS is exponentially less expensive. On the other hand to choose the value of MTPD, its MAE can be any of the nine dots if MTPD is set to be greater than our suggested value, the compu- shown in Fig. 6. The rectangular dot shown in Fig. 6 represens er tional complexity of constructing trust networks for TARS is the MAE of our proposed model, in which [L l is selected as the lue of MTPD. The experimental results show that: (1)If MTPD is set To sum up, though setting MTPD smaller than our suggested va- to be smaller than our suggested value, the rating prediction accu- lue is computational less expensive, the rating prediction accuracy racy of TARS is getting worse. 2)If MTPD is set to be greater than and the rating prediction coverage of TARS are worse; while setting our suggested value, the rating prediction accuracy of TArs dose MTPD greater than our suggested value leads to similar rating pre- not significantly change. diction accuracy and similar rating prediction coverage of tar The coverage of TARS is measured by both the rating coverage but it is computational exponentially more expensive. We there- fore draw the conclusion that [LI is a good estimation of MTPD and the recommender coverage. The rating coverage is the portion which provides the maximum rating prediction coverage and the of items that TARS is able to predict, i.e., the portion of items that the active user can get at least one recommendation. However this tional complexity. This verifies the effectiveness of our proposed naximum rating prediction accuracy with the minimum computa- quantity is not always informative about the quality of TARS TARS is sometimes good on the rating coverage, but only involve small model portion of recommenders. This is because an item usually has a number of recommendations, so a good rating coverage does not 5 Conclusions and future work ecessaril a good coverage on the recommenders. Since it facilities the rating prediction by involving as many recommenda- Analyzing five trust networks obtained from the real online ions as possible in TARS, we introduce the term recommender sites, we verify that the trust network is the small-world network. coverage. The recommender coverage is the portion of recom- This means that it is able to build up the trust relationship between menders that could be involved in TARS. By using different value two randomly selected users of the trust network within limited of MTPD, the rating coverage and the recommender coverage of number of hops, and the average path length of the trust network ur explored experimental data are given in Fig. 7. Since the con is similar to that of the random network that has the same number entional TARS model did not mention how to choose the value of users and same number of edges per user as the trust network. of MTPD, its rating coverage and the recommender coverage can This verified small-world nature of the trust network can facilitate be any of the nine dots shown in the lines of Fig. 7. The rectangular its usage in various applications. In this paper, we use tarS as an
4.2. Experimental results We examine the performance of our proposed TARS model in three aspects to verify its effectiveness. These three aspects include the rating prediction accuracy, the rating prediction coverage and the computational complexity. The data used for simulations are those shown in Section 4.1. The rating prediction accuracy is measured by the error of the predicted ratings of TARS. Specifically, we calculate the mean absolute error (MAE) since it is very appropriate and useful for evaluating prediction accuracy in offline tests [1]. To calculate MAE, the predicted rating is compared with the real rating and the difference (in absolute value) is the prediction error, this error is then averaged over all predictions to obtain the overall MAE. By predicting the rating on each rated item of our explored experimental data, we report the MAE of TARS with different values of MTPD in Fig. 6. Since the conventional TARS model did not mention how to choose the value of MTPD, its MAE can be any of the nine dots shown in Fig. 6. The rectangular dot shown in Fig. 6 represents the MAE of our proposed model, in which dL e is selected as the value of MTPD. The experimental results show that: (1) If MTPD is set to be smaller than our suggested value, the rating prediction accuracy of TARS is getting worse. (2) If MTPD is set to be greater than our suggested value, the rating prediction accuracy of TARS dose not significantly change. The coverage of TARS is measured by both the rating coverage and the recommender coverage. The rating coverage is the portion of items that TARS is able to predict, i.e., the portion of items that the active user can get at least one recommendation. However, this quantity is not always informative about the quality of TARS. TARS is sometimes good on the rating coverage, but only involve small portion of recommenders. This is because an item usually has a number of recommendations, so a good rating coverage does not necessarily imply a good coverage on the recommenders. Since it facilities the rating prediction by involving as many recommendations as possible in TARS, we introduce the term recommender coverage. The recommender coverage is the portion of recommenders that could be involved in TARS. By using different values of MTPD, the rating coverage and the recommender coverage of our explored experimental data are given in Fig. 7. Since the conventional TARS model did not mention how to choose the value of MTPD, its rating coverage and the recommender coverage can be any of the nine dots shown in the lines of Fig. 7. The rectangular dots shown in Fig. 7 represent the rating coverage and the recommender coverage of our proposed model, in which dLe is selected as the value of MTPD. The experimental results show that: (1) If MTPD is set to be smaller than our suggested value, both the rating coverage and the recommender coverage of TARS decrease, in which the recommender coverage decreases significantly. (2) If MTPD is set to be greater than our suggested value, the rating coverage and the recommender coverage of TARS do not significantly change. This is because the rating coverage and the recommender coverage of TARS are both very high, more than 99%, by using our suggested value of MTPD. The computational complexity of constructing the trust network for TARS is Oðk dmax Þ, as mentioned in Section 2. Therefore, if MTPD (represented by dmax) is set to be smaller than our suggested value, the computational complexity of constructing trust networks for TARS is exponentially less expensive. On the other hand, if MTPD is set to be greater than our suggested value, the computational complexity of constructing trust networks for TARS is exponentially more expensive. To sum up, though setting MTPD smaller than our suggested value is computational less expensive, the rating prediction accuracy and the rating prediction coverage of TARS are worse; while setting MTPD greater than our suggested value leads to similar rating prediction accuracy and similar rating prediction coverage of TARS, but it is computational exponentially more expensive. We therefore draw the conclusion that dLe is a good estimation of MTPD which provides the maximum rating prediction coverage and the maximum rating prediction accuracy with the minimum computational complexity. This verifies the effectiveness of our proposed model. 5. Conclusions and future work Analyzing five trust networks obtained from the real online sites, we verify that the trust network is the small-world network. This means that it is able to build up the trust relationship between two randomly selected users of the trust network within limited number of hops, and the average path length of the trust network is similar to that of the random network that has the same number of users and same number of edges per user as the trust network. This verified small-world nature of the trust network can facilitate its usage in various applications. In this paper, we use TARS as an 1 2 3 4 5 6 7 8 9 0.7 0.75 0.8 0.85 MTPD MAE Fig. 6. The MAE of TARS: the MAE of the conventional TARS model can be any of the nine dots, while the rectangular dot represents the MAE of our proposed model. 1 2 3 4 5 6 7 8 9 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 MTPD Coverage Rating Coverage Recommender Coverage Fig. 7. The rating coverage and the recommender coverage of TARS: the coverages of the conventional TARS model can be any of the nine dots, while the rectangular dots represent the coverages of our proposed model. W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238 237
w. Yuan et al/ Knowledge-Based Systems 23(2010)232 example of the applications, and show how the small-worldness of MKE/ KEIT. [2009-S-033-01, Development of Saas Platform for S/ the trust network contributes to the applica pecifically, we w Service of Small and Medium sized Enterprises. propose a novel TARS model by using L as MTPD for TARS. The simulation results show that: by involving recommenders that References are within LI hops away from the active user, it is possible to achieve high rating coverage and recommender coverage, while [1] P. Massa, P. Avesani. it is computational exponentially less expensive than using a great- systems, in: Proceedings 20pP+ Conference on the move to er value of MTPD. On the other hand, by using [L] as MTPD, the er- 12 P, 02 ACM Conference on Recommender Systems, Minneapolis, MN, USA, ACM, ommender systems, in: Proceed ror of the predicted ratings is less than the error of using a smaller value of MTPD. These simulation results verify the effectiveness of ur proposed methodology of TARS [31 E. Gray, J. Seigneur, Y. Chen, C. Jensen, Trust propagation in small worlds, in Our future work focuses on several aspects. Firstly, we will mprove the existing TARs models with the implicit trust net [4 M. Venkatraman, B. Yu, M.P. Singh, Trust and reputation management in a york. Existing works of TARS focus on using the explicit trust, while it is sometimes time consuming or expensive to get [51 x Guo, eling small-world trust networks licit trust. Explicit trust refers to the trust that should be explic ternational Symposium on Ubiquitous Multimedia Computing 2008, UMC itly pointed out by the users. These explicit trust statements ar then used as the inputs of TArs with the recommendations to th International Conference on Intelligent User Ints Proceedings of the predict the ratings. Though the explicit trust based TARS models have high rating prediction coverage and high rating prediction [7 P Bedi, H Kaur, S Marwaha, Trust based recommender system for semantic web, in: Proceedings of the 2007 International Joint Conferences on Artificial ccuracy, the explicit trust statements are not always available Intelligence, Hyderabad, India, pp. 2677-2682. Therefore, we will try to use other cheap and easy available trust n: Proceedings of Www-08, 2008, pp. 199-208. TARS. Secondly, we will focus on how to filter out the unfair rec- [9]G. Pitsilis, L Mar shall, A trust-enabled P2P recommender system, in: ommendations for TARS. TARS suggests information to the active sers based on the recommendations given by various Infrastructure for collaborative Enterprises, 2006. D0.59-64ing technologi [10 P. Massa, P. Avesani, Controversial users demand local trust metrics: an menders. However, there may exist some self-interested recom- own gains(perhaps at the cost of others ). So it is essential to 111 P. Massa. P Avesani, Trust metrics in recommender systems, in: Computing avoid or reduce the influence of the unfair positive or negative [12] P. Avesani, P. Massa, R. Tiella, A trust-enhanced recommender system recommendations from the self-interested recommenders for ication: moleskiing, in: Proceedings of the 2005 ACM Symposium this purpose, we intend to introduce the users'distrust state nents into our TARS model. By analyzing the recommendations [ 13] M. Newman, A Barabasi, D.J. Watts. The Structure and Dynamics of Networks first ed, Princeton University Press, given by each users distrusted recommenders and the relation- [14].A small world web. in: Proceedings of the Third European ship between the trust statements and the distrust statements Conference on Research and Advanced Technology for Digital Libraries, the reliable recommendations will be chosen for the rating aggre- [151 H. Ebel, L Mielsch, S. Bornholdt, Scale-free topology of e-mail networks gations of our proposed TARS model. Acknowledgements International Conference on Hybrid Intelligent Systems 2006, HIS06, 2006, p. The authors would like to thank anonymous reviewers and frequency, small-world human brain functional network with highly the editors of the journal for their valuable comments. This re- [181 Ds. 6 )512-527 Bullmore, Small-world brain networks, Neuroscientist 12 search was supported by the MKE(Ministry of Knowledge Econ- my), Korea, under the (Information Technology Research [19] P Mass. Center)support program supervised by the inta(Institute of Infor mation Technology Advancement) (IlTA-2009-(C1090-0902 [20 D Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton University Press, 1999. 0002)). Also, this work was supported by the IT R&D program of
example of the applications, and show how the small-worldness of the trust network contributes to the applications. Specifically, we propose a novel TARS model by using dLe as MTPD for TARS. The simulation results show that: by involving recommenders that are within dLe hops away from the active user, it is possible to achieve high rating coverage and recommender coverage; while it is computational exponentially less expensive than using a greater value of MTPD. On the other hand, by using dLe as MTPD, the error of the predicted ratings is less than the error of using a smaller value of MTPD. These simulation results verify the effectiveness of our proposed methodology of TARS. Our future work focuses on several aspects. Firstly, we will improve the existing TARS models with the implicit trust network. Existing works of TARS focus on using the explicit trust, while it is sometimes time consuming or expensive to get the explicit trust. Explicit trust refers to the trust that should be explicitly pointed out by the users. These explicit trust statements are then used as the inputs of TARS with the recommendations to predict the ratings. Though the explicit trust based TARS models have high rating prediction coverage and high rating prediction accuracy, the explicit trust statements are not always available. Therefore, we will try to use other cheap and easy available trust sensitive information to generate the implicit trust statements for TARS. Secondly, we will focus on how to filter out the unfair recommendations for TARS. TARS suggests information to the active users based on the recommendations given by various recommenders. However, there may exist some self-interested recommenders who give unfair recommendations to maximize their own gains (perhaps at the cost of others). So it is essential to avoid or reduce the influence of the unfair positive or negative recommendations from the self-interested recommenders. For this purpose, we intend to introduce the users’ distrust statements into our TARS model. By analyzing the recommendations given by each user’s distrusted recommenders and the relationship between the trust statements and the distrust statements, the reliable recommendations will be chosen for the rating aggregations of our proposed TARS model. Acknowledgements The authors would like to thank the anonymous reviewers and the editors of the journal for their valuable comments. This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Advancement) (IITA-2009-(C1090-0902- 0002)). Also, this work was supported by the IT R&D program of MKE/KEIT. [2009-S-033-01, Development of SaaS Platform for S/ W Service of Small and Medium sized Enterprises]. References [1] P. Massa, P. Avesani, Trust-aware collaborative filtering for recommender systems, in: Proceedings of Federated International Conference on the Move to Meaningful Internet, 2004, pp. 492–508. [2] P. Massa, P. Avesani, Trust-aware recommender systems, in: Proceedings of the 2007 ACM Conference on Recommender Systems, Minneapolis, MN, USA, ACM, 2007, pp. 17–24. [3] E. Gray, J. Seigneur, Y. Chen, C. Jensen, Trust propagation in small worlds, in: Proceedings of First International Conference on Trust Management (iTrust’03), 2003, pp. 239–254. [4] M. Venkatraman, B. Yu, M.P. Singh, Trust and reputation management in a small-world network, in: Proceedings of Fourth International Conference on MultiAgent Systems, 2000, pp. 449–450. [5] X. Guo, X. Li, Y. Qin, C. Chen, Modeling small-world trust networks, in: International Symposium on Ubiquitous Multimedia Computing 2008, UMC ’08, 2008, pp. 154–159. [6] J. O’Donovan, B. Smyth, Trust in recommender systems, in: Proceedings of the 10th International Conference on Intelligent User Interfaces, San Diego, California, USA, ACM, 2005, pp. 167–174. [7] P. Bedi, H. Kaur, S. Marwaha, Trust based recommender system for semantic web, in: Proceedings of the 2007 International Joint Conferences on Artificial Intelligence, Hyderabad, India, pp. 2677–2682. [8] R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai, V. Mirrokni, M. Tennenholtz, Trust-based recommendation systems: an axiomatic approach, in: Proceedings of WWW-08, 2008, pp. 199–208. [9] G. Pitsilis, L. Marshall, A trust-enabled P2P recommender system, in: Proceedings of 15th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, 2006, pp. 59–64. [10] P. Massa, P. Avesani, Controversial users demand local trust metrics: an experimental study on epinions.com community, in: Proceedings of 20th national conference on Artificial intelligence, 2005, pp. 121–126. [11] P. Massa, P. Avesani, Trust metrics in recommender systems, in: Computing with Social Trust, 2009, pp. 259–285. [12] P. Avesani, P. Massa, R. Tiella, A trust-enhanced recommender system application: moleskiing, in: Proceedings of the 2005 ACM Symposium on Applied Computing, pp. 1589–1593. [13] M. Newman, A. Barabasi, D.J. Watts, The Structure and Dynamics of Networks, first ed., Princeton University Press, 2006. [14] L.A. Adamic, The small world web, in: Proceedings of the Third European Conference on Research and Advanced Technology for Digital Libraries, Springer-Verlag, 1999, pp. 443–452. [15] H. Ebel, L. Mielsch, S. Bornholdt, Scale-free topology of e-mail networks, Physical Review E 66 (2002). [16] M. Markosova, P. Nather, Language as a small world network, in: Sixth International Conference on Hybrid Intelligent Systems 2006, HIS’06, 2006, p. 37. [17] S. Achard, R. Salvador, B. Whitcher, J. Suckling, E. Bullmore, A resilient lowfrequency, small-world human brain functional network with highly connected association cortical hubs, Journal of Neuroscience 26 (2006) 63–72. [18] D.S. Bassett, E. Bullmore, Small-world brain networks, Neuroscientist 12 (2006) 512–523. [19] P. Massa, K. Souren, Trustlet, open research on trust metrics, in: Proceedings of the 2nd Workshop on Social Aspects of the Web (SAW 2008), 2008, pp. 31–43. [20] D.J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton University Press, 1999. 238 W. Yuan et al. / Knowledge-Based Systems 23 (2010) 232–238