Facebook's 'People you may know' Feature Uses This Simple Algorithm

Each person has $d_i$ people in the group who they don't know. If every person who they don't know does know every person who they do know, then each person can partake in a maximum number of FSTs, given by $\displaystyle \frac12 d_i\left(9-d_i\right)$ .

Ignoring possible constraints, the maximum possible number of FSTs is given by

$\sum\limits_i \max \frac12 d_i\left(9-d_i\right) = 10 \max \frac12 d_i\left(9-d_i\right) = 100$

We now show that such an arrangement is possible (blue indicates a random person of interest):

img

The sum is maximized by an arrangement in which the 10 people are partitioned into two sets of equal size, each containing people who don't know people in their own set, but do know every person in the other set.

Note : $d_i=5$ also maximizes the sum but it is not possible to put each person in a group with 5 people who they don't know. It is also not possible to put some people into a group with 5 people who they don't know and put others into a group with 4 people who they don't know because the first group would have to contain 6 people.

Lets divide 10 in two groups group A and group B with 10 - x people and other with x people respectively. Each person in a group doesn't knows other members but knows all the members of the other group. Take any two member of a group A, the two don't know each other but they have all members of group B as common friends, so for two members we have x FSTs. Now there $\binom {10-x} {2}$ such pairs of two in group A so $x \binom {10-x} {2}$ FSTs for a group A. Similarly for group B we have $(10-x)\binom {x} {2}$ FSTs.

Total FSTs = $x \binom {10-x} {2} + (10-x)\binom {x} {2} = 4x(10-x)$ Maximum of which occurs at $x = 5$ , which is $\boxed{100}$ FSTs

I chose to take it step by step, starting from 4 people (maxfst(4) = 4)

if 4 people are named a, b, c, d, respectively, the configuration that maximises FSTs is when a is not friends with b and c is not friends with d

suppose a 5th person e comes into the picture. under the assumption that the maxFST(n) = maxFST(n-1) + number of FSTs that include the nth person (i.e. non-maximising configurations of (n-1) people cannot generate maximising configurations for n people), maximising the FSTs with 5 people is a matter of choosing who e is friends with.

if e is friends with a, let a = 1, otherwise a = 0, and the same applies to b, c, and d.

since a is not friends with b, e needs to be friends with both a and b to form the FST abe. since a is friends with c, e needs to be friends with exclusively either a OR c to form the FST ace.

this produces a series of logic gates, whose sum, when added to 4 (maximum FSTs with (n-1) people), is equal to the maximum FSTs with 5 people.

a AND b a XOR c a XOR d b XOR c b XOR d c AND d

the ordered quadruplet (a, b, c, d) = (1, 1, 0, 0) gives 9 FSTs with 5 people, 1 shy of the total number of triangles = ${5 \choose 3}$ = 10. it is trivially proven that 10 is impossible; because of the AND gates; if both a AND b and c AND d are equal to 1, then all other 4 gates have to be 0; hence at least either one of the AND gates must be 0.

we repeat the process for the 6th person f, this time with 4 new logic gates: a XOR e, b XOR e, c AND e, d AND e. since the configuration used previously was (1, 1, 0, 0), f must be friends with either a or e (not both) to produce FST aef, but both c and e to produce cef.

paying attention to the AND gates since intuitively they are the most restrictive, maximising FSTs for 6 people is quite simply (0, 0, 1, 1, 1, 1); and when the results of the gates are summed up, we get 9; adding this to 9, we get 18.

the process is repeated again and again until we reach the 10th person j; along the way, the AND gates seem to form between restricted pools of people; after this step a, b, f have AND gates all with one another and c, d, e also all with one another. to satisfy all the other XOR gates that exist, it's only a matter of setting all the people in one pool to 1 and the other pool to 0; this gives maxFST (n) - maxFST(n-1) = ${(n-1) \choose 2} - {k \choose 2}$ = (total number of gates) - (number of AND gates sacrificed by setting one pool to 0), where k is the number of individuals in the smaller pool.

maxFST (7) = 18 + 15 - 3 = 30, maxFST (8) = 30 + 21 - 3 = 48, maxFST (9) = 48 + 28 - 6 = 70, maxFST(10) = 70 + 36 - 6 = $\boxed{100}$ .

Thankfully this solution requires basic intuition only...

Name persons as A,B....J. Fix a person (say A) Now A can be friends with n (out of 9 others) and strangers to (9-n) remaining. Why not apply symmetry (i.e. Let each person be friends with n others and strangers to 9-n others. Symmetry is the point at which no. of FSTs is maximum (Don't ask why))

Put n = 5 (5 friends and 4 strangers)

Say A is friends with BCDEF. G is friends with BCDEF ... J is friends with BCDEF

Now, Out of AGHIJ, choose any two (=10 ways) For each such pair, there are 5 FSTs. (=>50 FSTs counted)

Now, Out of BCDEF, choose any two (=10 ways) For each such pair, there are 5 FSTs. (=>50 FSTs counted)

total = 100