- The formation and evolution of interest groups in Online Social Networks is driven by both the users' preferences and the choices of the groups' administrators. In this context, the notion of homogeneity of a social group is crucial: it accounts for determining the mutual similarity among the members of a group and it's often regarded as fundamental to determine the satisfaction of group members. In this paper we propose a group homogeneity measure that takes into account behavioral information of users, and an algorithm to optimize such a measure in a social network scenario by matching users and groups profiles. We provide an advantageous formulation of such framework by means of a fully-distributed multi-agent system. Experiments on simulated social network data clearly highlight the performance improvement brought by our approach.
and Twitter have become very complex realities [
Recent studies investigated the relationships between users
and groups in OSNs [
Although the concept of social profile is known in the
context of virtual communities [
Commonly, a group might be considered (i) as a set of nodes
(i.e., users) more densely connected among each other than
to the others (i.e., the group formation is viewed as a graph
clustering problem [
Satisfaction, on the other hand, is often related to the notion
of group homogeneity: when the similarity/inter-connectivity
among group participants is high, according to both structural
and semantic dimensions, a OSN group is regards as
homogeneous and this yields better satisfaction among its users [
However, if we assume that homogeneity should reflect users
satisfaction, we argue that other behavioral characteristics
of members and groups should be considered as important
components [
In this paper, we define a novel measure of group homogeneity that exploits users similarity and the other users’ features cited above. By means of our new definition we are able to provide an algorithm to match the individual users’ profiles with group profiles. The goal of this method is to find the matching between users and groups capable of improving the homogeneity of the social groups. More in detail: • We introduce the notion of group profile in the context of
OSNs considering a set of categories of interests,
common rules, behaviors, communication styles and facilities
for sharing media content. This definition of group profile
is coherent with the definition of a user profile containing
information comparable with those of a group profile.
• Each OSN group is associated with a group agent [
II. THE REFERENCE SCENARIO information stored in its profile. In particular, every time u In our scenario, we consider an OSN, the set of its users, deals with a category c, the associated value Iu(c) is updated and the set of its groups, denoted by S, U and G, respectively. as the weighted mean between its previous value and the new In S, each group of users g ∈ G represents a subset of U (i.e, contribution to Iu(c) = · Iu(c) + (1 − ) · . In detail, sgu⊆ch Utha∀tg: (∈i) Gea)c.hAumseurltui-aisgesnutppsyosrtteemd biys ahsesropcieartseodnawl iathgeSnt, tahnedincarreemreenatl tvoagluivees taorbtihterauri’lsy isnetetrbeyst uininc d[0u.e.1t]o, whehrearectionis, au in the activities of participation to groups; and, (ii) each while weights the two components of Iu(c). Similarly, every group g is supported by an administrator agent ag managing time the Iu(c) value of any user u ∈ g changes, the Ig(c) value all the received requests to join with the group. of a group g is updated by the agent ag as the mean of all the Iu(c) values ∀c ∈ g. For each action performed by the user u (e.g. publishing a post, etc.) its agent au sets the appropriate A. The agents knowledge boolean values of the variables in Bu. Analogously, the agent
To represent the knowledge that each agent au (resp., ag) ag updates the variables contained in Bg every time the has about the orientations of its user u (resp., group g), a administrator of g changes the associated rules. Besides, when profile pu (resp., pg) is associated with it. This profile stores u (resp., the administrator of g) modifies her preferences about preference and behavioral information referred to the user the access mode, the associated agent updates Au (resp., Ag). u (resp., the users of g) in four section (called interests, Also, when u (resp., a user of g) modifies her friends list, the access preference, behaviors and friends) storing data on associated agent updates Fu (resp., Fg). Note that ag computes topics of interest, mode to access groups, ways of performing Fg as the union of the sets Fu of all the users of g. activities and friends, respectively. The profile of a user u Periodically, the agent au (resp., ag) executes the user (resp., (resp., a group g) is represented by a 4-tuple ⟨Iu; Au; Bu; Fu⟩ group) agent task described above, to contribute to the group (resp., ⟨Ig; Ag; Bg; Fg⟩), where each component describes the matching activity of the OSN. properties of u (resp., g). To perform the above tasks, the agents can reciprocally
Let C be the set of all categories considered in the OSN, interact, send and receive messages thanks to a Directory where each element c ∈ C is an identifier representing a Facilitator agent (DF), associated with the OSN, that provides given category (e.g. music, sport, etc.). Each OSN user u a indexing service. The DF stores the names of each user and (resp., group g) deals with some categories belonging to C group belonging to the OSN and those of their agents. Note where Iu (resp., Ig) denotes a mapping that, for each category that the DF is the only centralized component in the proposed c ∈ C, returns a real value Iu(c) (resp., Ig(c)), ranging in scenario, while the the GHM matching algorithm is completely [0::1]. This represents the level of interest of the user u (resp., distributed on the whole agent network. the users of the group g) with respect to discussions and multimedia content dealing with c. The values of this mapping are computed based on the actual behavior of u (resp., of the C. Definition of homogeneity users of g) — see Section II-B for the details. In order to represent the potential attitude of the user u to
The access mode property represents the policy regulating stay in the same group with the user v (resp., to stay in the the access to a group (described by an identifier, e.g. open, group g), we define the homogeneity between two users u and closed, secret, etc.) preferred by u (set by the administrator of v (resp., a user u and a group g) as a measure representing the group g) and denoted by Au (resp., Ag). how much u and v (resp., u and g) are similar (or, different)
The property Bu represents the types of behavior adopted with respect to the properties I, A, B and F . (resp., required) by u in her OSN activities, for instance The homogeneity hu;v between the users’ profiles of u and “publishing posts shorter than 500 characters”. Let b ∈ B v is defined as a weighted mean of the contributions cI , cA, a behavior adoptable by user u (admitted in the group g) cB and cF , associated with the properties I, A, B and F , and described by a boolean variable set to true if b is measuring how much the values of each property in pu and adopted (resp., tolerated) or f alse otherwise and let B be pv are similar. To this purpose: the set of possible behaviors associated with the OSN (e.g., B = {b1; b2; · · · ; bn}). Therefore, let Bu (resp., Bg) be a mapping that, for each b ∈ B, returns a boolean value Bu(b) (resp., Bg(b)), where Bu(bi) = true means that such behavior is adopted by u (resp., tolerated in g).
The property Fu (resp., Fg) represents the set of all users that are friends of u (resp., that at least have a friend among the members belonging to the group g). • cI is the average of the differences (in the absolute value) of the interests values of u and v for all the categories present in the social network, that is cI = ∑c∈C |Iu(c) − Iv(c)|=|C|. • cA is set to 0 or 1 if Au is equal or not equal to Av. • cB is the average of all the differences between the boolean variables stored in Bu and Bv, where this difference is set to 0 or 1 if the two corresponding variables are equal or different. • cF is computed as the percentage of common friends of u and v, with respect to the total number of friends of u or v as cF = |Fu ∩ Fv|=|Fu ∪ Fv|. Note that, to make them comparable, the contributions are normalized in [0::1].
The agent au (resp., ag) automatically updates the profile pu (resp., pg) of its user u (resp., group g) after that u (resp., a user affiliated to g) performs an action involving an ag1 group 1
ag2 u,g1 group 2 ag3 group 3 u,g2 u,g3 u au g,u Similarly, homogeneity hu;g between a user u and a group g is simply computed as hu;v substituting user v with group g.
periodically executed by each user agent au (resp., group agent ag), where we call epoch every time the task is executed and T the (constant) period between two consecutive epochs.
A. The user agent task • For each user u ∈ K such that dateu > (i.e., a fixed threshold), it sends a message to the agent au to require the profile pu associated with u (cf Action 1, of Fig. 2). • When ag receives the required users’ profiles (cf. Action 2, Fig. 2), it computes the homogeneity measure hg;u between the profile of each user u ∈ K ∪ r
{ } and the profile of the group g (cf. Action 3, Fig. 2). • The user u having the highest homogeneity values such that hg;u > , where is a real value ranging in [0::1], is inserted by ag in the set of good candidates, named GOOD, to join with (up to a maximum of kMAX users).
If u ∈ GOOD, ag accepts its request to join with g (cf.
Action 4, Fig. 2). Moreover, if u ∈ K but u ̸∈ GOOD, ag deletes u from g.
Let X be the set of the n groups u is affiliated to, where n ≤ nMAX and nMAX is the maximum number of groups a user can join with. We suppose that au stores into a cache IV. EVALUATION the profile pg of each group g ∈ X, contacted in the past, We evaluate the effectiveness of the GHM algorithm in with the date dateg of its acquisition. Let m be the number increasing the homogeneity of the groups of an OSN by using of group agents that at each epoch is contacted by au. In such a simulator, called GHM-Sim, capable of modeling all the a context, au behaves as follows (see Figure 1): required users and groups activities. The experiments involve • From the DF repository, au randomly selects a set Y of a simulated OSN having 30.000 users and 100 groups, ad hoc m groups so that X ∩ Y = {0} and let Z = X ∪ Y the generated by GHM-Sim, each one provided with a profile, set consisting of all the groups present in X or in Y . having the structure described in Section II. More in detail, • For each group g ∈ Y ∩ X such that dateg > (i.e., the profile pu of a user u is generated as follows: a fixed threshold), u sends a message to the agent ag to ask the profile pg associated with g (cf. Action 1, Fig. 2). • For each received pg (cf. Action 2, Fig. 1), u computes the homogeneity measure hu;g between her profile and that of the group g (cf. Action 3, Fig. 1). • The groups belonging to Z and having the highest homogeneity values such that hu;g > , where is a real value ranging in [0::1], are inserted by au in the set of good candidates, named GOOD, to join with (up to a maximum of nMAX groups). For each group g ∈ GOOD if g ̸∈ X, au sends a join request and the profile pu of u to ag (cf. Action 4, Fig. 1). Otherwise, if g ∈ X but g ̸∈ GOOD, then au deletes u from g.
• The values of Iu(c) are randomly chosen from a uniform
distribution in the interval [0::1]; • Au is assigned the value open (resp., closed and secret ) with a probability of 0.7 (resp., 0.2, 0.1) to implement the variability of OSNs group access restrictions; • Bu contains the values, randomly generated, of six boolean variables representing in average the user’s attitude to: (i) publish more than 1 post per day; (ii) publish posts longer than 200 characters; (iii) comment at least two posts of other users per day; (iv) respond to comments associated with her posts; (v) leave at least 2 “Like” rates per day; (vi) respond to the messages. • The set of friends Fu are randomly generated choosing in the set of the users.
Let K be the set of the k users affiliated to the group g, where k ≤ kMAX , being kMAX the maximum number of members allowed by the administrator of g. Suppose that ag stores into its cache the profiles of the users u ∈ K obtained in the past along with the date dateu of their acquisition. When ag receives a join request by a user agent u (along with u’s profile pu), it behaves as follows (see Fig. 2):
most 15 of the available groups. The properties Ig, Ag, Bg and Fg of the profile pg of each group g are randomly generated. The values of the parameters introduced in Section III are shown in Table I. We also limit to: (i) 250 the users who can join a given group; (ii) 15 the groups that a user can be joined with; (iii) 5 the maximum number of requests that a user can send in each epoch to new groups. 0,0000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
epoch
the average homogeneity AHg, derived by [
M AH DAH = = ∑g∈G AHg
|G| √ ∑g∈G(AHg − M AH)2 |G| (2) (3) In the simulations, the initial values for the above measures were M AH = 0:266 and DAH = 0:0011, denoting a very low homogeneity, due to the random generation. Applying the GHM algorithm we have simulated 15 epochs of execution per user. We can observe that the GHM algorithm quickly converges after few iterations (see Figure 3). The experimental results show that the GHM algorithm increases the homogeneity in OSN groups of about 14 percent on average, with respect to a random assignment of users to groups, achieving a stable configuration (e.g., M AH = 0:320 and DAH = 0:0052) after about 10 epochs. It is reasonable to suppose that the GHM algorithm, when applied to real OSNs, should lead to concrete benefits in terms of homogeneity.
achieved in the fields covered by this paper, illustrating the main novelties brought in by our approach.
In the latest years, an increasing number of authors focused
on the problem of recommending items to the member of a
group [
More formally, let U , I and G ⊆ U be the user population, a collection of items and a group of users, respectively. Suppose that a rating function r : U × I → R is available, where R (rating space) is a discrete set. The function r receives a user ui ∈ U and an item ik ∈ I as input and returns an element rik ∈ R as output. Building the profile of G is equivalent to compute a function fG : I → R receiving an item ik as input and returns how much the members of G are satisfied by ik.
To compute fG( ) two popular strategies are: (i) Average [
In the Average strategy the score of an item ik depends on how many users in G liked it and, if fG(ik) is large, ik could be recommended also to whom in G dislikes it. Otherwise, with Least Misery the opinion of who liked the less ik has the biggest weight in computing fG(ik) to minimize the chance that ik is recommended to someone in G who dislikes it.
For example, if all of the group members but one like ik and the Least Misery strategy is applied, ik will automatically get a low score although almost all users in G are interested in it. Differently, in the Average strategy few low ratings on ik are largely compensated by the ratings of other users.
Besides, most approaches assume that user’s preferences are independent of users joining (or not) with a group: if a user alone likes (or dislikes) an item, she will continue liking (or disliking) it if she decides to join a group.
In the literature there are few papers dealing with the
matching of a user and a group profile. Most of this work
has been designed to recommend to an OSN user groups to
join with (such a problem is also called affiliation
recommendation in [
Spertus et al. [
Vasuki et al. [
Summarizing the benefits provided by our approach are: (i) to models user interests, behaviors, friendship relationships and the policies for accessing groups; (ii) to manage both group and user profiles by means of a multi-agent architecture where agents provide all the required affiliation activities; (iii) to provide a distributed greedy algorithm to match users and groups that computes, at each stage, how good a group is for a given user and selects, uniformly at random, some of these groups; (iv) to manage large networks with a large number of groups in a flexible and computationally feasible manner.
VI. CONCLUSIONS
The problem of dynamically increasing the intra-group homogeneity is emerging as a key issue in the OSN research field. The introduction of high-structured user profiles, the large dimensions of current OSNs and the increasing number of groups require to face efficiency and scalability issues. In this paper, we presented the Group Homogeneity Maximization algorithm that allows a set of software agents, associated with the OSN user profiles, to dynamically and autonomously manage the evolution of the groups, detecting for each user the best groups to join with based on the measures of homogeneity. The agents associated with the group administrators accept only those users having a profile compatible with that of the group. Our experiments on simulated social network data clearly show that the execution of the matching algorithm increases the internal homogeneity of the groups composing the social network, bringing about 15% of improvement with respect to the baseline.
In order to obtain more accurate results, in our ongoing research we are considering to combine the homogeneity measure with a new measure taking into account the trustworthiness of the users. Indeed, in virtual communities, interacting users reciprocally measure the trustworthiness of their counterparts to decide if these are reliable interlocutors or not. To this aim, we are planning a specific experimental session on real OSN data to evaluate our approaches.