« Good Progress with Wilbur2 | Main | More Wilbur2 progress »


Erdös Numbers

Another take on the Small World Problem ("six degrees of separation" as some people like to say) is the concept of Erdös Numbers. Hungarian mathematicial Paul Erdös was very prolific and published a huge number of papers; he also had a large number of co-authors. Erdös number is defined as follows: Erdös himself has the Erdös number 0, his co-authors have the Erdös number 1, their co-authors have 2, etc. In other words, in a social network where co-authorship is a link, how many hops away are you from Erdös.

Since mathematics spills over to computer science, also many computer scientists have low Erdös numbers. Determining your Erdös number is not all that simple, however. If only we had special FoaF-style data about publishing and co-authorships, searching could be done automatically.

So far, I believe my own Erdös number is at most 6, given, for example, the following path: me, James Hendler, Lynn Stein, David Karger, Robert Tarjan, Stephen Hedetniemi, Paul Erdös. The real problem, I find, is that once you start pondering about path lengths, you cannot stop trying to find shorter ones. :-)

Posted by ora at 11:48


I can suggest a path of length five:

0 Paul Erdos, 1 Aviezri Fraenkel, 2 Yaacov Yesha, 3 Yelena Yesha, 4 Tim Finin, 5 Ora Lassila

Posted by: Tim FInin at October 7, 2005 05:47 PM

Waaahooo! :-)

Posted by: Ora Lassila at October 8, 2005 07:14 AM

Even I am at 5:

(0 Paul Erdos, 1 Andrew Odlyzko, 2 Gian-carlo Rota, 3 Walter Whiteley, 4 Ileana Streinu, 5 Louis Theran).

Problem 1: Is there anybody with a number higher than 5?

Problem 2: What is the support of the Erdos graph?

Problem 3: How do we get paragraphs in the comments?

Posted by: Louis Theran at December 7, 2005 11:55 AM