Let us revisit the community detection problem but with an interesting twist. Re- member that we...

 

Transcribed Image Text:

Let us revisit the community detection problem but with an interesting twist. Re- member that we have a collection of n people for some odd integer n and we know that strictly more than half of them belong to a hidden community. As before, when we introduce two people together, the members of the hidden community would say they know the other person if they also belong to the community, and otherwise they say they do not know the other person. The twist is now as follows: the people that do not belong to the community may lie, meaning that they may decide to say they know the other person even though in reality only people inside the hidden community know each other. Concretely, suppose we introduce two people A and B, then what they will say would be one of the following (first part of tuple is the answer of A and second part is the answer of B): if both belong: (know, know); if A belongs and B does not: (does not know, know/does not know); if B belongs and A does not: (know/does not know, does not know); if neither belongs: (know/does not know, know/does not know); Design an algorithm that finds all members of the hidden community using O(n) greetings. (+10 points) Let us revisit the community detection problem but with an interesting twist. Re- member that we have a collection of n people for some odd integer n and we know that strictly more than half of them belong to a hidden community. As before, when we introduce two people together, the members of the hidden community would say they know the other person if they also belong to the community, and otherwise they say they do not know the other person. The twist is now as follows: the people that do not belong to the community may lie, meaning that they may decide to say they know the other person even though in reality only people inside the hidden community know each other. Concretely, suppose we introduce two people A and B, then what they will say would be one of the following (first part of tuple is the answer of A and second part is the answer of B): if both belong: (know, know); if A belongs and B does not: (does not know, know/does not know); if B belongs and A does not: (know/does not know, does not know); if neither belongs: (know/does not know, know/does not know); Design an algorithm that finds all members of the hidden community using O(n) greetings. (+10 points)