This is a transcript of a mail I sent: on network theory, inspired by Linked
There are several types of networks all around us, e.g. social, computer, biochemical, internet and so on. People before 2000 tried to conduct various experiments on social networks, by trying to send out letters from A to B. A wouldn’t know B, but would fwd the letter to someone likely to know B. Like that they had some 160 letters sent out and measured the chain lengths. Basically the number of edges in the graph to traverse to that point.
I speak all this on the wake of a book “Linked” by Barabasi (http://www.nd.edu/~alb/), who’s a great genius and is on the way to become a legend! He’s done various types of network analyses — I am mostly concerned with his network biology… However, there are various kinds of networks, such as scale-free, small world, random and so on. The world view of Erdos (Erdos number is itself a kind of network measure. For beginners, Erdos was a great mathematician who travelled all over the world co-authoring papers with many many authors. Erdos was defined to have an Erdos number of zero; his co-authors’ EN=1; co-authors’ co-author EN=3 and so on… I guess my EN shd be about 5, considering there’s a prof Jayant in the dept with an EN of 2 or 3!) and Renyi was that the whole world was composed of random networks. The next idea of small-world networks was that of Watts, a PhD student of Steven Strogatz (who’s written a book called SYNC). It talks about ‘small world’ networks, where everyone has only a couple of links (for example, to the immediate neighbour and one more, say) plus a few random links, connecting wide across — try visualising this as circular table where everyone knows four people around him: i-1, i-2, i+1, i+2. Few ppl (0.3*n, say – very arbitrarily) know (randomly?) the person sitting bang opposite (~i+n/2). This greatly shortens the number of links between two arbitrary persons.
Barabasi has a whole theory of his, which I am yet to entirely familiarise myself with — I am still in the Fifth Chapter of the book (Barabasi calls it the Fifth Link!). He had made a crib at one point about the lack of a social network directory (this book was printed in 2003, and must have been written in 2002, before the days of orkut and hi5 etc). It is unbelievable as to what kinds of analyses are possible now that you have a network like orkut. So, I was just thinking on those lines, just casually, if some people out there know Barabasi’s work and are interested in doing some analyses.
You might really want to pick yourself a copy of the book: http://www.amazon.com/exec/obidos/tg/detail/-/0738206679?v=glance
Now, over to something called the Kevin Bacon game. Kevin Bacon is some hollywood actor (whom I ob don’t know considering my poor knowledge of English films!), who was the protagonist of a game developed by some college kids. They had a show on which they claimed they could link any actor to Kevin Bacon through two or three links.. THis is very similar to Erdos number (Erdos was a hub of mathematicians!). Barabasi’s analysis proved later on that Kevin Bacon, happened to be 876th on the list of most connected actors, but still had an average path length of around 3, which is why the game worked. I don’t know if you guys have heard the play and hence the phrase “Six Degrees of Separation”… it’s basically the same idea.. Kevin Bacon had ~ 3 degrees of separation from any hollywood actor!
Ok, I hope at least some part was interesting for most of you… But, most of the phrases and stuff I’ve used are things you’re going to see more of in the future. Be sure to read this book if you can or atleast see some pics on Barabasi’s site.