Erdös-Rényi Graphs

We started with a discussion of the early Christian Paul and “Mafia Boy” and the supposed connection between how Paul helped spread Christianity and how “Mafia Boy” launched a denial-of-service attack on Yahoo! in 2000. Barabasi uses the phrase “masters of the network” to describe both Paul and “Mafia Boy.” While this is an evocative phrase, I must say that I am skeptical of there being more than a superficial connection between the early spread of Christianity and this attack on Yahoo!’s servers. It is easy to imagine that there were external factors that had nothing to do with Paul’s “mastery” of his networks that had a bigger impact on the early spread of Christianity.

Our discussion then shifted to the collaboration of two Hungarian mathematicians, Paul Erdös and Alfréd Rényi, who studied mathematical properties of random graphs obtained by a simple random process in which pairs of nodes are connected by edges independently and with a fixed probability p. In our first class we created an Erdös-Rényi graph with nodes being the 17 students in class and pairs of students connected by edges (“hand shakes”) with probability p = 1/2. We looked at the degree distribution of this network and chatted about how this graph, and Erdös-Rényi graphs in general, are unlikely to contain nodes whose degrees are too high or too low, relative to the expected degree. This seems to make Erdös-Rényi graphs somewhat different from “real-world” networks in which it is common to have lots of nodes with very small degree, relative to the expected degree.

Slides from the class.

Homework for next class (9/4): Read Chapter 2 (“The Random Universe”) from the textbook.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s