Honestly, it would only be n^2 if every node connected with every other node. I'm certainly not friends with EVERYONE who ever is or was on facebook!
But if a fairly static percentage of those connections are important, you are just multiplying by a factor which would still make it proportional to N^2. Though the law may fail for other reasons.