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...
Posted by Claire Mathieu at 17:20