Archive | Networks

RSS feed for this section

Applied Math at the Movies (including supplement)

This morning I had an article entitled The Mysterious Equilibrium of Zombies in the Boston Globe Ideas section about applied math in movies. I mentioned a number of movies, math and articles. For those who are interested in more details, here are some references, film clips and stills:

Casino Royale and Fractals

Harry Potter and The Millennium Bridge

The Dark Knight and Game Theory

Zombie Epidemiology

Six Degrees of Separation

Balance Theory

Network Theory in Cities

Jason Kottke recently pondered what the minimum number of New York City residents one would need to choose, such that these people know every single person in the city:

Any guesses as to the smallest group size? Better yet, is there any research out there that specifically addresses this question? Or is it impossible…are there people living in the city (shut-ins, hermits) who don’t know anyone else?

People have been commenting about it on the blog, where the consensus seems to be about 10,000 people (this sounds pretty reasonable). My two-cents (which can be seen as the first comment on kottke) are reproduced here:

 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.