<p>Yes, it is nearly connected, with 99.91% of individuals belonging to a single large connected component, see <a href="http://arxiv.org/abs/1111.4503" rel="nofollow">this paper</a>. You might also be interested in <a href="http://arxiv.org/abs/1111.4570" rel="nofollow">this one</a> concerning the so-called $N$ degrees of separation.</p>

CC BY-SA 3.0
2012-03-09T15:43:18.173Z
2012-03-11T15:12:17.890Z
2012-03-11T15:12:17.890Z
Juho
<p>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?</p>

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

<p>References will be appreciated.</p>

CC BY-SA 3.0
2012-03-09T15:48:46.570Z
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...
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-09T16:06:13.677Z
How is this a theoretical CS question?
Marcin Kotowski
CC BY-SA 3.0
2012-03-09T17:32:02.390Z
And how could we know? That is, besides the trivial answer: Everybody can trivially create an isolated subgraph of arbitrary size.
Raphael
CC BY-SA 3.0
2012-03-09T19:37:09.367Z
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).
K''
<reference-request><graph-theory>
is Facebook friendship graph connected?
Shir
# is Facebook friendship graph connected?

(Asked by: username_0 on 2012-03-09)

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.

**Tags:** reference-request, graph-theory

> **Comments:**
> **username_1**: 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...  
> **username_2**: How is this a theoretical CS question?  
> **username_3**: And how could we know? That is, besides the trivial answer: Everybody can trivially create an isolated subgraph of arbitrary size.  
> **username_4**: 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).  

---

## 1 answers

### Answer by username_5 on 2012-03-09. Score: 3 | Accepted answer

Yes, it is nearly connected, with 99.91% of individuals belonging to a single large connected component, see [this paper](http://arxiv.org/abs/1111.4503). You might also be interested in [this one](http://arxiv.org/abs/1111.4570) concerning the so-called $N$ degrees of separation.


---

