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.netWe 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 net￾works [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, Squeak￾foundation, 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 rec￾ommends items based on other users’ ratings. In addition to the rat￾ings 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. Advoga￾to.org is an online community site dedicated to free software devel￾opment. 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 robot￾s.net6 on March 1, 2009. The trust statements of Robots are weighted at three different levels: Apprentice, Journeyer, and Master. Kai￾tiaki.org, squeak.org and robots.net are all web community sites which use the same software which powers the Advogato web com￾munity site, mod virgule. These three datasets are much smaller than the Advogato dataset. The characteristics of our explored trust networks are summa￾rized 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 small￾world 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