The quiet ones

Computer Science Level 4

Consider this mini social network of fifty people. Each person on the network is represented by an integer. The social network is represented as a matrix $A$ . If person $i$ and $j$ are "friends" then, $A_{ij}=1$ else $A_{ij}=0$ . . How many mutual friends do the two people with the least number of mutual friends have?

Details and Assumptions

$A_{xx}=0$ .

The answer is 16.

2 solutions

Peter Lively
Nov 29, 2015

Two people have a mutual friend when they both have a "1" corresponding to that person. Multipling two peoples' rows together will thus produce a "1" for each mutual friend and a "0" for each non-mutual friend (1*0) and "0" for friends neither has. The matrix is symmetric because if a person A is a friend of person B then person B is a friend of person A. This allows us to multiply the matrix by itself, then sum across the rows or columns. The lowest sum is the lowest number of mutual friends.

in Excel: Place the matrix in A1-AX50. Then use mmult(A1:AX50,A1,AX50). Sum the columns of the resulting matrix and find the minimum of the sums.

In Matlab: If the friend matrix is M, then N=M^2; min(sum(N))

Masbahul Islam
Nov 26, 2015

Excel VBA:

Sub Button1_Click()

k = 1

For x = 1 To 49

For j = x + 1 To 50

Count = 0

For i = 1 To 50

a = Cells(i, x)

b = Cells(i, j)

If a = 1 And b = 1 Then

Count = Count + 1

End If

Next i

Cells(54 + k, 1) = x & "," & j

Cells(54 + k, 2) = Count

k = k + 1

Next j

Next x

mm = WorksheetFunction.Min(Range("B55:B1000000"))

MsgBox (mm)

End Sub

The quiet ones

The answer is 16.

2 solutions

0 pending reports