## Sunday, July 1, 2012

### The small world phenomenon

Recently by coincidence I learned that one of my dad's friends from old times was the friend of a friend of a friend of a friend. It's a cycle of length 6. Such cycles are probably quite common, but how easy is it to detect them when there are no shortcuts? Another way to phrase this: how can I discover the people who are at distance 3 from me but have at least 2 paths from me to them? Distance 2 seems feasible: as I chat with my friends, they often tell me about their own friends, so I know a little bit about my friends' friends, and so I can with reasonable chance discover cycles of length 4. But I know nothing about my friends' friends' friends...

#### 1 comment:

1. I had an experience of this kind recently too. I (C) went to a concert with my girlfriend (D) and in the queue we met a guy (E) who my girlfriend knew from playing chamber music - he was there with his wife (F). We sat down all together in the order C-D-E-F, and after a while a guy I sing in a choir with (B) spotted me and sat down on my left, reserving the seat on his left for his partner (A). When she arrived we were in the order A-B-C-D-E-F and it turned out that A and F already knew each other from work, so the graph of acquaintances was exactly C_6. This seemed quite remarkable to us at the time.