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 :)