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 cclustering coefficients of the trust networks with those of their cor￾responding randomly networks, it is obvious that the trust net￾works 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 compu￾tational expensive, so an accepted procedure is to measure it over a random sample of nodes [20]. The average path lengths for the lar￾ger 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 Epi￾nions 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 Squeakfoun￾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 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 net￾works, 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 net￾work [15], the human brain network [17,18], the film actors net￾work [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 repre￾sent the ratios of the selected networks and their corresponding random networks. Note that most small-world networks are con￾centrated 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 com￾parison clearly show that the trust networks have the same prop￾erties 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