In Facebook friendship graph the nodes are profiles and the edges are friendships (alternatively subscriptions could serve as well if we allow directed edges). Is the graph connected?

(Obviously it changes all the time, but is it close to being connected? If not, how many not-very-small components are there?)

References will be appreciated.

  • $\begingroup$ Why is the "Facebook graph" itself interesting? You could have considered social-networks in general, theoretical models that study certain geographical connectivity, something like that... $\endgroup$ – Juan Bermejo Vega Mar 9 '12 at 15:48
  • 10
    $\begingroup$ How is this a theoretical CS question? $\endgroup$ – Marcin Kotowski Mar 9 '12 at 16:06
  • 2
    $\begingroup$ And how could we know? That is, besides the trivial answer: Everybody can trivially create an isolated subgraph of arbitrary size. $\endgroup$ – Raphael Mar 9 '12 at 17:32
  • $\begingroup$ for sure there will be some nodes or subgraphs where a person signed up to Facebook and s/he doesn't have friends, or some kind of closed ring of friends. You can't guarantee that it's connected, and I believe it's the same for all social networks unless the logic behind that social network is to friend any new user with a default other account (like myspace). $\endgroup$ – K'' Mar 9 '12 at 19:37

Yes, it is nearly connected, with 99.91% of individuals belonging to a single large connected component, see this paper. You might also be interested in this one concerning the so-called $N$ degrees of separation.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.