The GroupFinder framework addresses the new problem of recommending the best group of friends with whom to enjoy a given item, e.g., a travel destination or a movie. Given a user, her social network and a recommended item that is relevant for the user, our novel recommendation task tries to maximize: i) the relevance of the recommended item for every member of the group, and ii) the intra-group social relationships. This extended abstract shortly summarize the work in [4]: we introduce the User-Item Group Formation problem, the possible solutions and the recommendation framework that organizes them. We experiment the proposed solutions using four publicly available Location Based Social Network datasets con rming the e ectiveness and the feasibility of the proposed solutions.
Our work starts from the simple observation that some human activities are
better enjoyed with travel companions. This shifts the problem from recommending
a single item to a single user (as in the traditional cases) to a new paradigm
of recommendation that takes into account items and groups of users. Given a
user and a recommended item, we want thus to deal with the novel problem of
suggesting the \best" group of friends with whom to enjoy the recommended
item. Consider for example a user who has been recommended to visit Paris:
we want to be able to suggest the travel companions who can join her in
visiting Paris. Such group should ideally have interest in visiting Paris and also
be friend each other to facilitate the staying together. Thus we need to balance
the strength of the group internal friendship with the group members interest in
travelling to Paris. Considering this last scenario, we design a recommendation
technique suggesting the \best" group of k friends for a pair < user; item >
taking into account both the social relations and the preferences of the user and
the group. Since this approach focuses on the formation of the group based on an
item and a user, we refer to it as User-Item Group Formation problem (UI-GF
or simply group formation). We present two algorithms as possible solutions to
this problem and the global recommendation framework that incorporates them.
The full version of this paper has been published in [
The User-Item Group Formation problem and the
GroupFinder Framework
Let U be a set of users and I a set of items, given a user u 2 U , her social
network S and an item i 2 I suggested to u, UI-GF aims at discovering the
group of k friends of u which maximizes a measure modeling the \satisfaction"
of the group for the recommended item. This measure of satisfaction considers
both the mass appeal of the recommended item for every member of the group
and the intra-group social relations. Given the relevance R(u; i) of i for u we
need rst to extend the measure of relevance to pairs of users. This adaptation is
obtained exploiting two well-known relevance aggregation methods: Aggregated
Voting (RP AV (u; v; i) = R(u; i) + R(v; i)) and Least Misery (RP LM (u; v; i) =
minz2fu;vgR(z; i)) [
Since we aim at weighting di erently the interest of an item for a pair of users on the basis of their friendship, we introduce the pairwise satisfaction function measuring the relevance of a item i for two users u and v, weighted according the \strength" of their friendship w(u; v).
De nition 1 (Pairwise Satisfaction). Given an item i 2 I and u; v 2 U , the pairwise satisfaction of users u and v w.r.t. the item i is de ned as P S(u; v; i) = w(u; v) RP (u; v; i).
On the basis of this pairwise satisfaction we build the following User-Item Ego Network.
De nition 2 (User-Item Ego Network). Given a user u, an item i, and an integer , the User-Item Ego Network of u w.r.t i is de ned as an undirected weighted graph u;i = (F; E) where F U is the set of friends of u at a distance lower than or equal to in the original graph SG, and E is the set of edges weighted by the pairwise satisfaction P S( ; ; i).
We model the UI-GF problem of nding the \best" group of k friends of user u for item i as the problem of nding the densest k-subgraph over the useritem ego network. In this formulation the densest k-subgraph problem has the objective of nding the subgraph of exactly k users that maximizes the weighted pairwise satisfaction density. In this way, we go to the problem de nition that is to select from F a group of k users characterized by strong friendship relations and high interest w.r.t the proposed item i: De nition 3 (User-Item Group Formation). Given a user u, an item i, her user-item ego network u;i, and an integer k, the User-Item Group Formation problem asks to nd the subgraph Gu;i = (Fu; Eu) of u;i, jFuj = k that maximizes the weighted pairwise satisfaction density: 8Gu;i max u;i;jFuj=k (Gu;i) = 2 P8t;v2Fu P S(t; v; i)
k (k 1) < u, ✓ > < u,i >
R(u,i) Create User-Item Ego Network
k Dense Subgraph < u, i, k >
group Gu,i
Solving the user-item group formation problem thus requires to compute
the densest k-subgraph maximizing the pairwise satisfaction. The densest
ksubgraph problem is NP-hard since it generalizes the clique problem [
These algorithms are incorporated into the GroupFinder framework, which
includes three di erent components (see Fig. 1). The Recommender System
is in charge of providing the relevance R(u; i) of the item i for user u; the
Social Network Manager retrieves the ego network of focal node u; the Group
Finder Engine implements the algorithms for approaching the UI-GF [
GroupFinder have been compared against state-of-the-art baselines by employing public Location Based Social Networks (LBSN) datasets collected from Foursquare, Brightkite, and Gowalla.
For the experiments we use a content-based recommender system that
exploit the metadata associated with venues to measure user-item relevance scores.
The relevance score R(u; i) of an item i for a user u is computed as the cosine
similarity between the user's preference vector vu and item's relevance vector
vi [
We assess the quality of the group recommended by GroupFinder and
the baselines solutions on the basis of di erent metrics: the weighted pairwise
satisfaction density, precision, recall. The rst metrics corresponds to De nition
3 and allows us to assess the e ectiveness of the algorithms in approximating
the densest k-subgraph of the user-item ego network. The used baselines are:
(1) Densest k-Subgraph (DkSP ), a well known algorithm from [
The results achieved report that the densest k-subgraph-based approaches
tend to overcome k-Top. k-Top considers only the user interest measured by
R( ; ), thus it may generate groups in which the members are not actually friends
in the social network. This explains the lower weighted density obtained with
k-Top. Interestingly, DkSP performs remarkably better with PAV than with
PLM pairwise user-item relevance. Greedy and k-NN algorithms outperform
DkSP and k-Top in terms of weighted density with both PAV and PLM pairwise
user-item relevance. Greedy outperforms DkSP from 6% to 17% for PAV, and
from 26% to 46% for PLM. This means that it suggests groups characterized
by a good balance between friendship and users' relevance, avoiding to include
users who are not interested in the item or users that are not well-connected with
the rest of the group members. A similar behavior is con rmed when evaluating
the performance of the algorithms by using the recall metric since Greedy and
k-NN achieve higher recall gures when PLM is used. For the precision metric
for the Brightkite and Gowalla datasets, Greedy and k-NN are always the best
group formation approaches regardless the pairwise user-item relevance function
used. The relatively high values of precision and recall achieved by our solutions
(extensively discussed in [