Evaluating Group Formation in Virtual Communities

Giancarlo Fortino, Antonio Liotta, Fabrizio Messina, Domenico Rosaci, Giuseppe M. L. Sarnè

Abstract—In this paper, we are interested in answering the following research question: “Is it possible to form effective groups in virtual communities by exploiting trust information without significant overhead, similarly to real user communities?”In order to answer this question, instead of adopting the largely used approach of exploiting the opinions provided by all the users of the community (called global reputation), we propose to use a particular form of reputation, called local reputation. We also propose an algorithm for group formation able to implement the proposed procedure to form effective groups in virtual communities. Another interesting question is how to measure the effectiveness of groups in virtual communities. To this aim we introduce the Gk index in a measure of the effectiveness of the group formation. We tested our algorithm by realizing some experimental trials on real data from the real world EPINIONS and CIAO communities, showing the significant advantages of our procedure w.r.t. another prominent approach based on traditional global reputation.

I. Introduction

VIRTUAL communities consist of social entities, users and/or agents, interested to mutually interact on a technical platform for reaching specific (individual or collective) goals. These communities usually exhibit complex social structures, emerging by some kind of social relationships, within a multidimensional scenario involving,for instance, social, physiological and computer science issues, to mention but a few. For example, online communities such as Facebook1www.facebook.comand Twitter2www.twitter.com, that account for hundreds of millions of in subscribers (in 2019, Facebook has reached 2.4 billion active users and Twitter surpassed 300 million users),allow the formation of thematicgroups. In fact, more than 1 billion groups have been formed in the last 5 years on Facebook.

Given their relevance, dynamics of virtual communities have been subject to a great number of studies [1]. Indeed,group formation in a community is often triggered by individual initiatives and evolves by means of well-defined social activities. For instance, a community member may ask to join an existing group for diverse reasons. One may be the similarity with certain attributes of the existing members (e.g.,age, interests, so on). In this case the group administrator may accept or refuse the request of the new member by evaluating a few important concerns. In this process, the group administrator may also want to involve group members in deciding whether the newcomer may join the group. We remark that this kind of scenario involves two different goals:i) the user wants to obtain a kind of “utility” by joining the group (e.g., for gaining knowledge); ii) the administrator wants to improve the “assessment” of the group itself, on the basis of some criteria.

The two activities above bring to a new member affiliation only when the sub-community representing the group gives a positive assessment to the new member. Differently, if the member joins the group without a positive assessment of his/her own social attitudes, there is a high probability that he/she will exit the group within a short timeframe. In other cases, his/her contribution to the social activities of the group will be very poor, he/she will be classified as an“outsider”. In general, the ability of the members of the same groups to have positive interactions will improve the social capital (or simply the effectiveness) of the community which represents the group itself [2].

In this work we address the general problem of forming effective groups. In particular, we are interested in three specific aspects related to the scenario described in the previous paragraph. The first aspect is related to the measurements of the overall effectiveness of a group, which is strictly related to the group composition, i.e., how the group component have been selected, to the context variables,e.g., the group topics. The second aspect is related to the group formation, i.e., the strategy applied by the community and/or by the group administrator to form groups. Last but not least, group formation is based on the computation of proper information about existing members and newcomers which is the third concern of our interest.

Note that our method performs a group formation,not a community detection.In fact,in our framework,agents are free to join with a group,and each group is free to accept or refuse a request.Our algorithm guides the agents to make the most rational choices, but it is not an automatic detection of sub-structures in the community,as for a clustering method,since it is necessary the willing of the actors for forming the groups,and also the values of reputations derive from the free behaviours of the actors.

A. Main Contributions

The contributions provided by this paper are as follows:i)the introduction of theGkindex associated with a set of groups in a virtual community,as a measure of effectiveness of the group formation activity;ii) the computation of individual trust, by combining reliability and local reputation information;iii)the adoption of a suitable voting mechanism,tested by means of a general-purpose distributed algorithm(referred to asGF,for Group Formation), to take decisions about newcomer affiliations.As we will discuss later in this paper,we will calltrust-voting(TV)the particular version ofGFthat makes use of the voting mechanism.

In order to test the approach described in this paper,we performed a number of experimental trials on the real data derived from the EPINIONS[3]and CIAO,communities.These include users’reviews concerning commercial products falling under different categories.These datasets have been largely used to perform study concerning trust,recommendation and social networks[4].Our experimental results show that the choice of combining reliability and local reputation,along with a voting mechanism, produces better results,in terms of theGkindex(k=10),compared to other existing solutions that did not use local reputation and voting mechanisms.

It is important to highlight that we have obtained these results on real datasets that are representative enough of common virtual communities,as the most known social networks,in terms of network topology and behaviour of the users.However,if data change,and for instance we have to face a community with a particularly high number of lowreputation users, the results could vary,and other investigations should be realized in the future for these particular situations.

The rest of the paper is organized as follow s.Section II discusses the details of the approach,while Section III describes the trust measures and the voting mechanism adopted in the proposed scenario.Section IV discusses the two parts of theGFalgorithm,while Section V presents the experimental trials we carried out.In Section VI our work is compared to related literature,while in Section VII we present our conclusions and anticipate possible further works.

II.Overall Approach

In this section we provide the details of the three research questions mentioned in the introductory section,as well as our approach for effective group formation (see Fig.1).

Fig.1.The conceptual framework about group formation and evaluation.

A. Measuring the Effectiveness of a Group

To clearly explain our first research question,let us suppose that each user belonging to the virtual community is characterized by asocial value,vthat quantitatively represents his/her utility for the whole community.For example,in the social communities CIAO3www.ciao.comand EPINIONS4www.epinions.com,in which users can publish reviews about products,the social utility of a review is represented by a value calledhelpfulness[5],computed by the feedbacks provided by the users about that review.In this context,the social utilityv,of a useru,could be reasonably considered as equal to the average of the helpfulness values associated with all the reviews published byu.

Now,let us suppose to classify the users belonging to a virtual community innclasses of social relevance, based on their social value.Just as an example,we could assume to have three classes(i.e.,n=3 ):the classC1of thebad users,having social valuev≤v1; the classC2of themedium users,havingv1v2,wherev1andv2are specific social values such thatv1

From a social viewpoint,i.e.,from a perspective in which the satisfaction of the whole community is the ultimate goal,the desired ideal configuration of the groups does not require to be composed only by the good users.Depending on the context,i.e.,on the particular nature of the involved social network,the possibility could arise to have groups whose composition involves also bad and medium users(that are themselves members of the network and,in such away, have a social value and their own expectancy).

Then,let us suppose that we wish to obtain groups having a particular distribution of the social values,i.e.,a percentagep1of users of classC1exactly equal to π1, a percentagep2of users of classC2exactly equal to π2,and so on until to a percentagepnof users of classCnexactly equal to πn(obviously,p1+p2+···+pn=1) ; wherep1,p2,...,pnare percentage values chosen by the group administrator.

For example,in the case of the CIAO and EPINIONS opinion networks,let us consider the three classes of bad,medium and good users,respectively,and let us suppose that it is socially desirable that all users have the same opportunity to find effective members into the groups that they have joined.The ideal goal of the whole community could reasonably be to achieve groups with an equipartition of the users in the three classes(i.e.,p1=p2=p3=1/3),since any other distribution would assign some social disadvantage to the users of some classes with respect to the users of other ones.

More formally,we can denote byV={V1,V2,...,Vn}a set of requirements on group formation,whereVirepresent theith requirement.For example, we may denote asV={V1={p1=33.3%},V2={p2=33.3%},V1={p3=33.3%}},the simple requirements for group formation in the previous example,wherepirepresents the desired percentage of users of classciin every group.

Also in the case of an e-Learning social community, where users are students with different levels of expertise, the equipartition appears the best choice,if the goal is to offer equal opportunities to all students(in an equi-partitioned solution,each group is formed by individuals of the same class,so that the learning process does not need to be adapted to students of different levels).However,in other situations,the equipartition of the users in the available classes may not be the best choice.For example,in an e-Commerce scenario such as in the case of eBay, where the social value of a user is given by the feedback score representing his/her reliability,it is probable that the best distribution is that of groups containing only users having high feedback scores,admitting only a few users that have medium feedback score(to give them some sort of second chance)and tending to exclude users having low feedback scores.In such a situation,depending on the tolerance degree of the network administrator for the medium users,we will have distributions with high value ofp1, low value ofp2and a value 0 forp3.

More formally, we can give the following simple definition.

Definition 1:The social disadvantage is defined as a functionDV(g)to measure the social disadvantage of a groupgw.r.t.a given set of requirementV.

We observe that,if we have formedmgroups, we would like to have a high percentage of groups having a low social disadvantage.Basing on this simple observation, we can give the following definition.

Definition 2:TheGkindex associated with a set of groupsgand a set of requirementsVin a given virtual community is defined as the percentage of the groups whose social disadvantageDV(g)is less than or equal tok/100.

We remark that group formation is not an optimization problem “driven”by the social values.Indeed,the social values of the users(i.e.,the helpfulness values in the case of CIAO and EPINIONS)are not perfectly knowna priori,when forming the groups.Conversely,these social values emerge and are consolidated in time,and are often unknown when a user (who could be even a newcomer) requests to join a group.Such social values can be evaluated only at a global level, by taking into account the opinions of all the users of the social community.In other words, theGkindex can only be used as a measure for thea posteriorievaluation of the effectiveness of a group formation algorithm,and not as key information for leading the formation itself.Indeed,each algorithm of group formation can be viewed as a heuristic method trying to produce, based on some information available into the community,a set of groups having a high value ofGkindex.

Thus,a specific choice forkrepresents a simple criterion to evaluate some group formation algorithms.In particular,the higher the value ofk,the higher the average evaluation for the group formation algorithms, because a high value ofkrepresents a bland requirement in terms of group composition.On the contrary,the lower the value ofk,the lower the average evaluation of the tested algorithms, because a small value ofkrepresents a strict requirement in terms of group composition.

In order to clarify this important concept,let us suppose to evaluate three algorithms for group formation(A,B,andC)with different behaviours.Let us suppose,for convenience,that we test the three algorithms in order to produce 5 groupsg1,g2,g3,g4,g5with specific requirements,and that we are able to measure the resulting social disadvantage in every group.The first algorithm,A,is able to form 5 groups with social disadvantagesD1=0.015,D2=0.011,D3=0.025,D4=0.11,D5=0.02;the second algorithm,B,is able to form 5 groups with social disadvantagesD1=0.23,D2=0.11,D3=0.025,D4=0.01,D5=0.018;finally,the third algorithm,C,is able to form 5 groups with social disadvantagesD1=0.3,D2=0.18,D3=0.12,D4=0.07,D5=0.09;The choice ofkof theGkindex plays an important role.Indeed,if we choose a valuek=10, then,we will haveG10(A)=4/5=80%,G10(B)=3/5=60%,G10(C)=2/5=40%. Nevertheless,if we choose a valuek=20, we will have

G20(A)=5/5=100%,G20(B)=4/5=80%,G20(C)=4/5=80%.Therefore,as expected, the higher the value ofk,the higher the average evaluation of the tested algorithm.

The introduction of theGkindex for evaluating the effectiveness of a group formation activity,from the viewpoint of the desired group composition, represents the first contribution we provide in this work.To the best of our knowledge,no other proposals have been previously presented in the literature to this purpose.However,we also highlight that this contribution is functional to support another goal of our research,that is related to the possibility of forming effective groups,as we will explain in Section II-C.

As already discussed,it is reasonable that the value ofkis chosen to be sufficiently small;therefore,in the experiments performed in this paper(relating to virtual communities of product reviewers)we will use theG10index,considering that a difference of 10 percent between the obtained configuration of a group and the desired one to be a “small enough”value.This choice strictly depends on the particular application domain and on the goals of the analyst.

B.Computing Information to Form Effective Groups

In the overall aforementioned scenario,we are interested in answering to the following research question:“Is it possible to form effective groups in virtual communities(where the effectiveness is determined by an objective measure,as discussed in Section II-A) by exploiting trust information in a simple way,similarly to real user communities?”

To answer this question,in this paper we propose to use a particular form of reputation,referred to aslocal reputation[6],using it instead of theglobal reputation.Specifically, the local reputation is based on opinions that come from the users’entourage,i.e.,1st level connections(friends),2nd level connections(friends of friends),and so on[7].This tends to be more reliable than using completely unreferenced recommendations.Therefore,similarly to real communities,when a user’s experience is insufficient to trust another user,the usual process will be to require an opinion from the user’s own network of friends.

A further level of connections should be taken into account when the number of user’s friends is insufficient to achieve a statistically significant number of recommendations(friends of friends and so on).But in this case we still need to decide how to weight their trustworthiness.

This approach has the additional advantage of fitting well with the distributed architecture that is often adopted by virtual communities,on which the local reputation is locally managed by each member by involving a generally very small number of members having a limited consumption of computational and communication resources.This(desirable)property cannot be satisfied when global information must be stored,accessed and processed by all the members of vast communities.

C. Forming Effective Groups

The problem of forming effective groups is based on the following premises,discussed in the previous sections:

1)a set of requirementsV={V1,V2,...,Vk} concerning the desired composition of the groups;

2)a given functionDV(g),to measure the social disadvantage of a groupgw.r.t.the given set of requirementV;

3)a functionGk(see Definition 2),along with a fixed value ofk,to evaluate the effectiveness of the group formation on the basis of the given functionD(V)g.

Therefore,given a set of algorithms for group formation, the“best” algorithm can be chosen as that maximizing the valueGk.

To this purpose,trust values must be appropriately combined and evaluated within each community[8]in order to assume the best decision as possible about potential new comers.Sometimes, trust information may be available in a binary form, by which it is possible to represent only a full trust or distrust,and a fine grain evaluation is impossible to have.Then some kind of aggregation of the individual expressions of trust about a target (e.g., by adding their values,by using a function or by exploiting a linear system[9])is adopted in order to achieve a synthetic value which is suitable for making a decision.However,all these modalities deeply differ from the processes that typically take place in human societies whereby decisions are based on some form of voting mechanism.This is one of the most important forms of social choice,allowing the community members to manifest their individual preferences.

In particular,the voting mechanism is largely used in the context of coordination activities,auctions, negotiation and also team formation[10].However,while voting comes with all the advantages deriving from democratic processes,it also presents manipulation risks.These are intrinsic in the voting itself,for instance due to strategic voting[11].Therefore,a great attention is commonly paid to adopting a voting strategy that is both resilient to manipulation and correct(in terms of outcomes).Specifically,with respect to our research question,we consider the first issue as an orthogonal problem,which will therefore not be examined in this paper.On the contrary,the second issue is more interesting for us because our goal is to form groups in a simple way and in accordance to the adopted group formation strategy.

The analysis above lead us to propose a strategy to form groups in virtual communities based on a combination of trust(obtained as a combination of reliability and local reputation)and a suitablevotegiven by every member of the group itself.In turn,this is based on the local trust of the user w.r.t.the requester.

III.Local And Global Trust,Similarity

Let us denote the user community asUand a relationship taking place therein by using a directed unlabeled graphG=?N,A?, whereNis a set of nodes(n∈Nrepresents the userun∈U)andAis a set of arcs, wherea∈Ais a pair (i,j)representing a trust relationship among the usersuianduj.From this point,we will denote either a noden∈Nor a userun∈Uto represent the same entity.

In the following we provide a few preliminary definitions.To this end, the main symbols used in this paper are grouped in Table I.

A.Trust

Thetrustrelationship between users is defined as a relation τ?:U×U→[0,1], where 0 (resp., 1) represents the minimum(resp.,maximum)level of trust.In our previous research[12],these two different trust measures were combined to obtain a final trust measure between two users.Thereliabilityρn,kis a measure of direct trust thatnhas inkbased on his/her direct past experiences occurred withk.Theglobal reputationωkrepresents the global measure of trust that the whole community perceives about a nodek∈N.The global reputation ωkis simply obtained by averaging all the reliability values ρx,k, for eachx∈N.Therefore,each noden∈Nwill derive a synthetic measure of the trust about the other nodekby integrating reliability and global reputation by assigning to them proper weights.Global trust τ?n,kis then defined as 0.5×0+(1?0.5)×1×0.625=0.31.If we giveTg=0.5,awill vote YES to the admission ofb(i.e.,va,b=1)while will vote NO for the admission ofd(i.e.,va,d=0).

IV.The Distributed Procedure for Group Formation

Here we describe the simple distributed algorithm(GF,for Group Formation)which is used for the experiments presented in Section V,where the main symbols used in the algorithms are resumed in Table I.The algorithm includes various selection criteria for group formation(e.g.,voting vs compactness),and it has been used to address the research question outlined in Section I.It can be assumed that the algorithms are executed by software agents that operate on behalf of their users,without loss of generality.Therefore,in the following we will denote agents and users interchangeably.The algorithm is composed by two parts.The former is designed to be executed on the user-side,while the latter will be executed by theadministratorof the group to decide whether to admit the user into the group.

Moreover, the procedure executed by the administrator may rely on different mechanisms and measures to drive the user admission decision.This leads to two different versions of theGFalgorithm,as we detail later in this section:the former takes into account only the compactness measure in order to decide whether to admit a user into a group,and it is dubbedU2G.In particular,U2Ghas been already used in our previous work, where we defined the compactness measure.The latter version is dubbedTV,as it relies on the voting mechanism and the computation of the local trust(as described in Sections III-E and III-D).We observe that,since any node can join more than one group,groups may overlap.Moreover,there is no restriction in theGFprocedure executed by the administrator on group overlapping.

A.The GF Procedure Performed by the User Agents

TheGFprocedure performed by the user agents is represented by the pseudocode listed in Algorithm 1,wherebyXnis the set of the groups to which the nodenis affiliated to,andNMAXis a parameter representing the maximum number of groups that a node is capable to analyze.It is assumed thatNMAX≥|Xn|.Furthermore,we suppose that the generic useranstores into a cache the group profile of each groupgjcontacted in the past and the time elapseddjfrom the last execution of theGFprocedure for that group.Finally,let ξnbe a timestamp threshold and χn∈[0,1]be a threshold fixed by the noden.The ratio behind the procedure executed by nodenis represented by his attempt to improve the overall social advantages of joining a specific set of group.For this aim,first of all,the values of compactness η(Section III-B)are recalculated if they are older than the fixed threshold ξi(lines 1–4).Then,candidate groups are sorted in a decreasing order with respect to the compactness η.

The loop in lines7–17 represents the core of the procedure,on which a number ofNMAXgroups are selected.If some groups in the setLgoodare not in the setXn, then nodencan potentially improve the overall compactness by joining with those groups.The only constraint of the algorithm is the maximum number of groups that the user can join.In the Algorithm 1, parametermis useful to count the number of new groups the user agent can join.As a consequence,the agent will leave the same number of groups which are in the setXibut not in the setLgood.

B.The GF Procedure Performed by the Group Agent

TheGFprocedure performed by the group agent is represented by the pseudocode in Algorithm 2.LetKjbe the set of nodes affiliated to groupgj, where ||Kj||≤KMAX, beingKMAXthe maximum number of users allowed to be within groupgj.Suppose that the group administratorAjstores into its cache the profilePiof each user nodeiand the timestampdiof its retrieval.Moreover,let ωjbe a time threshold fixed by agentAj.The procedure performed by the group agentAjis triggered whenever a join request by the user agentn(along with its profilePn) is received byAj.ParameterMcan assume two values,TVorU2G.Before of discussing the algorithm in detail,we remark that parameterMrepresents a simple setting of the group administrator in order to switch to theTValgorithm – which relies on the computation of the local trust – or to theU2Galgorithm – which relies on the computation of the compactness which,in turns,includes the computation of the global trust.The difference between theU2GandTVis very simple,although relevant.TheU2Galgorithm tries to maximize the compactness of the member of the group;instead theTValgorithm relies on the vote of every group component – which relies,in turn,to the evaluation of the local trust – in order to decide whether to admit the new member into the group.

By lines1–5 the group agent asks the updated profile of the components of the group itself.By line6 of the algorithm,all the users of groupgjare asked to express a preference(i.e.,a vote)about the possible joining of usernin groupgjonly if the parameterMis set toTV.This represent theTVvariant of algorithmGF, which, for brevity, we refer to asTVin Section V.Here we use the functionV(·)as defined in Section III-D.

From line7 of the algorithm,there are several different options, which are listed below,along with the correspondent lines of code:

1) the users of the group did not accept usern(i.e., the voting has given a negative result);in this case the procedure will end andnwill not join groupgj(line7);

2) the number of users in the group plusnis not larger thanKMAX; then usernwill join the group(lines8–10);

V.Experiments

In this section we discuss a number of experimental results obtained by comparing the proposedTVapproach with the pastU2Gapproach,on two different datasets5extracted from the social networks CIAO and EPINIONS.Both these datasets have been craw led by some researchers in order to carry out the study described in[15].They are widely used to investigate on trust evaluation and trust-based recommendations because they store information on i)user trust relationships and ii)user-item ratings.In particular,EPINIONS and CIAO users review items,assign them numeric ratings and can also build their own trust network by adding the people whose reviews they think are valuable.Moreover,in EPINIONS and CIAO datasets timestamps inform about when the reviews have been published.Data extracted from EPINIONS and CIAO represent interactions of the users in the whole community,i.e., they are not aware of belonging to a particular sub-community or group.This aspect is quite useful for our research.Indeed, users interact with each other(i.e.,they produce and rate reviews)without any influence or constraint related to the communities to which they belong,which is important to test algorithms for group formation.

EPINIONS and CIAO dataset store data of 22166and 12375users, respectively.Both datasets consist of a pair of matrices(EM,T M).In the specific case,rows ofEMhave the form of {userID,productID,categoryID,rating,helpfulness,timestamp}.More in detail,categoryIDrepresents the commercial product category identified byproductIDwhich received the rating by the user identified byuserID,andhelpfulnessis the level of satisfaction of the other user for thatrating(the latter –timestamp– is unused in our experiments).In particular,the helpfulness can assume values between 0 and 5.The matrixTMis instead composed by the numbers representing the trust relations between the different users(the“trust matrix”).This matrix is used to compute the local as well as the global reputation.

A. Experimental Settings and Software

In our experiments we have considered helpfulness to be reflecting a social value.The goal of our activity of group formation is to obtain several different group configurations in terms of distribution of social values.We categorized the users of the communities into three classes,C1,C2,andC3:C1as the class ofbad users,having helpfulnessh≤2;classC2is that of themedium users,having 23.Then, we tested three different configurations,as follows:

1)S1:the ratio of users in each of the three classes arep1=p2=p3=0.33,i.e.,the users of each class areequally distributed into the groups;

2)S2:the ratio of users in each of the three classes arep1=0.1,p2=0.3,p3=0.6,i.e.,groups should havemany good users,a few medium users,and a very low percentage of bad users;

3)S3:the ratio of users in each of the three classes arep1=p2=0,p3=1,i.e.,groups should be formed byonly good users.

Let us remind that we defined theGkindex associated with a set of groups in a virtual community as the percentage of the groups having a social disadvantage less than or equal tok/100.Therefore,we show the results only in terms of impact on theGkindex,as theGkindex is directly dependent on the values of social advantage.

We setk=10,thus we compare,in term of theG10index,theTVandU2Galgorithms for different values of α,Nmax,andKmax.We highlight the following important issues:

1) In our experiments,we have used the versionU2G-comp of our algorithm,instead ofU2G-diff that does not take into account the trust component of the compactness,giving importance only to the similarity between users’profiles.In our previous research[16],we have already comparedU2Gcomp andU2G-diff,showing that the performances of the first method is always better than the second one,and thus highlighting that the use of trust is essential to obtain significant improvements of the group compactness.

2) We have reported the results corresponding toGkonly fork=10,since this value ofkrepresents a very strict requirement in terms of group composition(corresponding to obtain a social disadvantage less than or equal to 10%).We have verified by an exhaustive campaign of experiments that the results for values ofkgreater than 10 are always favourable for our approach(with and advantage that is increasing withk)with respect toU2G,while values smaller than 10 represents too strict requirements that are not practically significant.

Note that all the settings used for the involved parameters must be considered as examples of possible realistic configurations.More specifically:

1)Fig.3 shows the results obtained by applyingTVandU2Gin the configurationS1to EPINIONS,for different values of α ,fixedNmax=10andKmax=100.We note thatTValways outperformsU2Gwith an advantage in term ofG10ranging from a minimum of 11% to a maximum of 23% .An analogous result has been obtained on the dataset CIAO (Fig.4)where the advantage ofTVvsU2Granges from a minimum of 13%to a maximum of 20%.

Fig.3.TV vs U2G-comp on EPINIONS for configuration S 1 (p1=p2= p3=0.33 )with N max=10and K max=100.

2)Fig.5 shows the comparison betweenTVandU2Gon EPINIONS for different values ofNmax,fixed α=0.5 andKmax=100.We see that also with respect to this dimension of the analysis,TVis better thanU2Gby about 16 %.

3)Finally,Fig.6 presents the comparisonTVvsU2Gon EPINIONS for different values ofKmax,fixed α=0.5andNmax=10.Also in this situation, we remark thatTVperforms better thanU2Gby about 16%.

Fig.4.TV vs U2G-comp on CIAO for configuration S 1 (p1=p2=p3=0.33 )with N max=10and K max=100.

Fig.5.TV vs U2G-comp on EPINIONS for configuration S 1 (p1=p2=p3=0.33) with K max=100and α =0.5.

We repeated the experiments B and C also on CIAO by obtaining an advantage of about 14%and 15%,respectively.The experiments show also that values of α higher than 0.3 lead to a reduction ofG10(Figs.3 and 4).This underlines that,in a group scenario,reliability should be considered as less important than reputation.

The influence of the values of bothNmaxandKmaxonG10is modest(Figs.5 and 6),although little improvements are obtained for high values of both parameters;that is a statistical consequence of having set fewer constraints in the group formation algorithms.In any cases,TVshows significantly better results thanU2G,highlighting the importance of using the notion of local reputation in the mechanism of voting the acceptance of a new comer in the group.

Fig.7.TV vs U2G-comp on EPINIONS for configuration S 2 ( p1=0.1, p2=0.3 , p3=0.6) with N max=10and K max=100.

Fig.8.TV vs U2G-comp on EPINIONS for configuration S 3 ( p1=p2=0,p3=1) with N max=10 and K max=100.

A further confirmation on the advantage introduced byTVwith respect toU2Gcomes from the experiments on the configurationsS2andS3,for which we report in Figs.7 and 8 the values ofG10,for different values of α on EPINIONS.We see that the performances of both algorithms(TVandU2G)decreases with respect to the configurationS1, which highlights the increased difficulty in obtaining the desired configurations with respect to the case of equipartition of the classes.However,also in both these situations,TVperforms better thanU2G,with advantages ranging in 12–25 %(on theS1configuration)and 10–30 %(inS2).Similar results have been found on the CIAO dataset.Also the results achieved by varyingNmaxandKmax(not reported due to space limitations)completely confirm the trend shown in the analogous results obtained for theS1configuration.

VI.Related Work

To form groups within social communities,a large number of proposals in the literature exploit amatchingapproach between user’s requirements and group’s characteristics.These similarity measures are derived from personal profiles which are built by the users’ behaviors[17],[18].

A “similarity”metric can be considered as the most natural way to measure how much the group members are close to each other based on specific interests.However,the similarity criterion will neither ensure that group components will actually be engaged in the group interactions nor guarantee a minimum level of quality for such interactions. Nevertheless,recent studies[19]report that the level of mutual trust is tightly related to both the number and the quality of members’interactions(which can even occur through different channels[20]),as well as to the formation of thematic groups[1],[21].Therefore,we can argue that the larger is the level of reciprocal trust among members,the larger their interest in engaging in mutual interactions [22],[23].

To solve this later issue,and for improving the group effectiveness,a common solution chooses to refine the group formation processes by combining similarity and trust measures.As an example,in[12]similarity and trust measures are combined to represent both the individual and the global satisfaction,as respectively perceived by a user and by all the members of a group of a virtual community.However,the computation of similarity measures in large communities could imply the need to explore the whole member space[24],[25].This may become impracticable,and the matching may not be reliable due to a lack of information,or due to imprecise or fraudulent data [26].

Trust approaches have been widely used in several different fields,as vehicular social network,social media transportation,and cloud computing[27]–[30].In the specific case of communities,recent contributions in the group formation area give relevance only to trust measures[31].In particular,a complete and useful representation of trust within a given community through direct knowledge(referred to as reliability), would require community users to directly interact with each other.Yet, the usual approach is to exploit also the information deriving by other members of the community,referred to as reputation.

In computing reputation,an approach largely used is to gather the recommendations provided byallthe members of the community, which is known asglobal reputation[32],[33].Also,in this case a large number of members would make it difficult to compute this global information about the users.In fact,in similar contexts unreliable recommendations may lead to misleading estimations in trustworthiness,particularly for the unknown community members.This is often due to malicious behaviours aimed at gaining undeserved benefits[13].Therefore,reliable reputation measures require to evaluate the trustworthiness of the recommenders.To address this critical issue,researchers have developed complex,sophisticated and also computationally expensive techniques,often involving significant communication overloads[9].Thus,forming groups within virtual communities on the basis of a trust criterion bears the risk to realize processes dissimilar and more complex than those implemented in real user communities.

An interesting problem related to our work is that of team performance modeling and prediction,in order to drive team formation and to maximize the performance of the team itself.In[34],the authors analyze the problem team performance prediction and modeling and propose a novel way to model and predict the performance of a team/group.The model is named “E-CARGO”and includes a few algorithms which have been verified by a case study to demonstrate the practicability of the proposed method.Role assignment is a critical task in role-based collaboration.

The authors of [35]have performed a study related to group role assignment problem(GRAP).Moreover,they described a general assignment problem(GAP),converts a GRAP to a GAP and,finally,they proposed an efficient algorithm based on the Kuhn-Munkres(K-M)algorithm along with numerical experiments.From the analysis of the results the authors show that the proposed algorithm significantly improves the algorithm based on exhaustive search.In particular,the authors has contributed to expand the application scope of the K-M algorithm, by offering an efficient solution based on the K-M algorithm.

In this scenario,another main question is how to aggregate such trust information to form groups in a simple way.To this aim,voting is one of the most popular techniques,both in real and virtual communities,to aggregate individual preferences[36] by giving equal decisional weight to everyone,specifically when a common members’decision has to be made in face of different alternatives[37].Voting outcome is a mediation among different members’opinions and interests and,for this reason,it is effective when conflicts must be reduced[38],as well as when the social utility has to be maximized [39].

In the literature,different voting procedures have been designed by adopting either a global or a local approach.In the presence of very large communities,global procedures are inefficient or unfeasible(high computational complexity,absence of stable communications,and so on);local voting procedures– i.e.,decomposing the vote in more local votes and then gathering them together – generally represents a better choice [40].

Another aspect is represented by the possible attempt of manipulating the voting result.The literature includes several techniques useful to manipulate the outcome by strategic voting[41],[42].For example,selfish behaviors can address one or more community members to release a vote which is not in accordance with their true preferences but,in an egocentric vision,is aimed at obtaining as many individual benefits as possible in that specific scenario[43],[44].In particular,software agent societies are more exposed to voting manipulations than human societies because agents decide their vote based on coded algorithms and can easily explore a wide range of manipulation opportunities[45].Therefore, the challenge of designing voting mechanisms that show robustness is addressed in several works[46],[47].

However,the issue above can be considered orthogonal with respect to the focus of our proposal.In a very similar view,trust can assist voting mechanisms in virtual communities.Trust is a major asset of both human and virtual societies which arise from the inability of a(real or virtual)entity to suitably monitor or control its environment and relationships.Given its relevance and multidisciplinarity,trust is largely studied in many disciplines under different perspectives(e.g.,sociology[48],economics[49],computer science[50],and so on).Sociologically, trust can be assumed as the expectation that one or more entities have about the fulfillment of one or more events or behaviors[51],[52].In other words, trust is a beta trustor places on a trustee about a future event[53]in order to receive either an individual or a collective benefit [54].

Conceptually,a vote is not dissimilar from trust, because voters place their own expectations on some other actor(or in a future event)similarly to a trustee.Indeed, based on cognitive and emotional dimensions,voters expect to receive some form of benefit arising from their vote.Benefits may be individual, when the voters are driven by selfish targets,or social,for instance when they aim at improving the social capital of a group[12].On the contrary,voting and trust hold different properties and adopt different models among them.

As stated before,approaches relying on local trustand local voting are preferred to realize reliable relationships and quick decisions in all those contexts denoted by a great population,mobility,lack in infrastructure and/or communications,as well as in presence of limited computational and/or storage capabilities.To this regard,a trust-based voting strategy is described in[55],where a local voting mechanism is applied in a mobile wireless network context for establishing whether a node should be included in a transmission path.The evaluation is based on trustworthiness,as it is perceived by the other nodes.The theory of semi-rings is used in[56]to model trust in Ad-Hoc networks by a graph where links represent trust relationships.Users form their trust opinions about the other nodes by also using second-hand information,even though this information is weighted differently from that derived by direct experiences.By using a modified Mohri [57]iterative algorithm, the trustworthy nodes are identified on the basis of a voting process performed only by those nodes that have a trust value higher than a suitable threshold.Even though this algorithm currently implements a global approach,it could be easily converted in a local strategy.The authors of[58]discuss a group affiliation procedure where any groupjoining request is evaluated by means of a democratic group voting mechanism.In particular,each vote is driven by trust because each group member evaluates if the requirements for joining the group are satisfied by means of a local trustengine.

VII.Discussion and Conclusions

Group formation is a key issue in social communities,due to the importance of establishing an effective organization in which users perform actions that could benefit from collaboration and mutual social interactions.In this context,the necessity of determining the levels of trustworthiness between users naturally arises as well as the possibility of associating a reputation to each user.From this viewpoint,the question arises about which possible definition of effectiveness for a group should be adopted.In fact,the desired ideal configuration of the groups is not necessarily the one composed only by the highly reputable users.Depending on the context, the possibility could arise to have groups whose composition involves also bad and medium reputable users,which are themselves members of the network and,thus, have a social value and bring their own expectations.

Although an overwhelming amount of proposals exist in the literature about the problem of trust-base group formation,to the best of our knowledge nobody has yet proposed an objective metric for measuring the effectiveness of the groups,specifically from the viewpoint of their desired composition.In this paper,we propose to use a novel measure,dubbedGkindex,to face this issue in a natural and objective way.Starting from the goal of improving the effectiveness of the group formation activity in terms ofGkindex,we then proposed,as the core contribution of the paper,a strategy to form groups in virtual communities based on a weighted voting mechanism, whereby each vote is represented by a trust value obtained by a suitable combination of reliability and local reputation.This latter is a form of reputation that is based on opinions only coming from the entourage of the user(i.e.,friends,friends of friends,and so on)that appears as more reliable than using completely unreferenced recommendations.

Therefore,similarly to real communities,when the user’s experience is inadequate to trust another user, the usual process is to require an opinion to his/her network of friends.We have implemented this strategy by theTValgorithm,an evolution of theU2Galgorithm,which uses the local reputation instead of the global one and integrates a voting mechanism.Experiments performed on the real social networks CIAO and EPINIONS show that our proposed strategy significantly improves the results obtained byU2Gin terms ofGkindex.While the presented experiments are limited to the presence of three classes of users,our ongoing research is now devoted to studying the behavior ofTVin the presence of even more complex configurations of the groups,in cases in which many different classes of users exist.