Thread: Clique Problem of Social Networks

First off, I am not sure if this is the appropriate place to post this question but it's my best guess. An op can move it if appropriate.

My question is about what I understand is the 'decision problem' of the 'clique problem' of social networks. As far as I understand it it basically says that it is computationally very difficult or at the least time consuming to locate a clique of a given size (a group of people that are all connected to each other) within a well connected social network. It would seem to take an exponential amount of time to do relative to the number of people in the social graph.

My question is. If we take facebook as example, and I add a new 'friend' would it be simple enough to determine whether that new connection completes a clique of a given size (i.e. 5), or would that still be computationally very difficult to do.

Thanks

Originally Posted by runner108

First off, I am not sure if this is the appropriate place to post this question but it's my best guess. An op can move it if appropriate.

My question is about what I understand is the 'decision problem' of the 'clique problem' of social networks. As far as I understand it it basically says that it is computationally very difficult or at the least time consuming to locate a clique of a given size (a group of people that are all connected to each other) within a well connected social network. It would seem to take an exponential amount of time to do relative to the number of people in the social graph.

My question is. If we take facebook as example, and I add a new 'friend' would it be simple enough to determine whether that new connection completes a clique of a given size (i.e. 5), or would that still be computationally very difficult to do.

Thanks

Some thoughts.

If you have a fixed size like 5, then you should be able to speed things up by keeping an updated list of all 4-cliques for each member, stored as the three friends connected to that member (obviously, no need to include the member himself/herself in the list). Then when two members become friends, see if the two people have a list element in common (maybe organize lexicographically and iterate through both lists in parallel). If and only if they share a common list element, their friendship will create a 5-clique. Of course, you can keep track of 4-cliques by keeping lists of 3-cliques, etc. The memory overhead of this could be quite a lot in practice.