# Find friend groups in a virtual social graph

In my game, "people" form bonds through common interests. A person may have 1 or more interests, and a certain weight (0f - 1f) attached to it. Every now again, when 2 people are close to one another, relationships are formed based on common interests. E.g., if I have interests such as "Movies, Cheese, and Art", and you have "Movies and Cheese", then we have a pretty strong bond.

This is all working great, and over time, all the people in my game have some sort of bond with others.

What I'd like to do now, is construct social groups in a somewhat efficient manner (my game has an asynchronous task manager, so if the calculation is somewhat heavy, it's not a show-stopper). My current theory is to pick a person, look at his or her relationships, and then try to slowly build a graph to match as much like-minded people as possible.

I'm not 100% sure how to do this. I was thinking of comparing interests with common friends, but wondered if there was a better way? Currently relationships are stored as a person identifier, and then a list of (up to) 5 relationships, which contain their identifier, plus the weight.

The end result that I'd like, is a bunch of "groups" of like-minded people, that have been fed from this initial map.

What I'm looking for needs to be quite performant (with the caveat that I do have an asynchronous task manager), but the end result is that over time, social groups are constructed within which are people best suited to "hang out" with one another, based on their shared interests.

This sounds like a graph clustering problem.

Given a graph of nodes (people), and edges (bonds/relationships), where edges have weights (relationship strength), you want to split it into disjoint subgraphs (groups of people where no person is in two different groups), such that the level of connection inside each group is in some sense "higher" than the connection between groups.

How we define this "higher" level of connection will determine what algorithms we use, and what kinds of groups we get:

## A) Group the strongest relationships first

This approach leads to Kruskal's Algorithm - often used for finding a minimum spanning tree of a graph, but it can be stopped early to produce clusters instead.

Here you start with everyone in their own solo group.

Sort all your bonds by strength, then walk through the list from strongest to weakest, looking at each bond in turn.

If the two people sharing that bond are already in a group together, skip it and move on.

Otherwise, if the two people are in different groups, merge the two groups into one group containing all the members of each.

Stop once you hit a bond you consider too weak to unite a group, or once you're down to a desired number of groups.

This is simple to code up and with appropriate disjoint set data structures is very fast - the initial edge sort is the most expensive part ($$\O(E \cdot \log E)\$$). But it can produce "tenuous" groups, where individual members each share a strong bond with at least one other member, but might have no connection at all with more distant members in the same group.

## B) Find groups where everyone shares a strong bond

To counter this, we might insist that everyone in the group should have a strong relationship with everyone else in the group. In graph theory terms, this means they form a "clique," and finding them entails the NP-Complete "Clique Problem," so you can expect to work harder to find these. Exact algorithms run in exponential time, though their are more modest approximation algorithms you can try.

You can either convert your graph to an unweighted one by discarding all relationships below a threshold strength, to use algorithms that look for cliques with the largest number of members, or keep your weights and use algorithms that look for cliques of maximum total weight.

Depending on how you define which bonds are strong enough to count, you might find your graph contains very few, small cliques of just a handful of people - since two people knowing each other only as "a friend of a friend" is enough to block them from both being members of the same group.

## C) Allow friends-of-friends

We can relax our clique criterion to say it's OK if not everyone in the group knows everyone else directly, as long as they know someone who knows them. In graph theory terms, we're looking for subgraphs of diameter 2, where any two members of the group are separated by at most two relationships with a mutual friend in between.

We can find groups like these with a Highly-Connected Subgraphs clustering algorithm. Here again, we'd discard relationships below a threshold strength to convert our graph to an unweighted one. We then repeatedly search for a minimum cut, the smallest bundle of edges we can slice to split the graph into two. As long as there are fewer than half as many edges in the minimum cut than nodes in our group (the connection from one side of the group to the other is "weak enough"), we slice those edges out and repeat on each of the two subgraphs.

This animation by Fredseadroid via Wikipedia shows the algorithm in action.

This looks to me like it gives a good compromise between the tight connections of a clique and the six-degrees-of-separation chains of a Kruskal cluster, as well as intermediate complexity to compute (roughly $$\O(n^2)\$$ to $$\O(n^3)\$$ depending on the min-cut subroutine you choose).

• Hey, thanks very much for the informative, and very useful answer. – Moo-Juice Apr 6 '19 at 12:42