Consider a set of n people who are members of an online social network. Suppose
ID: 2933488 • Letter: C
Question
Consider a set of n people who are members of an online social network. Suppose that each pair of people are linked as “friends” independently with probability 1/2. We can think of their relationships as a graph with n nodes (one for each person), and an undirected edge between each pair that are friends. A clique is a fully connected subset of the graph, or equivalently a subset of people for which all pairs are friends.
a) A clique of size 2 is simply a pair of nodes that are linked by an edge. Find the expected number of edges as a function of the number of nodes, n. What is the expected number of friend relationships among n = 10 people?
b) A clique of size 3 is a triplet of nodes within which all three pairs are linked by an edge. Find the expected number of 3-cliques as a function of the number of nodes, n. What is the expected number of 3-cliques among n = 10 people?
c) Larger cliques may occur involving groups of nodes of any size k. Find the expected number of cliques of size k 3 as a function of the number of nodes, n. What is the expected number of cliques of size k 3 with n = 10 people?
Explanation / Answer
(a) 2 nodes will form an edge with probability 1/2. A clique of size 2 can is a pair of nodes. A pair of nodes can be selected from a set of n nodes in C [n,2] = n * (n-1) / 2 ways.
Expected number of edges = (1/2) * n * (n-1) / 2 = n * (n-1) / 4
For n =10 people, expected number of friend relationships = expected number of edges = 10 * 9 / 4 = 22.5
(b) A clique of size 3 is a triplet of nodes within which all three pairs are linked by an edge.
A triplet of nodes can be selected from a set of n nodes in C [n,3] = n * (n-1) * (n-2) / (3 * 2) = n * (n-1) * (n-2) / 6 ways.
Since a triplet of nodes have to have 3 edges, and each edge forms with probability 1/2, the three pairs within the triplet of nodes can be connected with edges with probability (1/2) * (1/2) * (1/2) = 1/8
Expected number of 3-cliques = (1/8) * n * (n-1) * (n-2) / 6 = n * (n-1) * (n-2) / 48
For n=10 people, the expected number of 3-cliques = 10 * 9 * 8 / 48 = 15
(c) On similar lines as in part (b), k nodes can be selected from a set of n nodes in C [n,k] ways. The k nodes can be connected to each other in pairs with probability (1/2)^C[k,2], since there would be C[k,2] pairs to be connected.
Expected number of cliques of size k = C [n,k] * (1/2)^C[k,2]
For n = 10 people, expected number of cliques of size k 3 = C [10,k] * (1/2)^C[k,2]