This seems like a graph clustering downside.

Given a graph of nodes (folks), and edges (bonds/relationships), the place edges have weights (relationship power), you need to break up it into disjoint subgraphs (teams of individuals the place no particular person is in two totally different teams), such that the extent of connection inside every group is in some sense “increased” than the connection between teams.

How we outline this “increased” degree of connection will decide what algorithms we use, and what sorts of teams we get:

A) Group the strongest relationships first

This method results in Kruskal’s Algorithm – usually used for locating a minimal spanning tree of a graph, however it may be stopped early to provide clusters as an alternative.

Here you begin with everybody in their very own solo group.

Sort all of your bonds by power, then stroll by way of the record from strongest to weakest, taking a look at every bond in flip.

If the 2 folks sharing that bond are already in a bunch collectively, skip it and transfer on.

Otherwise, if the 2 persons are in several teams, merge the 2 teams into one group containing all of the members of every.

Stop when you hit a bond you take into account too weak to unite a bunch, or when you’re right down to a desired variety of teams.

This is straightforward to code up and with acceptable disjoint set information buildings could be very quick – the preliminary edge type is the most costly half ($O(E cdot log E)$). But it could possibly produce “tenuous” teams, the place particular person members every share a robust bond with at the very least one different member, however might need no connection in any respect with extra distant members in the identical group.

B) Find teams the place everybody shares a robust bond

To counter this, we’d insist that everybody within the group ought to have a robust relationship with everybody else within the group. In graph idea phrases, this implies they type a “clique,” and discovering them entails the NP-Complete “Clique Problem,” so you’ll be able to anticipate to work more durable to search out these. Exact algorithms run in exponential time, although there are extra modest approximation algorithms you’ll be able to attempt.

You can both convert your graph to an unweighted one by discarding all relationships beneath a threshold power, to make use of algorithms that search for cliques with the biggest variety of members, or preserve your weights and use algorithms that search for cliques of most complete weight.

Depending on the way you outline which bonds are sturdy sufficient to depend, you may discover your graph accommodates only a few, small cliques of only a handful of individuals – since two folks understanding one another solely as “a pal of a pal” is sufficient to block them from each being members of the identical group.

C) Allow friends-of-friends

We can chill out our clique criterion to say it is OK if not everybody within the group is aware of everybody else instantly, so long as they know somebody who is aware of them. In graph idea phrases, we’re searching for “subgraphs of diameter 2”, the place any two members of the group are separated by at most two relationships with a mutual pal in between.

We can discover teams like these with a Highly-Connected Subgraphs clustering algorithm. Here once more, we would discard relationships beneath a threshold power to transform our graph to an unweighted one. We then repeatedly seek for a minimal lower, the smallest bundle of edges we are able to slice to separate the graph into two. As lengthy as there are fewer than half as many edges within the minimal lower than nodes in our group (the connection from one aspect of the group to the opposite is “weak sufficient”), we slice these edges out and repeat on every of the 2 subgraphs.

This animation by Fredseadroid by way of Wikipedia reveals the algorithm in motion.

This appears to be like to me prefer it offers compromise between the tight connections of a clique and the six-degrees-of-separation chains of a Kruskal cluster, in addition to intermediate complexity to compute (roughly $O(n^2)$ to $O(n^3)$ relying on the min-cut subroutine you select).