Recommending Items in Social Networks using Cliques-Based Trust Lidia Fotia† † DIIES, University Mediterranea of Reggio Calabria, Via Graziella, Località Feo di Vito, 89122 Reggio Calabria, Italy, lidia.fotia@unirc.it Abstract—Thematic groups are gaining a lot of attention and evaluating the level of trustworthiness of an interlocutor. high centrality in online community, as users share opinions Commonly, in the traditional OSN contexts, the reputation of and/or mutually collaborate for reaching their targets. In this a user is evaluated by averaging feedbacks provided by all the paper we consider the concept of clique in the social networks. A clique is a group of actors connected to each other more closely other users belonging to the same community. than the overall network of which they are a part. In the common In the past literature, there are many approaches based on language, the term clique means an informal and restricted global reputation [4]–[6] which is calculated on the evaluation social group formed by people who share common interests or of the users’ behaviours shared with the entire community, characteristics. This paper proposes a new trust measure in social and local reputation [7] that is based on the recommendations networks which focuses on cliques. In particular, we represent this scenario by means of a specific model, and we introduce coming by the entourage of the user (friends, friends of friends an algorithm for detecting trust recommendations. We show a and so on). The first type of approaches shows a limitation complete example of how our approach works. due to the difficulty of taking into account the effects of Index Terms—Recommendation, Online Communities, Trust, malicious or fraudulent behaviours, thus making the feedback Group. themselves. Also, they are limited by the fact they need a training phase in generating recommendations. The latter I. I NTRODUCTION overcome these limitations but they do not consider a group- based structure [8]–[10]. In the last few years, the number of users of online social In this paper we present an approach to find a certain class networks has grown at an unprecedented rate. Many social of groups of users linked by trust relationships. In particular, networks provide tools which recommend friends, and some- we apply the BronKerbosch algorithm [11] to find the cliques times resources, to their users. These tools rely on a notion in a social network. The algorithm is a simple backtracking of similarity between users or between a user and a resource. procedure that recursively solves subproblems specified by Obviously, they are not able to recommend to a user new social three sets of vertices: the vertices that are required to be networks potentially relevant to him. included in a partial clique, the vertices that are to be excluded For this reason, an important target in Online Social Net- from the clique, and some remaining vertices whose status still works (OSNs) is to implement recommender systems capable needs to be determined. Moreover, our approach depends on to supply users with profitable suggestions about users to two main parameters: the relevance given to the reliability with contact as interlocutors or interesting content to access. To respect to the reputation and the threshold of recommendation achieve this goal it is necessary to consider the opinions under which a product can be considered as not interesting. We provided by the community about the other users or the OSN propose an algorithm for detecting trust recommendations for content [1]–[3]. However, some users have malicious or even a user considering the recommendations that come from users fraudulent behaviours in OSNs, thus the recommender sys- within his own cliques and those of other cliques weighted tems could generate unreliable recommendations. Therefore, with the global reputation. We also present a complete example in these contexts, it is necessary to introduce the concept of of how our approach works and an application to a real social trust. network. The issue of trusting interlocutors largely emerged in online The paper is organised as follows. In the next section, e-Commerce communities as, for instance eBay, and now it is we describe the BronKerbosch algorithm. In Section III, we discussed in many OSNs which allow their users to create provides technical details about our approach for finding trust and share contents with other users as well as opinions. For recommendations about products. In Section IV, we survey example, in the social networks EPINIONS1 and CIAO2 the the related work of the recent literature. In Sections V and VI, users supply reviews about commercial products of different we describe a possible case study of the application. Finally, categories. Almost all of these platforms tackle this goal by in Section VII we draw our conclusions and illustrate some adopting a reputation system. possible future works. Reputation is a form of indirect trust, where a user takes advantage from the opinions coming from other users for II. T HE B RON K ERBOSCH A LGORITHM 1 www.epinions.com The BronKerbosch algorithm [11] is a recursive backtrack- 2 www.ciao.it ing algorithm used to find all maximal cliques in a graph. A 51 recursive call to the BronKerbosch algorithm supplies three able to evaluate y’s trustworthiness. In order to compute the sets of vertices C, S, and B as arguments, where C is a reputation, we adopt the notion of (possibly non-maximal) clique and S ∪ B = Γ(C) are the vertices that are adjacent to every vertex in C. Within the 1 X REPy = hρ (1) recursive call, the algorithm lists all cliques in S ∪ C that are hmax |REVy | ρ∈REVy maximal within the subgraph induced by S ∪ C ∪ B. where |REVy | is the set of the reviews made by the user y The algorithm selects v ∈ S to add to the clique C, and and h is the helpfulness, i.e., it is associated with each review makes a recursive call in which v has been moved from C to and represents the level of satisfaction of the other users for S. In this phase, it restricts B to the neighbors of v because that review. To normalise REPy , we divide it by the maximum non-neighbours cannot affect the maximality of the resulting value of the helpfulness hmax . REPy assumes values ranging cliques. At the end of the recursive call, v is moved to B. The in the interval [0 . . . 1]R. Finally, we define T RU STx,y of x recursion procedure ends when S and B are empty and the about y in the interval [0 . . . 1] as follows: output C is a maximal clique. To obtain all maximal cliques in the graph, This recursive algorithm is called with S equal T RU STx,y = α · RELx,y + (1 − α) · REPy (2) to the set of all vertices in the graph and with C and B empty. The algorithm is shown in Listing 1. where α is a real number, ranging in [0...1], which is set by x to weight the relevance he/she assigns to the reliability Listing 1. BronKerbosch algorithm with respect to the reputation. p r o c B r o n K e r b o s c h ( C , S , B) 1: i f (S ∪ B = 0) then 2: r e p o r t C a s a maximal c l i q u e A. The Trust-Based Recommendation System without and with 3 : end i f cliques 4 : f o r e a c h v e r t e x v ∈ S do 5: B r o n K e r b o s c h ( S ∩ Γ(v) , C ∪ {v} , B ∩ Γ(v) ) At this step, x receives some recommendations about the 6: S := S\{v} community products. In particular, RECxp is the recommenda- 7: B := B ∪ {v} tion that the user x receives about the product p. It is calculated 8 : end f o r as follows: p P p y∈A,y6=x T RU STx,y · ratey RECx = P (3) y∈A,y6=x T RU STx,y III. O UR SCENARIO where ratepy is the review of the the user y about the product We introduce a virtual community V , formally denoted as p (a number between 1 and 6), weighed by the trust of y. V = hA, Ci, where A is the set of agents joined with V and C This means that his/her opinion about a product is taken into is the set of cliques contained in V . Moreover, each clique c is account if his/her trustworthiness is high. handled by an administrator agent ac . All such communities 1) Cliques: Now, we introduce the clique’s concept in the are organised in social structures based on social relationship community. The cliques are calculated following the BronKer- (like, Facebook or Twitter). The formation of a group (i.e. bosch algorithm described in the section II. In this case, we cliques) is a process based on two main events: a user asks suppose that the trust perceived by an agent x with respect for joining with a group and the administrator of the group to the component of its clique is equal to tx,y + ∆, instead accepts or refuses the request. the agent x considers the trust that user has in the whole In our proposal, we introduce two measures to ensure that community (see Equation 2). In other words, if a user y the recommendation system generates correct outputs. The first belongs to the same clique of x, tx,y can be increased by measure is the trust. We denote it by the mapping T RU STx,y a value ∆. Being part of the same clique, even if x and y do that receives as input two agents x and y and produces as not know each other directly, they have interests in common output a value representing the degree of trust between two and there is an indirect connection between them. ∆ is a agents: T RU STx,y = 0 (resp. T RU STx,y = 1) means that x real number, ranging in [0...1], which is set by x to weight assigns the minimum (resp. maximum) trustworthiness to y. the relevance he/she assigns to the clique with respect to the The trust measure is asymmetric. If x does not have a sufficient standard configuration. tx,y + ∆ must not exceed 1. direct knowledge of y, the agent must use the recommenda- tions coming from the other agents of the community. For IV. R ELATED W ORK this reason, we introduce a more general trust measure, by Concerning the concept of trust, there are several proposals combining two components RELx,y and REPy , where (i) in the literature and in several domains [12]–[16] In particular, RELx,y is the direct reliability of y because has interacted a large number of papers in the literature investigated on the in the past with x while (ii) REPy is the global reputation topic we deal with here, therefore, in this section we cite of y, i.e. the trustworthiness that the whole community has only those approaches which we consider comparable with in y. In particular, [ RELx,y assumes values ranging in the that discussed in this paper. domain [0 . . . 1] {N U LL}, while RELx,y = NULL means Sherchan et al. [17] present an important review of trust, that y did not have past interactions with x and thus it is not in which they comprehensively examine trust definitions and 52 We apply the BronKerbosch algorithm (see Section II) to the graph depicted in Figure 1, which also contains the final set of cliques obtained by the algorithm itself. In our case, there are four cliques called c1 , c2 , c3 and c4 . Moreover, the values of REL are as follows: REL1,2 = 0.6, REL1,5 = 1, REL1,7 = 0, 82, REL1,8 = 0, 4, REL1,9 = 0, 3, REL1,11 = 0, 1, REL2,3 = 0, 81, REL2,4 = 0, 81, REL3,2 = 0, 9, REL3,4 = 0, 85, REL4,2 = 0, 9, REL4,3 = 0, 81, REL5,1 = 0, 9, REL5,7 = 0, 85, REL5,11 = 0, 4, REL6,8 = 0, 9, REL7,1 = 0, 81, REL7,5 = 0, 95, REL8,6 = 0, 81, REL9,10 = 0, 86, REL9,11 = 0, 85, REL10,9 = 0, 91, REL10,11 = 0, 85, REL11,9 = 0, 86, REL11,7 = 0, 3 and REL11,10 = 0, 9. In particular, in our example, there are nine products that are divided in three main categories called Electronics, Informatics Fig. 1. The cliques obtained by applying the BronKerbosch algorithm. and Software, these are shown in Table I, while in Table II, we show an example of dataset. measurements, from multiple fields including sociology, psy- productID name categoryID chology, and computer science. Trust models [18]–[21] allow 1 Car TomTom, Display 5” Electronics 2 Smartphone Android 5.1 Electronics to exploit information derived by direct experiences and/or 3 TV HD Ready 15,6” Format 16:9 Electronics opinions of others to trust potential partners by means of a 4 Notebook 15” i7, RAM 8 GB, HDD 500GB Informatics 5 Black and white laser printer Informatics single measure [22], [23]. Xia et al. [24] build a subjective trust 6 Tablet 7”, Wi-Fi, 8 GB Informatics management model AFStrust, which considers multiple factors 7 Microsoft Windows 7 PRO SP1 32/64-bit Software 8 Microsoft Office 365 Personal - 32/64 Bit Software including direct trust, recommendation trust, incentive function 9 Nuance Power PDF Standard Software and active degree, and treats those factors based on the analytic TABLE I hierarchy process (AHP) theory and the fuzzy logic rule. L IST OF PRODUCTS [25] describes how to build robust reputation systems using machine learning techniques, and defines a framework for translating a trust modelling problem into a learning problem. In our model, we have associated with each agent a profile In many disciplines, there is a population of people which contained, as unique feature, the reputation to review the should be optimally divided into multiple groups based on products. This reputation has been computed by averaging, on certain attributes to collaboratively perform a particular task all the reviews posted by the agent, the helpfulness associated [26], [27]. The problem becomes more complex when some with each review, where the helpfulness is an information other requirements are also added: homogeneity, heterogene- available on the dataset and obtained by the opinions ity or a mixture of teams, amount of consideration to the expressed by the users of the community. We obtain that the preferences of individuals, variability or invariability of group reputation values (see Equation 1) of the agents belonging size, having moderators, aggregation or distribution of persons, to our scenario are as follows: REP1 =0.79; REP2 =0.76; overlapping level of teams, and so forth [5], [28]–[30]. Basu REP3 =0.66; REP4 =0.42; REP5 =0.96; REP6 =0.62; et al. [31] consider the problem of how to form groups such REP7 =0.66; REP8 =0.5; REP9 =0.77; REP10 =0 and that the users in the formed groups are most satisfied with REP11 =0.58. At this point, we calculate the trust (see the suggested top-k recommendations. They assume that the Formula 2). Fixed the agent a1 , we compute the opinion recommendations will be generated according to one of the (i.e., trust) that a1 has with regard to other agents. Recall two group recommendation semantics, called Least Misery and that this value changes with α. We consider three values of Aggregate Voting. Rather than assuming groups are given, or α. In particular, α=1 means that the agent a1 considers only rely on ad hoc group formation dynamics, their framework the opinions of the agents with whom he/she interacted in allows a strategic approach for forming groups of users in the past (contrariwise, α=0). Finally, α=0.5 means that the order to maximise satisfaction. In [32], the authors reveal how agent a1 considers in the same way both the opinions of the these problems can be mathematically formulated through a agents with whom he/she interacted both others. For detail, binary integer programming approach to construct an effective see Table IV. Let ξ be a threshold fixed by the agent a1 , we model which is solvable by exact methods in an acceptable suggest only those products that have RECap greater than ξ time. (in our case, we fix ξ > 4). In particular, we note that the agent a5 that has a high value of reliability for the agent a1 buys the products p8 and p9 . Also, a5 assigns to them a high V. A N E -C OMMERCE CASE STUDY rate while the rest of the community gives a very low rate. Now, we explain how it is possible to use cliques to generate Surely a1 would be very interested in these products, because the recommendations of products for the users inserted into an he/she trusts a5 with a high value. At this point, we see how online e-Commerce communities. As an example, we propose the algorithm behaves. The agent a1 receives, at the current to model our community by a graph G. step, some recommendations by the other agents, in response 53 userID productID categoryID rating helpfulness u v tuv (α = 0) tuv (α = 0.5) tuv (α = 1) 1 9 3 3 5 1 2 0.76 0.68 0.6 1 5 2 3 5 1 3 0.66 0.33 0 1 6 2 5 2 1 4 0.42 0.21 0 1 7 3 1 6 1 5 0.96 0.98 1 1 8 3 5 6 1 6 0.62 0.31 0 2 1 1 3 5 1 7 0.66 0.74 0.82 2 2 1 4 6 1 8 0.50 0.45 0.4 2 5 2 4 5 1 9 0.77 0.54 0.3 2 6 2 5 5 1 10 0 0 0 2 8 3 5 2 1 11 0.58 0.34 0.1 3 1 1 4 2 3 8 3 5 3 TABLE IV 3 2 2 3 5 S IMULATION PARAMETERS WHEN VARYING α 3 4 2 6 6 4 1 1 5 1 4 3 1 5 2 4 6 2 3 6 4 9 3 2 1 can consider the assumption made in the Section III. Recall 5 1 1 2 6 5 3 1 2 6 that, for the agents that are in the same cliques, the trust is 5 4 2 4 5 equal to tx,y + ∆. If tx,y + ∆ is greater than 1, tx,y = 1. This 5 8 3 6 6 5 9 3 6 6 means that for any value of Delta, tx,y can not assume a value 6 6 2 2 6 greater than 1. Now, we can calculate the recommendations 6 5 2 4 2 6 7 3 1 4 (see Equation 3) to the agent a1 for all the products in the 6 8 3 0 3 community in presence of the cliques and ∆ = 0, 5. The table 7 1 1 4 4 7 9 3 4 6 V shows the results obtained. 7 5 2 5 3 7 8 3 4 3 α p1 p2 p3 p4 p5 p6 p7 p8 p9 8 1 1 5 2 0 3.74 3.76 3.33 4.79 4.42 3.64 1.00 3.65 3.99 8 3 1 5 0 0.5 3.92 3.83 3.16 4.47 4.50 3.96 1.00 3.90 4.17 8 6 2 2 5 1 3.32 4.00 3.03 4.00 4.62 4.52 0 4.37 4.49 8 9 3 3 5 9 2 1 4 4 9 6 2 2 5 TABLE V 9 9 3 3 5 T HE RECOMMENDATIONS TO THE AGENT a1 IN THE PRESENCE OF 11 1 1 5 3 CLIQUES 11 3 1 3 3 11 2 2 4 3 11 9 3 4 5 The results in the presence of the cliques are best, because TABLE II a3 and a7 know better a1 and consequently are able to make A N EXAMPLE OF DATABASE targeted recommendations. VI. T HE APPLICATION OF OUR PROTOCOL TO THE SOCIAL to previous recommendation requests (see Table III). If α=1, NETWORK CIAO we suggest to a1 the products p5 , p6 , p8 and p9 . In this case, In this section, we describe the implementation of our we consider the recommendations that come from agents that protocol for the social network CIAO. CIAO dataset, described have a high reliability. In fact, these products were acquired in [33], consists in a matrix with a total of about 36k rows, and evaluated good by agents a5 and a2 . Comparing these each of them representing an event in the virtual community, results with truly user-purchased products, it is visible that in the form userID, productID, categoryID, rating, helpful- four out of four products were actually purchased by a1 . If ness, timestamp. More in detail, CategoryID represents the α=0, we suggest to a1 the products p4 and p5 . This is correct commercial category of the product for which the user has because they are products purchased by agents who have a released a rating, and the helpfulness (a number between 1 and high reputation in the community. But, these agents did not 6) represents the level of satisfaction of the other users for that interact directly with a1 therefore they do not know his/her rating. In addition, a dataset representing trust relationships is preferences. Indeed, only the product p5 is of interest to a1 . available. It consists in a list of pairs of user IDs (x, y), where If α=0.5, we suggest to a1 the products p4 , p5 and p9 . This each of them represents a trust relationship among user x and choice is a good compromise, since two of the three products user y. are of liking for the agent a1 . The measure REP (see Formula 1) for each agent is calculated using the code shown in Algorithm 1. α p1 p2 p3 p4 p5 p6 p7 p8 p9 0 3.74 3.76 3.35 4.82 4.32 3.62 1.00 3.61 3.95 0.5 3.56 3.83 3.17 4.50 4.42 3.95 1.00 3.89 4.17 Listing 2. Algorithm 1: computeREP 1 3.28 4.00 2.87 4.00 4.58 4.52 0 4.42 4.49 Input r e v : t h e r e v i e w m a t r i x g e n e r a t e d by t h e a g e n t s Input numAg : t h e number o f a g e n t s i n t h e community Variable j : a r e a l number TABLE III Variable x : a r e a l number T HE RECOMMENDATIONS TO THE AGENT a1 Variable c o n t S c o r e : a r e a l number Variable sum : a r e a l number Variable r e p V a l u e : a v e c t o r 1 : sum : = 0 With the introduction of the cliques in the community, we 2: contScore :=0 54 3 : for x : = 1 to numAg do T RU STi,m = α + (1 − α) · repV alue[m] (Line 3). If there 4: for j : = 0 to length of r e v do 5: if x = r e v [ j ] [ 1 ] then is no interaction between i and m (Line 5), the algorithm 6: contScore := contScore + 1 calculates T RU STi,m = (1 − α) · repV alue[m] (Line 6). 7: sum : = sum + r e v [ j ] [ 4 ] ; 8: end if If there is a direct link between i and m but they have at 9: end for least a clique in common (Line 8), the algorithm calculates 1 0 : if ( sum 6= 0 ) AND ( c o n t S c o r e 6= 0 ) then 11: r e p V a l u e [ x ] : = ( sum / c o n t S c o r e ) / 6 ; T RU STi,m = α + (1 − α) · repV alue[m] + delta and store 11: sum = 0 ; it in the variable verif y (Line 9). The algorithm checks the 12: contScore =0; 1 3 : end if trust to verify if it takes a value equal to or less than 1 (Lines 1 4 : else 10-14). Finally, if there is no direct link between i and m but 15: repValue [ x ]=0; 1 6 : end else they have at least a clique in common (Line 17), the algorithm 1 7 : end for calculates T RU STi,m = (1 − α) · repV alue[m] + delta and First, for each agent x of the community (Line 3), if the verify if its value is equal to or less than 1 (Lines 18-23). index x corresponds to the one contained in the review matrix Whenever T RU STi,m 6= 0, its value is inserted into an output (Line 3), the algorithm saves all the helpfulness related to its file (Lines 26-27). reviews within the variable sum (Line 7) and increases the Finally, the measure RECxp (see Formula 3) for each agent variable contScore to keep track of the number of reviews x is calculated using the code shown in Algorithm 3. affected by x (Line 6). At this point, if x has issued at least Listing 4. Algorithm 3: computeREC one review (Line 10), the algorithm saves to the x position of Input r e v : t h e r e v i e w m a t r i x g e n e r a t e d by t h e a g e n t s the vector repV alue the value of REP (Line 11). Otherwise, Input t r u s t : t h e t r u s t m a t r i x o f t h e a g e n t s Input numProd : t h e number o f p r o d u c t s i n t h e community the rep value is set to zero (Line 15). Variable r e c P r o d : t h e m a t r i x o f recommended p r o d u c t s The measure T RU ST (see Formula 2) for each agent is Variable recAg : a r e a l number Variable s : a r e a l number calculated using the code shown in Algorithm 2. Variable sumRec : a r e a l number Variable y : a r e a l number Listing 3. Algorithm 2: computeTRUST 1 : recAg : = 1 Input a l p h a : a r e a l number 2: s :=0 Input d e l t a : a r e a l number 3 : sumRec : = 0 Input i : a r e a l number 4 : for y : = 1 to numProd do Input m: a r e a l number 5 : for n : = 0 to length of r e v do Input c l i q u e s : an a r r a y L i s t o f a r r a y L i s t 6: if ( y = r e v [ n ] [ 1 ] ) AND ( recAg 6= r e v [ n ] [ 0 ] ) Input r e p V a l u e : a v e c t o r AND ( t r u s t . CONTROL( recAg , r e v [ n ] [ 0 ] ) = t r u e ) then Input a d j a c e n c y m a t r i x : a S p a r s e M a t r i x 7: s : = s + r e v [ n ] [ 3 ] ∗ t r u s t ( recAg , r e v [ n ] [ 0 ] ) Input t r u s t o u t f i l e : a f i l e 8: sumRep : = sumRep + t r u s t ( recAg , r e v [ n ] [ 0 ] ) Variable i n t e r : a H a s h S e t 9: end if Variable v e r i f y : a r e a l number 1 0 : end for Variable d e l t a : a r e a l number 1 1 : if ( s 6= 0 ) AND ( sumRec 6= 0 ) then 1: i n t e r : = INTESECT ( c l i q u e s ( i ) , c l i q u e s (m) ) 1 2 : r e c P r o d ( recAg , y ) : = s / sumRec 2 : if ( a d j a c e n c y m a t r i x . CONTROL( i , m) = t r u e ) AND ( lenght 1 3 : end if of i n t e r = 0 ) then 1 4 : else 3: t r u s t ( i , m) : = a l p h a + (1− a l p h a ) ∗ r e p V a l u e [m] 1 5 : r e c P r o d ( recAg , y ) : = 0 4 : end if 1 6 : end else 5 : else if ( a d j a c e n c y m a t r i x . CONTROL( i , m) = f a l s e ) AND ( lenght 17: s := 0 of i n t e r = 0 ) then 1 8 : sumRec : = 0 6: t r u s t ( i , m) : = (1− a l p h a ) ∗ r e p V a l u e [m] 1 9 : recAg : = recAg + 1 7 : end else if 1 7 : end for 8 : else if ( a d j a c e n c y m a t r i x . CONTROL( i , m) = t r u e ) AND ( length of i n t e r 6= 0 ) then First of all, the algorithm initialises the variables recAg, s 9: v e r i f y : = a l p h a + ((1 − a l p h a )∗ r e p V a l u e [m] ) + d e l t a 10: if ( v e r i f y <= 1 ) then and sumRec (Lines 1-3). recAg stores the agent’s index to 11: t r u s t ( i ,m) : = v e r i f y which we want to recommend the product. It is incremented at 12: end if 13: else the end of each for loop (Line 19). For each product y of the 14: t r u s t ( i ,m) : = 1 community and for each row of rev (Lines 4-5), if there is a 15: end else 1 6 : end else if revision for the product y that has not been inserted by recAg 1 7 : else if ( a d j a c e n c y m a t r i x . CONTROL( i , m) = f a l s e ) AND ( length and there is a direct link between the reviser (i.e., rev[n][0] of i n t e r 6= 0 ) then 18: v e r i f y : = ((1 − a l p h a )∗ r e p V a l u e [m] ) + d e l t a ; ) and recAg, the algorithm calculates the numerator and the 19: if v e r i f y <= 1 then denominator of the Formula 3 (Lines 6-8). Then, the algorithm 20: t r u s t ( i ,m) : = v e r i f y 21: end if verifies that these values are different from zero and stores this 22: else value in a matrix in row recAg and column y (Lines 11-15). 23: t r u s t ( i ,m) : = 1 24: end else When the for loop on the revision matrix ends, s and sumRec 2 5 : end else if are reset and recAg is increased by 1 (Lines 17-19). 2 6 : if ( t r u s t ( i ,m) >0) AND ( t r u s t o u t f i l e 6= NULL) then 27: i n s e r t t r u s t ( i ,m) i n t r u s t o u t f i l e 2 8 : end if VII. C ONCLUSION First, the algorithm verifies if the agents i and m have In this paper, we introduce a trust model that integrates cliques in common and stores them in inter (Line 1). The reliability and reputation in an OSN organised by cliques. algorithm performs some checks to determine how to calculate In particular, we considered two important parameters: the the trust. If there is a direct link between i and m but they do relevance given to the reliability with respect to the reputation not have cliques in common (Line 2), the algorithm calculates and the threshold of recommendation under which a product 55 can be considered as not interesting. Furthermore, we present [13] ——, “Improving grid nodes coalitions by using reputation,” in Intelli- a realistic example and the results show that, combining the gent Distributed Computing VIII. Springer, Cham, 2015, pp. 137–146. [14] F. Messina, G. Pappalardo, D. Rosaci, C. Santoro, and G. M. Sarné, opinion of the whole community (reputation) with that of the “A trust model for competitive cloud federations,” Complex, Intelligent, agents who had direct interactions with her/him (reliability), and Software Intensive Systems (CISIS), pp. 469–474, 2014. the algorithm produces good recommendations. In addition, [15] P. De Meo, F. Messina, D. Rosaci, and G. M. Sarné, “Combining trust and skills evaluation to form e-learning classes in online social the algorithm is more accurate when the cliques are introduced networks,” Information Sciences, vol. 405, pp. 107–122, 2017. in the OSN. Finally, we apply our approach to the social [16] F. Messina, G. Pappalardo, D. Rosaci, C. Santoro, and G. Sarné, “A network CIAO. Our ongoing research is focused on better trust-based approach for a competitive cloud/grid computing scenario,” Intelligent Distributed Computing VI, pp. 129–138, 2013. analysing the behaviour of this algorithm. In particular, we are [18] E. Majd and V. Balakrishnan, “A trust model for recommender agent theoretically studying the efficiency and the effectiveness of systems,” Soft Computing, pp. 1–17, 2016. the approach from a statistical viewpoint, and we are perform- [19] S. Tadelis, “Reputation and feedback systems in online platform mar- ing some experimental campaigns for practically evaluating kets,” Annual Review of Economics, vol. 8, no. 1, 2016. [20] A. Comi, L. Fotia, F. Messina, D. Rosaci, and G. M. Sarné, “A the advantages introduced by our approach. partnership-based approach to improve qos on federated computing infrastructures,” Information Sciences, vol. 367, pp. 246–258, 2016. R EFERENCES [21] A. Comi, L. Fotia, F. Messina, G. Pappalardo, D. Rosaci, and G. M. Sarné, “A reputation-based approach to improve qos in cloud service [1] F. Buccafurri, L. Fotia, and G. Lax, “Allowing non-identifying in- composition,” in Enabling Technologies: Infrastructure for Collabora- formation disclosure in citizen opinion evaluation,” in International tive Enterprises (WETICE), 2015 IEEE 24th International Conference Conference on Electronic Government and the Information Systems on. IEEE, 2015, pp. 108–113. Perspective. Springer, 2013, pp. 241–254. [22] D. Rosaci, G. M. Sarné, and S. Garruzzo, “Integrating trust measures [2] ——, “Allowing privacy-preserving analysis of social network likes,” in in multiagent systems,” International Journal of Intelligent Systems, Privacy, Security and Trust (PST), 2013 Eleventh Annual International vol. 27, no. 1, pp. 1–15, 2012. Conference on. IEEE, 2013, pp. 36–43. [23] L. Xiong and L. Liu, “Peertrust: Supporting reputation-based trust for [3] ——, “Social signature: Signing by tweeting,” in International Confer- peer-to-peer electronic communities,” Knowledge and Data Engineering, ence on Electronic Government and the Information Systems Perspec- IEEE Transactions on, vol. 16, no. 7, pp. 843–857, 2004. tive. Springer, 2014, pp. 1–14. [24] H. Xia, Z. Jia, L. Ju, X. Li, and Y. Zhu, “A subjective trust management [4] P. De Meo, A. Nocera, D. Rosaci, and D. Ursino, “Recommendation model with multiple decision factors for manet based on ahp and fuzzy of reliable users, social networks and high-quality resources in a social logic rules,” in Green Computing and Communications (GreenCom), internetworking system,” Ai Communications, vol. 24, no. 1, pp. 31–50, 2011 IEEE/ACM International Conference on. IEEE, 2011, pp. 124– 2011. 130. [5] A. Comi, L. Fotia, F. Messina, G. Pappalardo, D. Rosaci, and G. M. [25] X. Liu, A. Datta, and E.-P. Lim, Computational Trust Models and Sarné, “An evolutionary approach for cloud learning agents in multi- Machine Learning. CRC Press, 2014. cloud distributed contexts,” in Enabling Technologies: Infrastructure [26] M. Wessner and H.-R. Pfister, “Group formation in computer-supported for Collaborative Enterprises (WETICE), 2015 IEEE 24th International collaborative learning,” in Proceedings of the 2001 international ACM Conference on. IEEE, 2015, pp. 99–104. SIGGROUP conference on supporting group work. ACM, 2001, pp. [6] P. D. Meo, K. Musial-Gabrys, D. Rosaci, G. M. Sarnè, and L. Aroyo, 24–31. “Using centrality measures to predict helpfulness-based reputation in [27] A. Comi, L. Fotia, F. Messina, D. Rosaci, and G. M. Sarné, “Grouptrust: trust networks,” ACM Transactions on Internet Technology (TOIT), Finding trust-based group structures in social communities,” in Interna- vol. 17, no. 1, p. 8, 2017. tional Symposium on Intelligent and Distributed Computing. Springer, [7] P. De Meo, F. Messina, D. Rosaci, and G. M. Sarné, “Recommending 2016, pp. 143–152. users in social networks by integrating local and global reputation,” [28] L. R. Hoffman and N. R. Maier, “Quality and acceptance of problem in International Conference on Internet and Distributed Computing solutions by members of homogeneous and heterogeneous groups.” The Systems. Springer, 2014, pp. 437–446. Journal of Abnormal and Social Psychology, vol. 62, no. 2, p. 401, 1961. [8] P. De Meo, L. Fotia, F. Messina, D. Rosaci, and G. M. Sarné, “Forming [29] A. Comi, L. Fotia, F. Messina, G. Pappalardo, D. Rosaci, and G. M. classes in an e-learning social network scenario,” in International Sarné, “Forming homogeneous classes for e-learning in a social network Symposium on Intelligent and Distributed Computing. Springer, 2016, scenario,” in Intelligent Distributed Computing IX. Springer, 2016, pp. pp. 173–182. 131–141. [9] D. Rosaci, “Finding semantic associations in hierarchically structured groups of web data,” Formal Aspects of Computing, vol. 27, no. 5-6, [30] ——, “Using semantic negotiation for ontology enrichment in e-learning pp. 867–884, 2015. multi-agent systems,” in Complex, Intelligent, and Software Intensive [10] P. De Meo, E. Ferrara, D. Rosaci, and G. M. Sarné, “Trust and com- Systems (CISIS), 2015 Ninth International Conference on. IEEE, 2015, pactness in social network groups,” IEEE transactions on cybernetics, pp. 474–479. vol. 45, no. 2, pp. 205–216, 2015. [31] S. Basu Roy, L. V. Lakshmanan, and R. Liu, “From group recommen- [11] C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an dations to group formation,” in Proceedings of the 2015 ACM SIGMOD undirected graph,” Communications of the ACM, vol. 16, no. 9, pp. International Conference on Management of Data. ACM, 2015, pp. 575–577, 1973. 1603–1616. [12] P. De Meo, F. Messina, D. Rosaci, and G. M. Sarné, “An agent-oriented, [32] A. A. Kardan and H. Sadeghi, “An efficacious dynamic mathematical trust-aware approach to improve the qos in dynamic grid federations,” modelling approach for creation of best collaborative groups,” Mathe- Concurrency and Computation: Practice and Experience, vol. 27, no. 17, matical and Computer Modelling of Dynamical Systems, vol. 22, no. 1, pp. 5411–5435, 2015. pp. 39–53, 2016. [17] W. Sherchan, S. Nepal, and C. Paris, “A survey of trust in social [33] J. Tang, X. Hu, H. Gao, and H. Liu, “Exploiting local and global social networks,” ACM Computing Surveys (CSUR), vol. 45, no. 4, p. 47, 2013. context for recommendation.” in IJCAI, vol. 13, 2013, pp. 2712–2718. 56