PRISM’s “Two Hops”

NSA agents are trained to target friends of friends. How many friends of friends do you have?

A smartphone user shows the Facebook application on his phone in the central Bosnian town of Zenica, in this photo illustration, May 2, 2013.
If you’re the target, all the friends of all your friends are candidates for data gathering as well

Photo by Dado Ruvic/Reuters

News reports on the secret PRISM data-surveillance program suggest that agents are focusing attention on people “two hops” from a target of interest. In other words, if I’m the target, all the friends of all my friends are candidates for data gathering as well.

But how many people is that? For instance, if you listed all your friends on Facebook, and then made a big list of all of their friends, how many people would that actually be?

Facebook doesn’t offer an easy way to get a definitive accounting, so I decided to use the new Facebook Graph Search to make a quick and dirty estimate. If you ask it to show you all the friends of your friends, it just tells you there are more than 1,000, but doesn’t supply an exact number. If you want a count, you have to ask it something more specific, like “How many friends of my friends are named Constance?”

In my case, the answer is 25.

So what does that mean? Well, according to Marty Wattenberg’s amazing NameVoyager, between 100 and 300 babies per million are named Constance, at least in the birth-date range that contains most of Facebook’s user base and, I expect, most of my friends-of-friends (hereafter, FoFs). So under the assumption that my FoFs are as likely as the average American to be named Constance, I should have between 85,000 and 250,000 FoFs.

That assumption is massively unlikely, of course; name choices have strong correlations with geography, ethnicity, and socioeconomic thingamabobs. But you can just do this sort of search redundantly to get a sense of what’s going on. Fifty-nine of my FoFs are named Marianne, a name whose frequency ranges from 150-300 parts per million; that suggests a FoF range of about 200-400K.

I did this for a few names (50 Geralds, 18 Charitys (Charities??)) and the overlaps of the ranges seemed to hump at around 250,000, so that’s my vague estimate for the number of FoFs in my network.

But then I remembered that there was actually a paper about this on the arXiv, “The Anatomy of the Facebook Graph,” by Ugander, Karrer, Backstrom, and Marlow, which studies exactly this question. They found something which is, to me, rather surprising: The number of FoFs grows approximately linearly in the number of friends. The appropriate coefficients have surely changed some since 2011, but they get a good fit with #FoF = 355(#friends) – 15,057.

For me, with 680 friends, that’s 226,343. Good fit! (Of course, this line is only appropriate for people with a fairly large group of Facebook friends; it would predict a negative number of FoFs for anyone with fewer than 42 friends.)

This 2012 study from Pew (on which Marlow is also an author) studies a sample in which the respondents had a mean 245 Facebook friends, and finds that the mean number of FoFs was 156,569. Interestingly, the linear model from the earlier paper gives only 72,000, though to my eye it looks like 245 is well within the range where the fit to the line is very good.

These studies are filled with interesting data about the Facebook graph. The graph tends to be assortative; that is, the more friends you have, the more friends, on average, your friends have. What’s more, your friends, on average, have more friends than you do! That’s not because you’re a schmuck; it’s just that those people with thousands of contacts on their profiles, the Superfriends, are by their nature more likely to show up on your lists than less compulsive friend-adders, and it’s the Superfriends who really pull the average upward. (Mathematician Steven Strogatz wrote up a great explanation of this phenomenon last year in the New York Times.)

Indeed, the Superfriends make the study of the Facebook graph an object lesson in the difference between means and medians. In the Pew study, the mean (that is, the average) number of friends was 245; but the median was only 111, which means that only half the sample had more than that many. The average number of friends of friends was 156,569, but the median was only 31,170, a fifth as big. How did the average get so big? The study says that the very friendliest member of their study had a friend-of-friend network of almost 8 million people. If you want to keep the NSA occupied, you should send in a tip about that guy.

A version of this piece originally appeared on Jordan Ellenberg’s blog.