This is actually a well-established problem in graph theory called the vertex-cover problem. It is NP-hard, which means that there are no really good algorithms for it (although some approximate algorithms are good within a factor of two). In terms of answering this for NYC itself, my guess would be something on the order of 1000 or so. But I don't have a good reason for that number, just a feeling. You could probably do better by assuming a power-law distribution for the number of acquaintances and derive a better estimate, but I haven't thought about that in detail.

Jason:

Read Linked: How Everything Is Connected to Everything Else and What It Means

As a statistical problem, I would be surprised if a survey could be efficiently conducted to get a large enough sample size. But certainly you see strong nodes (popular, well-known people) and weak nodes (poorly-connected people). I would certainly like to assert that it is impossible to construct an accurate graph of connections witin nyc population such that all nodes are connected. I suggest that it is inevitable that some long-term residents know only a handful of people, who in turn, actually only know each other. This will result in small disconnected networks in the resulting graph.

My best guess would be ~30,000. Based on a population of 8 million, each of those 30,000 would have to know an average of 267 distinct other people...which seems about right to me.

Or is that too many? How many people does the average person know anyway? 300? 500? 800?

i recall a stats class where it was stated that the "average" person "knows" about a thousand people. the criteria for "knowing" was someone you would recognize and be able to some sort of brief conversation with.

but i have no facts to substantiate this, just a recollection.

My hunch is less than 30,000, maybe closer to 20-25,000. Are we looking for the smallest random NYC sample that would know everyone else in the area? Or are we looking for the absolute smallest group cherry-picked from biggest socializers within the NYC population?

Absolute smallest group.

I've also heard the ~1000 people stat, but how many of those will be New Yorkers for any given New Yorker? Plenty, but not all.

I think the number would be a lot higher than 30,000. The biggest socializers may know two or three times as many people than an average person, but the people they know are probably the other socializers, so it limits their effectiveness. I would guess there's a pretty large number of people that only know a handful of other people

Milgram's findings aren't exactly proven. Maybe between urban legend and reality.

http://www.washingtonpost.com/ac2/wp-dyn?pagename=article&node=&contentId=A14356-2002Feb27&notFound=true?referrer=emailarticle
http://query.nytimes.com/gst/fullpage.html?res=9C05E6DE1739F936A15752C0A9659C8B63&sec=&spon=&pagewanted=all

In order to make sure this conversation devolves into adolescence, I think we all know the answer is 42.

Perhaps there is a clue in ancient Rome. The Roman army "company" of 120 men was considered the ideal number which could be effectively managed by a Captain. Still is.

I don't know about any of this, but I do know that I find it vastly interesting how an 'online' friend of mine from Maine was visiting NYC once, and as we were chatting she said she'd like to try to meet a cop friend of hers in the NYPD that she knew from an online geocaching community. Idly passing the conversation along, I asked about him... and it turns out that this same guy was actually a pretty good friend of mine. Oh, what a small world.

The present-day analogue to the Roman army company number is Dunbar's number: "Dunbar's number, which is 150, represents the maximum number of individuals with whom a set of people can maintain a social relationship, the kind of relationship that goes with knowing who each person is and how each person relates socially to every other person."

I think part of the problem is that while NYC is a city as a whole, it's really many distinct groups of people who just happen to live in a common area. The groups can be based on race, religion, ethnicity, and, probably most important, financial.

I'd guess it would be much higher than 30,000 to be able to jump the financial disparity between Park Ave. and, say, BedStuy. I'd put the number between 55,000 and 75,000.

"Dunbar's number, which is 150, represents the maximum number of individuals with whom a set of people can maintain a social relationship, the kind of relationship that goes with knowing who each person is and how each person relates socially to every other person."

Please, God, do not let the creators of Lost find this out.

> "Pick a group of people who live in NYC whose members collectively know everyone else who lives in NYC. What's the smallest number of people you'd need for that group?"

Is this a trick question? The answer depends on the number of people each person knows. Since I don't have data on your definition of knows, mine is that they are friends.

In this study called "Traffic's Human Toll," conducted in New York City, they found that the number of friends a person has decreases as the traffic in their neighborhood increases. They asked 600 subjects to count their friends and then categorized the subject's neighborhood into one of Astoria, Brooklyn Heights, Chinatown and High Bridge. They also indicated the amount of traffic in their neighborhood as light, medium or heavy. To find an average for NYC using this data, I will just take the average of each neighborhood's medium traffic case to arrive at the average number of friends for each new yorker. You could find better traffic data for every location in NYC and use the numbers from this study in a linear regression to estimate the exact number of friends for each new yorker, but i'll save that for someone else...so the number is 7.1 friends, on average.
(1) Population of NYC: = 8,143,198
(2) Average number of friends per this data = 7.1
(3) = (1)/(2) = 1,146,929.3

In the best case, every one of our 1,146,929.3 people knows exactly 7.1 people that nobody else in this group knows. They additionally do not know each other (or themselves).

As Josh says: Isn't the (empirical) difficulty here the question of social class?

It's an interesting thought experiment to see if we could imagine "mapping" the distinct social/spatial New Yorks, say, in terms of these networks.

Brian, I think you may be misreading the results of that study. 7.1 seemed like a bizarrely low average number of friends for any normal population, so I looked at the data—it appears that the 7.1 statistic represents how many friends or acquaintances someone has on their block. It's cited as a measure of "community cohesion," and it has nothing to do with how many friends one has overall.

I believe that the distinct pockets actually helps you. If you are cherry picking connected people for each community, you could get to 98% with a couple of thousand people. i.e. the rabbi who knows all the orthodox Jews, the guy who organizes community sporting events knows all the weekend basketball players. The leaders/organizers/activists would get you almost there.

That last 2% (still 162,000 people) would be a bitch, and require many more 10s of thousands of contacts.

Source: pulled out of ass

I think if you're talking about averages (that is, you went through and identified all of the groups of people such that everyone in NYC is known to at least one member of the group), then jkottke's 30,000 figure sounds about right. There are going to be plenty of "outlier" residents of NYC who know only a tiny handful of people, but then again, in most cases, among that handful will be some "hub people" who know lots and lots of others(clergy, shopkeepers, community outreach people, building supers).

But if the goal is to find the very smallest such group, I think it would number fewer than 30K. Sam's right that as a practical mathematical matter, proving you've identified the very smallest such group is very very hard. But you could try to assemble such a group by starting not just with socialites (since, as others point out, you'll tend to see a lot of overlap among the large groups of people they know), but with the kind of "hubs" I mentioned above. If you took 100 socialites from various groups/social strata, 100 ministers/priests/rabbis from various religions and neighborhoods, 100 shopkeepers from various enclaves around the city, 100 building supers (focusing on large buildings where people seem to have less social interaction), you're well on your way to having everyone covered. Throw in, like, 5 of those weird dudes haninging around in Washington Square Park, plus the 27 freaky guys in Queens who never leave their apartment, and you've probably got it covered. Oh, but you'd still have to figure out a way to link in Staten Island...

An equally interesting problem might be trying to figure out how large a pair of groups you could find in NYC, such that no one from one group knows anyone from the other group. Judging by the size of the smaller of the two groups (because saying "There's this one guy, and 8 million people in NYC don't know him" doesn't count), do you think you could get over a million? Two? If so, what does that say about your answer to the first question? (It may not say anything, since the problems aren't the same, but the answer to one my shed light on the answer to the other.)

I'm going to state a few facts that are blindingly obvious, but still unexplicably ignored by some fellow posters:

The population of NYC is about 8 million. If there really were 1000 people who collectively knew all the others, then, in a fantasy world of naïve oversimplifications, each of them would have to be acquainted with more than 8000 people. And, remember, we aren't just talking about recognizing someone's face, not even knowing their names is enough, these have to be acquaintances you'd have in your address book. Now, if we return to reality, and realize that the reason why sozial networks are networked in the first place is that there are such big overlaps (e.g. your friend knows half the people you know), and that specifically people who like to have many acquaintances have a strong tendence to clump together, we see that the average address book would have to contain more than 8000 contacts ... tens of thousands, in fact.

If you had ten thousand friends, and you called then all to invite them to your birthday party, spending about two minutes on each call, without taking breaks, it would take you about two weeks.

So, can the solution really be anywhere near 1000? No, it's off by orders of magnitude. Please, when you're following a gut feeling, do a simple sanity check.

Oh, and I hate hate HATE people who call everyone they're having a short chat with a few times a year a friend. I'm not talking about people who just want to be friendly, but the socialites, lounge lizards and sycophants who claim, "oh, I have two thousand friends, honest!" 7.1 is NOT a bizarrely low number of friends. It's realistic. I mean, as an average ... finding a tenth of a friend would be rather complicated.

Ignoring the analytics (which are admittedly way over my head), and keeping this NYC only... the true answer is that there is no answer. Every major urban city worldwide absolutely has to have a noticeable chunk of people that live alone, almost never go out and socialize, and (due to computers and internet) mostly likely work from home (or are perhaps rich enough not to work). Out of that chunk of people, almost assuredly there are a number of them that have no family anymore in the entire world (let alone still in NYC). And no friends.

There must people who live in NYC that no person knows about (let alone knows personally).

Therefore, it is impossible for a group of people in NY C to know absolutely everyone in NYC.

[Sorry, I guess this was one of those loopholes]

Yeah, it is one of those loopholes. I'd say since this is a statistics problem, it's enough if the "absolute minimum group" knows about 99,99% of all New Yorkers.

I don't think that those remaining 0,01% are wealthy people, just because only those can 'afford' not to make any aquaintances. I don't even think they're likely to have a job and work from home. I think such people generally are bums who are on some kind of drug (such as alcohol) half of the time. And maybe a few paranoid criminals who are hiding underground. Here's why: Pretty much no one is perfectly happy with having exactly zero acquaintances (even if we're only counting people from your home city ... the thing is, you mustn't forget that NYC is _big_, this is not like living in Hicksville, but only knowing people from Woodsville), and you'd actually have to go out of your way to maintain this status, and sane people don't invest much effort into maintaining a situation that makes them unhappy. Also, if you were deliberately avoiding all social contact (i.e. not out of depression, desperation, ...), working from home, never going out, you'd have to be a picture book idiot to choose NYC as the site of your home office.

a few connectors (as Malcolm Gladwell describes in the Tipping Point) can skew the data.