MaxGF: Bridging the Gap Between Friend Recommendation and Social Activity Organization

TL;DR

Online social networks (OSNs) excel at recommending individual friends but often struggle to organize group activities that foster new friendships. This paper defines the Hop-bounded Maximum Group Friending (HMGF) problem. It introduces a heterogeneous graph model that combines existing friendships with potential ones, offering a 3-approximation algorithm to find the "sweet spot" of group size where people are likely to hit it off without feeling like total strangers.

The "Social Presence" Problem

According to Social Presence Theory, online interactions are inherently inferior to face-to-face ones. While sites like Meetup or Facebook Events facilitate gatherings, they usually either target tight-knit friend groups or complete strangers.

The authors identify a critical missing piece: Social Lubricators. To make new friends effectively, you need a group that contains both:

1. Potential Friends: People you don't know but are likely to like (high link-prediction weight).
2. Social Lubricators: Mutual friends who ensure you aren't socially isolated during the event (short hop distance in the friendship graph).

Methodology: The HMGF Framework

The problem is modeled as a heterogeneous social graph $G=(V,E,R)$:

• $E$ (Solid Lines): Existing mutual friendships.
• $R$ (Dashed Lines): Potential friendships with weights $w$ (likelihood of becoming friends).

The Objective Function

The goal is to maximize the average weight $\sigma (H)$: $\sigma (H)=\frac{w(H)}{|H|}$ Subject to:

• Size constraint: $|H|\ge p$ (the group isn't too small).
• Cohesion constraint: $d_E(u,v)\le h$ (any two people are within $h$ hops via existing friends).

In the figure above, (d) represents the optimal balance: high potential weights with tight social "hops" as lubricators.

The MaxGF Algorithm

The authors prove that HMGF is NP-Hard and has no standard approximation. To solve this, they propose MaxGF, which:

1. Iterates through candidate "reference" vertices.
2. Constructs a hop-bounded subgraph around the reference.
3. Refines the group by greedily removing vertices with the lowest "incident weight" (contribution to potential friendships).
4. Relaxes the hop constraint slightly (to $2h$) during processing, then uses a Post-Processing step (Expand & Shrink) to pull the solution back into the $h$ constraint while maximizing quality.

Experimental Validation

The researchers didn't just run math; they conducted a User Study with 50 Facebook users.

Key Findings:

• Efficiency: While humans take minutes to struggle with these constraints, MaxGF finds solutions in milliseconds.
• Human Alignment: 74% of users preferred MaxGF's groups over traditional density-based subgraphs (DkS), noting that DkS often fails to differentiate between "friends" and "potential friends," leading to awkward or ineffective social groupings.

Fig 3: Highlights how MaxGF maintains high feasibility (FeaRatio) and quality (ObjRatio) compared to the optimal baseline while scaling much better.

Critical Insight & Conclusion

The brilliance of this work lies in the $w(H)/|H|$ objective. Unlike simple density measures, this ratio naturally seeks the most "valuable" social connections without letting a large group size dilute the interaction quality.

Future Outlook: While the current model uses hop distance as a proxy for social comfort, future iterations could integrate NLP-derived interest similarity or real-time location data to make these group recommendations even more potent for modern OSNs like Discord or LinkedIn.