Phacebook® uses a simple clustering method described below to cluster users into
ID: 3378380 • Letter: P
Question
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
Explanation / Answer
Phacebook® uses a simple clustering method described below to cluster users into