Phacebook uses a simple clustering method described below to

Phacebook® uses a simple clustering method described below to cluster users into groups of close friends based on which a marketing campaign will be launched.  

For the following 9 users {a, b, c, d, e, f, g, h, i }, a friendship matrix is defined as follows: a value of 1 in a cell indicates the two corresponding users are friends; a value of 0 indicates the two users are NOT friends; and further a user is not considered as a friend to himself/herself. We want to cluster the 9 users into two groups.

a

b

c

d

e

f

g

h

i

a

0

0

0

1

0

1

0

1

1

b

0

0

1

0

1

1

1

0

1

c

0

1

0

1

0

0

0

0

1

d

1

0

1

0

0

0

1

0

0

e

0

1

0

0

0

1

0

0

0

f

1

1

0

0

1

0

1

1

1

g

0

1

0

1

0

1

0

1

1

h

1

0

0

0

0

1

1

0

1

i

1

1

1

0

0

1

1

1

0

This method takes two steps to complete:

1) We first select two users that have the most friends as the two cluster centers. (2%)

2) We then assign each of the remaining 7 users to one of the two clusters whose center he/she is most similar to.   (8%)

Instead of using distance in K-means as similarity measure, here we use the number of mutual friends between two users as the measure of similarity.

For example, a and b share two mutual friends (i.e., f and i) whereas a and d share no mutual friend; therefore a and b are more similar to each other than a and d.

If a user is equally similar to both centers, then he/she is assigned to both groups.

Apply this method to cluster the 9 users into two groups.

	a	b	c	d	e	f	g	h	i
a	0	0	0	1	0	1	0	1	1
b	0	0	1	0	1	1	1	0	1
c	0	1	0	1	0	0	0	0	1
d	1	0	1	0	0	0	1	0	0
e	0	1	0	0	0	1	0	0	0
f	1	1	0	0	1	0	1	1	1
g	0	1	0	1	0	1	0	1	1
h	1	0	0	0	0	1	1	0	1
i	1	1	1	0	0	1	1	1	0

Solution