In social communities the composition of thematic groups varies over time due to changes occurring in users' behaviors. To study the time evolution of such a process, we design a conceptual framework exploiting a distributed algorithm driving group formation. The results of tests carried out on real data extracted by the social network CIAO, show as groups formed by combining similarity and trust measures are i) more time-stable, independently by the weight of the trust component, and ii) more time-homogeneous, independently by the presence of uncorrelated random agents' behaviors affecting the similarity component.
Many online communities include thematic groups [1] and many studies investigated on the users motivations to join with groups [2], as well as the impact of their growth [3], [4] and failure [1]. Important issues in forming groups require to an agent of selecting those groups able to satisfy its expectation [5]- [8] and, in a complementary way, the members of a group search to accept only new agents able to improve their utility. Many studies present algorithms effective in driving such group formation processes (e.g., by using diffusion processes [3], [4]) by analyzing i) the group evolution in terms of surviving or failure and ii) the reasons for which an agent will join with/left a group. Many of such studies assume that groups should be formed by like-minded members. To this aim, many measures exist to evaluate the similarity degree among the groups members (e.g., based on the number of affiliations to groups [7], member/group interests [5], individual preferences [6] and so on).
In such a context, the aptitude of a group to retain its members (i.e., time stability) [9], [10] is a major factor for its survival or extinction. The evolution of these groups is, in the most part of the cases, driven only by the mutual similarity criterion [11], although it has evident limitations. Indeed, the problem of recommending groups to a potential member usually relies only on the mutual similarity between the profile features of a candidate at the time t and the interests of a group. When such interests vary in a relatively short time frame then groups selected at the time t could not be the best choice at the time t + ∆t.
Based on data of the social network CIAO [12], we verified as the mutual similarity alone does not ensure the group homogeneity over time. In particular, when uncorrelated (e.g., random) users' behavior aspects assume a relevant weight. Consequently, we investigated on improving the time-stability of the group homogeneity in terms of similarity. In this respect, recent studies on group formation processes consider trust [13]- [15] to increase the level of the group member's engagement over time and avoiding the group failure [16]. However, all the approaches reviewed in [16] do not face the problem of combining similarity with trust.
In [17]- [20] we proposed to integrate similarity and trust in a unique measure to form groups and finding those most suitable for joining with. In this paper, we extended this work to study how changes occurring in the similarity and trust measures impact on the groups formation over time. To test this approach, we used a new conceptual framework by means of which we verified, always by using the data of the social network CIAO, that groups formed by considering both similarity and trust have higher time-stable homogeneity, in terms of similarity, than groups formed by adopting the only similarity criterion. This result is valid also when both the weight assigned to the trust component is low or random (i.e., "uncorrelated") behavior components considered in computing the similarity have a relevant weight. We assume that this behavior is mainly due to the effect of trust in balancing potential incongruence of the similarity measures. Besides, we found as the function used to aggregate similarity and trust measures is not fundamental. Therefore, for a good trade-off between the need of producing accurate results and that of having an easy interpretation model, we aggregated similarity and trust by simply computing their weighted sum, as in [17].
The remaining of the paper is structured as follows: in Section II we present the related literature, in Section III the adopted reference scenario is introduced, while in Section IV deal with the similarity and trust measures computation. Sections V and VI illustrate the A2G algorithm and our conceptual framework. Section VII describes the experimental campaign, discuss its results and, finally, conclusions ends the paper.
In the group formation the common identity and bond theory [21] identifies as main mechanisms to join with a group (i) the strong personal ties and (ii)) the shared interests with other group members. Differently, in [2] the authors applied the community detection algorithms to identify clusters into OSNs and comparing their structural features with user-defined communities. A study on the group affiliation mechanisms is presented in [3], where in two different kind of networks the authors noted as the act to join with a group can be modeled in terms of new ideas spreading for both the networks. Kairam et al. [4] compared the growth processes in which groups attract new members in presence/absence of social ties with existing/any group members. Their main finding is that more a group is highly clustered and more likely it grows for a diffusion process. It is in accord with [1], where 500,000 Facebook groups created in an 8-day period were monitored for 3 months after which the most part of groups were inactive. The analysis of [1] highlighted that group survival depends on the social capital brought by group founders and of their behavior. Differently from us, any of the papers above explored the homogeneity of such groups to verify if they result timestable homogeneous in terms of similarity.
Homogeneous processes are defined as those whose parameters are time-stable with respect to some measure. Usual group formation processes do not assure that properties like to similarity, social identity and so on, will be time-stable. Conversely, some affiliation recommendation [7] processes suggest to an OSN user only time-stable groups. From a wide experimentation involving Social Identity and Cohesion theories on more Twitter datasets, the authors of [22] verified that groups based on the users' social identity and formed by users interested in a great variety of topics are less cohesive over time in presence of transient events.
A flexible framework in which group affiliation is treated as an event impacting on user's preferences is proposed and validated in [6], where a probabilistic framework provides to model the individual preferences when he/she joins with a group. In other words, it affiliates to a group those users maintaining a high similarity level into the group over time and keeping homogeneous the group under this point of view. In this scenario, we note as friendships and time-homogeneity of their relationships strictly depend by the mutual trust among individuals. Differently, in the literature the most part of the proposals to form time-stable groups consider it as a problem essentially involving some form of similarity among users.
Among the cited contributions, only [9] indirectly refers to trust, in the mean derived by the social theories [23], while the other consider some form of similarity as the unique criteria to form possible time-stable homogeneous groups.
Our framework involves a community C = A, G , where A and G are the sets of agents and groups active in C. Let I a set of available items, each one belonging to a specific category x, belonging to the set of categories X1 , that in C can be reviewed by each agent a ∈ A with an integer in the range [0, 5]. Moreover, let r a,i be the generic review of an item i ∈ I released by a, which consists of: (i) a rating assigned to i by a; (ii) a category x ∈ X associated with i; (iii) a numerical score specifying the helpfulness2 of r a,i ; (iv) a timestamp. Finally, we denote by r a the set of reviews associated with a, called review history, and by R the set of all the review history in C. In such a scenario, we assume to adopt a multi-agent platform where, each agent a u assists a user u, whereas an administrator agent a g assists a group g. The agents knowledge representation, the agent tasks and our definitions of similarity and trust will be introduced below.
Interests and preferences of each owner (i.e., u, g) are taken into account by the associated agent a ∈ A and stored into its profile p a consisting of (i) interests, (ii) behaviors, (iii) access modes and (iv) trust levels, as follows:
Interests: The interest of the agent a in a category x is a function I a (x) : A × X → [0, 1] ∈ R computed as the overall ratio of reviews for items belonging to x. More formally, I a (x) is expressed by I a (x) = |{r a,i : i ∈ x}|/|r a |, where r a is the review history of a, and we denote by r a,i each review contained in r a and referred to an item i.
Behaviors: The behavior field informs us about the activities admitted or not within a group. It is assumed to be a statement of the form "The average rating of items is greater than 3.0" and so on. Targets (e.g., average rating, frequency of posts, etc.) and goals (e.g., discriminating thresholds) of the statements depend on the specific considered community. Therefore, let b be a behavior (e.g., performed by a user, admitted into a group) and let B = {b 1 , b 2 , . . . , b p } be a given a set of behaviors. We assume to dispose of a function ζ a (b) : A × B → {True, False} which takes an agent a ∈ A and a behavior b ∈ B and checks whether the behavior b matches with the a's past behaviors. The set of behaviors associated with an agent a will be defined as B a , i.e., we set
Access modes: An access mode identifies a modality for accessing/allowing the access to a group, arbitrarily set by the agent owner, like to open, closed or secret, and let L be a list specifying such accessing modes. More in general, we supposed that a function M : A → L is available to associate an agent a ∈ A with a mode l ∈ L for accessing to a group. This components of the user profiles can be considered as fully random, and not correlated with the other components.
Trust levels: We suppose that an asymmetric trust function returning how much an agent j perceives another agent k as trustworthy is available (i.e., in general if j trusts k it does not mean that k trusts h too, t j→k = t k→j ). Trust levels are assigned during the agent interactions and mostly depend on the specific community. For instance, in CIAO everyone can explicitly declare the own trust about each other member. Similarly, the trust perceived by an agent a u with respect to a group g of agents can be defined as t au→g = v∈g t au→av /|g|.
Note that for a group g: (i) its administrator sets the admitted behaviors access modalities (denoted as M g ); (ii) the interest for a category x ∈ X is computed as the average of the interests of its agent members for x that are stored in their profiles; (iii) how the members of g perceive as trustworthy an agent a u is computed as t g→au = av∈g t av→au /|g|.
An agent updates its profile when an action involving information stored therein is performed. More precisely:
• After each performed action, an agent a u updates in its profile the interests and the boolean values of the involved behavioral variables. Similarly, an agent a g in its profile updates the behavioral variables every time the administrator of g changes the associated rules. Besides, each time that the preferred access modes change then the associated agent updates its profile.
• When u expresses his/her evaluation about another user v then a u updates the trust measure. We also assume that a Distributed Directory Facilitator agent (DDF) supports the other agents in C with an Agent Indexing Service and a Communication Layer enabling the agent message exchange.
To investigate the time-stability of groups in terms of similarity, by means of the model previously presented, we consider agents' similarities and trust relationships, as follows.
Let s u,v be the measure of similarity between the profiles of agents a u and a v computed as a weighted mean of the contributions of interests (c I ), behaviors (c B ) and access modes (c M ) normalized in [0, 1]. More formally,
where w I , w B , w M ∈ [0, 1] ∈ R are system weights for the contributes c I , c B and c M , in turn, are computed as follows:
• c I is based on the average difference between the interest values of a u and a v for each category x ∈ X :
• c B is computed on the average difference between the boolean variables contained in B au and B av . This difference is 0/1 if the two corresponding variables are equal/different.
The similarity s u,g between an agent and a group is computed in the same manner described above, simply by substituting a v with a g .
We view trust as two terms specifying how much an agent trusts another agent, and how much the community perceives an agent as trustworthy. A feedback mechanism usually allows each agent to record its satisfaction for its interactions with other agents in order to compute/update its trust measures [24]- [26] based on the concept of social capital [27]. In fact, a high rate of positive interactions means that an agent can receive an advantage to interact with another agent and, therefore, trust should increase/decrease in presence of positive/negative interactions. The first component, known in the trust theory as reliability, represents the satisfaction of a u about a v , i.e. rel au→av , and can specify several types of trust relationships (e.g., the honesty, the dependability or, as in this work, how much a u is satisfied by the services provided by a v ). Usually, reliability can assume values ranging in [0..1] ∈ R and the higher rel au→av , the higher the perception of the reliability of a v by a u . Note that reliability is an asymmetric measure. The second trust component, named reputation and denoted it by rep a in the interval [0..1] ∈ R, is a global measure of the trust perceived by the whole community about each other agent. The reputation is computed by averaging all the reliability values rel au→av for each a v ∈ A.
The two trust components are joined in a unique value to compute the trust a u about a v as t au→av = α au • rel au→av + (1−α au )•rep av , where α au ∈ [0..1] ∈ R is set by a u to weight the relevance it assigns to the first trust term with respect to the second one. Note that trust is an asymmetric measure because in the formulation it takes into account the reliability. Besides, each time a reliability value is updated by a u , it sends the new value to the DF that, in turn, returns a reputation value to a u when it needs to compute a trust measure.
As defined in [17], compactness is a measure combining trust and similarity, say γ au→av , able to exploit importance given to the mutual similarity with respect to the mutual trust. We model this level of importance by the coefficient W s, ranging in [0..1] ∈ R and, consequently, we define γ au→av as γ au→av = W s • s au,av + (1 − W s) • t au→av . Remember that trust is an asymmetric measure γ u→v = γ v→u .
In Table I the meaning of the symbols is reported.
In this section the algorithm (A2G), enabling user agents to select the groups to join with, is presented.
Let G = {g 1 , g 2 , . . . , g n } be the groups of C, with |G| = n. Moreover, let k au MAX be the upper bound ranging in [0, n] which specifies the number of groups a u desires to join with and reasonably it will be k MAX au << n. In the following, for convenience, the notation k MAX will be used instead of k au MAX . Algorithm A2G selects k MAX groups having the largest value of compactness of a u vs the joined groups. We assume that a u continues to receive the whole benefit from all the K ⊆ G groups which it is joined with, so that the overall received benefit in joining with all the K groups, in term of compactness, is given by gi∈K γ u→gi . Finding the subset K ⊆ G producing the best benefit for a u under the constraint |K | = k MAX is equivalent to solve an optimization problem. In this work, we assume that each user agent a u is unable to know, in advance, the compactness of all groups in G. Furthermore, we assume that: (i) a u is able to sample m random groups from G; (ii) a u will record into an internal cache, denoted as H the profiles of the groups a u joined with in the past; (iii) m is the number of the group agents that at each epoch must be contacted by a u . Algorithm 1 describes the steps a u performs to find the k MAX groups it can join with, while the Algorithm 2 runs on the group agent. In particular, it is assumed that (i) the size of each group g ∈ G is ≤ than a threshold n MAX ; (ii) n MAX is fixed by the group administrator; (iii) each agent a g stores into an internal cache the profiles of the agents who joined with g;
In our framework, a community is associated with a temporal dataset of events consisting of a matrix EM , where each row represents an event containing a timestamp, an agent identifiers and the event attributes. An events can be an action performed by an agent or an external event changing the state of the community. Furthermore, we assume that a (non timevarying) matrix T M of trust relationships is available, where each row is a pair of agent IDs (a u , a v ) representing a trust relationship among agent a u and agent a v . Moreover, A2G-Comp and A2G-Sim are two versions of the algorithm A2G. In the former the compactness γ is computed by setting W s < 1 (i.e., it is driven by similarity and trust) and for the latter W s = 1 (i.e., it is driven only by similarity).
The framework provides the weights w I and W s in the range [0, 1] ∈ R influencing the A2G algorithm results. w I represents the weight assigned to the agent interest, while 1 − w I is divided between w B , representing the weight assigned to the agents behavior (see Section IV), and w M . c M is set as random not being into the original dataset. The lower the value of w I , the higher the incidence of the component c M in computing the similarity, in other words c M is an "uncorrelated component". Furthermore, the higher the value of W s, the lower the impact of the trust relationship in computing the compactness γ.
In this perspective, the M AC (Mean Average Compactness) and M AS (Mean Average Similarity) measures have been used to perform experiments, in dependence of w I and W s.
Data: au: an agent, H the current set of groups of au, m: an integer in [0, n], kMAX: the number of groups au can join with Result: The new set S of groups of au Y = a set of m random groups extracted from DF; Z = H Y ; for (g ∈ Z) {au sends a message to ag and let pg be the profile of g}; S = the set of kMAX groups of Z with the highest compactness values; for (g ∈ S) do if (g / ∈ H) then {au sends a join request with its profile to ag}; else {au left g}; end return S Algorithm 1: The User Agent Task Data: r: an agent which has asked to join with the group, K, the set of agents in g for (au ∈ K) do {ag sends a message to au}; for (au ∈ K {r}) do {Compute γg→u}; More in detail, AC g (resp., AS g ) is defined as the Average Compactness (resp., Average Similarity), similarly to the average dissimilarity commonly exploited in Clustering Analysis [28], since a group g can be viewed as a cluster of agents. Note that M AC is computed in the training phase of the A2G-Comp algorithm (i.e. it only drives group formation), while M AS is computed in the test phase. Therefore measuring the variation of M AS can be useful to verify the homogeneity, in terms of similarity, of the groups formed in the training phase.
We considered the time-variation of the average similarity of the groups in two different cases: (i) (Comp) Groups formed by the A2G-Comp algorithm are driven by compactness (W s < 1). (ii) (Sim) Groups formed by the A2G-Sim algorithm are driven by the similarity criterion (W s = 1).
The computation of the measures are performed by following the steps described below: (i) Rows of the matrix EM are arranged in an increasing order, basing on the database timestamp. (ii) The matrix EM is divided into a number of time-windows of equal size. The first time-window is for the training set and the remaining for the tests. (iii) The trust network is built by loading the matrix T M and for all. (iv)
The training is performed by executing the algorithm A2G-Comp (resp. A2G-Sim) on the first time-window, in order to form groups of agents. (v) The training is stopped when "stable" values of M AC for A2G-Comp (M AS for A2G-Sim) are reach, i.e. the difference between two steps is less than a given threshold (in our case it was 5%). (vi) Data of the remaining time-windows is loaded in sequence for each of them and M AS is computed without executing the algorithm A2G, such that group composition remains the same as in the end of the training phase. This technique allows us to study the variation of M AS due to the addition of events representing the execution of some further actions by the agents.
Experiments exploited the described framework on a dataset extracted from the social network CIAO [12] 3 referred to 12, 375 users and consisting of two matrices (i.e., EM, T M ). Rows of matrix EM have the form {userID, productID, categoryID, rating, helpfulness, timestamp}, where categoryID is the commercial category of the item identified by productID which received the rating by the reviewer identified by userID, and helpfulness represents the level of satisfaction of the other member for that rating (it has not been used in our experiments).
Experiments were performed by varying weights w I and W s in the range [0.1 − 0.9]. Figures 1 and 2 report the execution of A2G-Comp for w I = 0.1 and w I = 0.5 and W s in the range [0.1 − 0.9]. In Figure 1 the values of the M AS are relevant also when the weight of the trust component is low (i.e., W s > 0.5). In particular, values of MAS are larger than 0.8 (e.g., median is 0.82 for W s = 0.8), giving a good time-stability with a visible bias around the median value, if compared to the results shown in Figure 2, on which the uncorrelated component starts to assume a less significant weight. Figures 3-4 show the results for the 1st, 2nd, and 3rd quartile, minimum and maximum values of M AS computed after the training for the remaining time windows. Figure 3 shows the behavior of A2G-Sim for different values of w I , while Figure 4 represents the different values of M AS for A2G-Comp with W s = 0.5. From these Figures we note that the lower the value of w I , the lower the value of overall similarity at the end of the test for A2G-Sim (Figure 3), while for A2G-Comp the values of M AS are higher of about 10%. This first set of results say us of driving groups formation by compactness when the weight w M is of at least 25% to obtain homogeneous time-stable groups in terms of average similarity.
The experimental study has been conducted with a distributed algorithm for groups formation, named A2G, which exploits the compactness measure, i.e. a combination of similarity and trust. The experimental approach of the conceptual framework permits to employ different combination of similarity and trust.
Obtained results have shown that forming groups on the basis of users' similarity will lead to form time-stable homogeneous groups if the weight of the uncorrelated behavioral components is marginal. Nevertheless, when group formation is driven by compactness (i.e., by combining similarity and trust) then groups result time-stable homogeneous even if the uncorrelated components included in the computation of similarity are relevant. Therefore, trust relationships will help to improve the level of resilience, in terms of similarity, also in presence of behavioral components which are not strongly linked with the others. Interestingly, even when the weight assigned to the trust relationship in the computation of compactness is very low, group formation driven by compactness will lead to a number of groups having a higher level of timestability with respect the similarity measure.