I agree with you in principle, but I think the problem is more one of scale than of complexity theory. Sure the clique problem is hard to approximate in arbitr

I agree with you in principle, but I think the problem is more one of scale than of complexity theory. Sure the clique problem is hard to approximate in arbitrary graphs, but the graphs that appear in social networks are far from arbitrary. And indeed, in such scale free networks the clique problem becomes quasi polynomial or polynomial (http://link.springer.com/chapter/10.1007/978-3-642-35261-4_68 http://link.springer.com/chapter/10.1007/978-3-642-35261-4_6...). Approximate solutions are also much easier to find. On the other hand, the sheer size of Facebook's social graph means that anything other than streaming algorithms or local search is pretty much intractable. That makes solving these kinds of problems into interesting engineering challenges.