-Members of virtual communities generally expect and preferences). Therefore, for a given group, we define the that their groups satisfy some given requirements. For this average satisfaction computed on entire aim, the profile matching between user requirements and group In this work, we introduce a new measure, called Average crehparreascetnertistthices gcraonupbehcoomnosigdeenreeidty,asmtehaesumrionsgt hnoawturamluwchaythtoe Matching. The profile matching between user's requirements group members are mutually linked. However, optimizing profile and group's characteristics can be considered to represent the matching does not guarantee that the group will continue to group homogeneity, measuring how much the group members be homogeneous in time (i.e., cohesive). In the past we have are mutually linked. But, it is not said that the group will conalready shown that, when group formation is driven by trust tinue to be homogeneous in time (i.e., cohesive). Furthermore, Imneathsuisrews oarnkd, wpreofilperomvaetcbhyinegxpgreoriumpehnotsmoongeaneditaytaisseitmepxrtorvaecdte.d an agent, when declaring some characteristics of the profile, from a real social network, that trust measures can be used could be fraudulent, and this can affect the effectiveness to effectively replace profile matching for optimizing group's of the matching. For this reason, in [6], we introduce the cohesion. Furthermore, we prove also that using a local trust trustworthiness between two members. Moreover, computing measure will does not penalize the cohesion of the group. profiles similarities is not always possible because the user tuaIlnCdeoxmTmerumnist-Cieosh.esion, Homogeneity, Similarity, Trust, Vir- do not make publicly available such information in order to preserve his/her privacy [7]-[11]. In our past approach, we define another measure, called Average Compactness, taking I. INTRODUCTION into account both the similarity and the trustworthiness. On Social networks, as Facebook [1] and Twitter [2], involve the basis of this measure, we have introduced an algorithm, several users and online communities as, for example, those called User-to-Group (U2G), able to heuristically provide based on Internet Relay Chat. These communities are based a good solution to the problem of maximizing the Mean on social relationship, as the facebook friends and the twit- Average Compactness (M AS) of all the groups of the social ter followers: users form groups based on some thematic community. Clearly, groups formed based on compactness, interests [3], but the groups are also created for representing should be capable to exhibit an internal cohesion in time, classes in e-Learning activities, or set of customers interested even in absence of information about profile matching. In in performing together e-Commerce purchases. Furthermore, this paper, we define a criterion for measuring the actual some distributed systems as, Grid virtual organizations [4] or capability of the group to not decreasing in time the mutual cloud of clouds [5], can be viewed as virtual communities profile matching of their members. Secondly, in [6], we have whose members are software agents performing activities used a measure of the trustworthiness, only by taking into implying social interactions. account the direct knowledge. However, in many cases, it is Two main activities are performed in a virtual community impossible to estimate the trustworthiness because the agents with reference to group formation: a potential group member have not had direct contacts. To solve this problem, we have looks for interesting groups and a group administrator manages considered the possibility to use both the direct experience a group. Consequently, a potential new member asks for of interaction occurred with a (target) agent (i.e., reliability), joining with a group of interest and a group can accept or and the past experiences of the whole set of the agents refuse the request of a potential new member. In this way, it present in the community with the same target agent (i.e., is possible to produce groups whose members are satisfied of reputation). Moreover, in [12], we integrate the traditional their memberships. In many cases, new members must meet use of the global reputation with the local reputation, that some requirements to be part of a group. For this reason, in [6], is based on recommendations only coming by the entourage we have extended the concept of profile similarity to define a of the user. The experiments showed that the use of local measure, called Average Similarity, that represents the global, reputation improves the effectiveness of the recommendations mutual satisfaction perceived by the members of a group of with respect to the use of the global reputation and, in most of a virtual community. This measure takes into account the the cases, the use of the sole local recommendation is the best similarity between the profiles of two members (i.e., interests choice. In this paper, as a second contribution, we propose
to compare the use of the local reputation vs the simple reliability when using the algorithm U2G for automatically forming groups in virtual communities.
t(x, g) =
P{y∈g:t(x,y)6=NULL} t(x, y) |{x ∈ g : t(x, y) 6= N U LL}|
The matching metric is a mapping that receives as input two agents and yields as output a real value, ranging in the interval [0 · · · 1]. The profile matching metric is symmetric and explains how much the values of the profile properties of an agent match with the values of the corresponding properties of another agent. It is computed as
Pn i=1(ρix − ρiy) , where we assume that an
n appropriate operator “ −”is defined for each property ρi, that returns a real value in the interval [0 · · · 1]. Clearly, 0 means that there is not a matching between x and y. The matching between an agent and a group is defined in the following way:
Py∈g m(x, y)
, where |g| denotes the cardinality |g| of group g.
The trust t(x, y) is a mapping that receives as input two agents and yields as output a boolean value representing the degree of trust. The trust metric is asymmetric. In the same way, the trust perceived by an agent with respect to a group is defined as:
A relevant research area investigate on virtual
communities [
Other studies model trust in social communities by means
of a graph (usually sparse), defined trust network, whose
vertexes represent the users and oriented edges represent trust
relationships. For example, in [
The trust can be calculated in different ways [
In the other way, trust can be computed by adopting a local or a global approach in a centralized or distributed way.
Some researches states as the local trust is the more accurate
when personal users’ point of views are adopted [
The ego-network of an agent x will be defined as the subgraph of G, denoted by Gx, that represents all the agents both directly and indirectly trusted by x. Hereafter, we say that an agent y belongs to the ego-network of x if the node n(y) belongs to Gx. We assume that localtrust is a relation defined on A × A, such that an ordered pair of agents belongs to localtrust only when the node n(y) belongs to the ego-network III. THE PROPOSED EGO-NETWORK MODEL Gx of x. Also, for all the nodes n(x), n(y) such that [x, y] ∈ localtrust we also define a (normalized) local reputation
Our scenario is represented by a virtual community C, measure lrep(x, y) which represents how much the agents denoted as C = hA, G, m, ti, where A is the set of agents belonging to the ego-network Gx of x trusts y. We compute and G is the set of groups, while m and t are two mappings local reputation by suitably summing the contributions (in denoting the matching and the trust metric. terms of trust in y) coming by all the users k (with k 6= x)
Each group g is managed by an administrator agent ag. Fur- belonging to the ego-network of x which results to be also thermore, each agent and each group owns a profilepx defined connected with y. as a list of n property values, i.e. px = {ρ1x, ρ2x, .., ρxn}. Each Let total(x, y) be this sum, and we call local network, property ρix, i = 1, 2, .., n represents the value assumed by a denoted by lnet(a, b), the set of contributors, lnet(x, y) = {z : specific aspect characterizing the agent x in the community. z ∈ Gx ∧ ∃(z, y) ∈ Gy}. If k ∈ lnet(x, y) is a user in which x directly trusts, then there exists an arc (n(x), n(k)) ∈ Gx. Our model assumes that the contribution of k to total(x, y) is equal to 1. Otherwise, if k is indirectly trusted by x, then there exists at least one path in Gx which connects x and k. We assume that the shortest path between n(x) and n(k) belongs to Gx and suppose it has a length lx,k. In this case, the contribution provided by k to the trust computation we propose be equal to 1/2lx,k−1. Therefore, the formula adopted for the (normalized) local reputation is the following: rep(x, y) =
X k∈lnet(x,y),k6=x,y
1 2lx,k−1 max z∈A,z6=x,y
X h∈lnet(x,z),h6=x,z
1 2lx,h−1
The two trust components are integrated in a unique value
in the interval [
(2) where βu is a real coefficient belonging to [0..1] which is set by x to weight the relevance he/she assigns to the reliability with respect to the reputation.
Now, we introduce a measure to define how much a configuration of groups in C can be considered as cohesive. We denote the Average Matching as Mg = Px,y∈g,x6=y m(x,y) , |g| that measures how much the agents are mutually satisfied to stay in g. Then, we denote as Mean Average Matching (M AM ), a measure of the internal mutual satisfaction of the whole configuration of groups S, defined as follows: M AM = Pg∈S Mg (3) h
The goal is to improve the value of M AM until the maximum possible value. This problem is not an optimization problem, since the property values change in time, and the best we could do is to compute the optimum configuration at a given time t. Therefore, it is easy to see that finding this optimum is a N P -problem and it is not guarantee that this optimum at time t will be the optimum of M AM also at t + 1.
In this perspective, let S0 be a configuration at a time t0, then the higher the optimum of M AM at the time t0 + Δ, the better the cohesion of the configuration SΔ at time t0 + Δ. Then, we define a measure calledΔ-Cohesion ΦΔ(S), defined as follows: let S be a configuration of groups in a virtual community, considered at the time t0 and let Δ be the timewindow [t0, t + Δ]. We define Δ-Cohesion ΦΔ(S) as the M AM obtained at the end of the time-window [t0, t + Δ]. Therefore, a group configuration S2 having a ΦΔ(S2) greater than the ΦΔ(S1) of another group configuration S1, can be considered more cohesive than S1 in the given time-window Δ, since it finally produces groups that in average present better group matching values. We would define a rational strategy for leading the agents of the community to change in time the configuration of groups in order to maximize the Δ-cohesion.
Suppose that an agent x ∈ g1 evaluates the possibility to
change group by joining with g2 because m(x, g2) > m(x, g1).
But, it is possible that this change lowers the cohesion of g2.
In this case, x could be led to make bad choices by some
unreliable of even fraudulent agents. For this reason, in [
M AC =
Pg∈S ACg h (4)
We define the measure called Δ-Compactness ΥΔ(S), defined as follows: let S be a configuration of groups in a virtual community, considered at the time t0 and let Δ be the time-window [t0, t0 + Δ]. We define Δ-Compactness ΥΔ(S) as the M AC obtained at the end of the time-window.
We can construct our groups having available a training phase Δ1, but at the end of this phase we would desire to have a group configuration that will result the best cohesive at the end of a test phase Δ2 − Δ1. In this case, we have uncertainty about the evolution of the agents’ behaviors in the unknown time-window Δ2 − Δ1, and we could be deceiving when forming our groups in the training phase by the behavior of unreliable agents. A solution could be to form the groups in the training phase by using the compactness to take into account information about the agents’ trustworthiness. Therefore, the configuration S1∗, corresponding to the compactness ΥΔ1(S0) after the training phase, could produce a better cohesion ΦΔ2−Δ1(S1∗) at the end of the test phase than the cohesion ΦΔ2−Δ1(S1), produced by the configuration S1.
In this section, we sketch the design of the algorithm UserTo-Group (U2G), which enables user agents to select the groups to join with by maximizing the values of compactness Υ (see Figure 1) .
We suppose that G is the set of n groups in C. Moreover, let kMAX be a threshold ranging in [0, n] which specifies the upper bound on the number of groups each user u desires to join with. Algorithm U2G has been designed to select kMAX groups yielding the largest value of the M AC computed on G. We assume that as u joins with more than one group then each of them still continues to give the whole benefit to u, so that the overall benefit, in terms of M AC, received by u is equal to the sum of each contribution.
Therefore, in presence of an arbitrary number of groups
J ⊆ G, the benefit gained by u in joining with all the groups 3. Verify subset J ? ⊆ G progid∈uJcing the best benefit for u under the constraint |J ?| = kMAX is equivalent to solve an optimization
u problem.
As shown in Figure 1, the user au is able to sample m random groups from G, where m is the number of the group agents that at each epoch must be contacted by au.
Furthermore, au will record into an internal cache the profiles of the groups with which joined in the past; we shall denote this set as X. au performs various steps to find thekMAX groups to which u can join.
It is assumed that the size of each group cannot be bigger than a threshold nMAX, (a value fixed by the group administrator) and each agent ag stores into an internal cache the profiles of the users who joined g. In particular, let Y be a set of m random groups extracted from DF and Z = X [ Y .
For each group g in Y , au sends a message to the agent ag.
Let s be the set of kMAX group of Z having the highest values of M AC. For each g in S, if g ∈/ X, au sends a join request to the agent ag that also contains the profile pu of u. Otherwise, au deletes u from g. In this way, we obtain the set Z. In our example, au sends the join request only to the group gm, that has the highest value of M AC. Finally, au updates the set X.
In [
G1
User a1 < nmax
G2
User a2 < nmax
User
Gm am < nmax Random Groups
Y
DF
In our experiments, we have associated with each user a profile containing the expertise of the user in reviewing products, computed by averaging the helpfulness associated with each review posted by the user. Conversely, the reliability is represented by the values found in the dataset of trust relationships, while reputation has been calculated based on Eq. 1 (Section III). We make the following assumptions, necessary for the simulation campaign. The rows of the dataset are arranged in an increasing order based on the timestamp and the dataset is divided into 11 time-windows Δ. The first timewindow is used as training set, the remaining ten are used for the subsequent tests. Then, the reliability matrix is constructed by loading the dataset containing trust relationships and the training is performed by executing the algorithm U2G on the first time-window Δ1. At the end of this phase, a cohesion ΦΔ1 is measured. The test phase is performed by computing subsequent cohesion values, by adding data of time-windows Δ2, . . . , Δend, until the final value ΦΔend is found.
The goal is to understand the ability to form cohesive groups on the basis of the trust measure. In particular, we are interested in comparing final values of cohesion, i.e.
ΦΔend , among the different categories used to perform the
VI. EXPERIMENTS training test (i.e., training based on matching, training based
In this section we discuss the results obtained by the on matching and trust, and training based on trust only). For
executing the algorithm U2G on a real datasets, extracted this reason, we performed a number of experiments that can
from the social networks CIAO, described in [
Otherwise, we use only the local reputation.
In the case of CIAO, reliability is a boolean value and it does not allow us to make the distinction mentioned above.
For this reason, we used a variation of Eq. 2 that formula, as follows: t(x, y) = β rel(x, y) + (1 − β) rep(x, v) rep(x, y) rel(1, y) 6= 0 rel(1, y) = 0
(5) A. Evaluation
In this first set of experiments, we have compared the final cohesion of groups when the training is performed by considering only the matching criteria, and that obtained by mixing matching and trust (i.e., matching and reliability, matching and reliability with reputation and matching and reputation).
The first result is represented by the fact that forming groups by considering also the reliability does not degrade the cohesion of the groups since ΦΔend is not subject to significant variation on its presence. If the training is still performed on the base of matching and trust, and the trust component is represented by a mix of reliability and local reputation, the contribution given by the reputation does not lead negative changes of ΦΔend . Finally, in the case on which groups are formed by means of a training based on the mix between matching and local reputation, we observe that using the local reputation does not lead negative changes of ΦΔend . By this, it is clear that local reputation can be used in place of reliability when groups are formed by mixing matching and trust.
Now, we compare the value of ΦΔend obtained for matching only, with that obtained for reliability, reliability with reputation and reputation. By setting parameter ω = 0, only trust is included in the computation of compactness, used in the training phase, in order to form groups. Observe that ΦΔend are larger than values obtained in the previous cases for CIAO. In particular, if we use only the reliability value (i.e., LocalReputation = 0 and β = 1), we do not observe degradation in the cohesion of groups. Instead, even a little improvement of about 5% is obtained for CIAO, if compared with the previous case.
In conclusion, in the case of reputation only, we can say that local reputation, i.e. suggestions given by friends and friends of friends, can be effective in forming cohesive groups as much as direct knowledge, as it gives almost identical value of cohesion. Another important result is represented by the case reliability + reputation, in which we have an increase of ΦΔend of about 8%.
In this work, we have defined a theoretical agent framework and applied it to the dataset extracted from the CIAO social network. In particular, we propose to represent the attitude of a group to maintain its internal homogeneity in a time interval Δ by a measure called Δ-cohesion, based on the profile matching. Then, we have defined another measure, mixing profile matching and trust, denoted as compactness. Finally, we have tried to form groups on the real social networks of reference by optimizing, at time t0 the compactness, and by comparing our results with those obtained forming groups only based on the profile matching optimization. In both cases, the results are represented in terms of Δ-cohesion. Moreover, we have considered two different types of trust measures, namely the reliability and the local reputation. From the experiments, we can conclude that trust, and in particular local reputation, is a powerful tool to substitute profile matching for forming cohesive groups.
In the next future, we will try to go deeper into this result by performing a simulation campaign on a dataset extracted from an extensive social network.