Heavy-Tailed Degree Distributions

We discussed how some distributions (e.g., human heights, scores on standardized tests, etc.) have the “bell curve” shape (normal or Gaussian distribution) whereas others (e.g., populations of cities, sizes of earthquakes, etc.) have a very different, heavy tailed shape. In such distributions there are lots of items with tiny values and a few items with enormous values. The “heavy” (sometimes called “fat” or “long”) tail of the distribution refers to the fact that a small, but not insignificant number of items in the distribution take on extremely large values relative to the mean. See these slides for more details.

The reason we are interested in shapes of distributions is that real-world networks seem to have a heavy-tailed degree distribution. In other words, real-world networks seem to contain lots of nodes with very small degree, but also a small number of nodes (aka “hubs”) with very high degree. The Computational Epidemiology research group at Iowa has built a “contact networks” for health-care workers at the  University of Iowa Hospitals and Clinics (UIHC) and these networks show a clear heavy-tailed degree distribution. See these slides for a description of how these networks were built and for plots that clear show the heavy-tailed shape of the degree distributions of these networks.

The fact that many real-world networks have heavy-tailed degree distributions means that random graph models for generating real-world networks need to able to generate nodes with these degree distributions. This is the main motivation for the preferential attachment models proposed by Barabasi and Albert. More on this next week.

Homework (Due by e-mail on Friday, Oct 26th): Wolfram Alpha is a “computational engine” on the web that I use a fair bit. If you have not used it you should spend some time playing with it! You can type “weather in Iowa” or “human height distribution” or “Solve x^2 + 9x = 12” or anything else that strikes your fancy and see what output is produced. You should also try clicking on “Examples” to read more about all the kinds the queries Wolfram Alpha is designed to answer.

Recently Wolfram Alpha added capabilities that allow it to do “personal analytics” using your Facebook data. See this blog post by Stephen Wolfram and this web page for more details. In Part I of the homework I would like you to use Wolfram Alpha to generate a “Facebook report” for yourself and take a close look at this report before class on Tuesday, Oct 23rd. In class, I would like to discuss your findings and I will also ask for volunteers to show their “Facebook report” in class (using my laptop). If you are uncomfortable doing this you can opt out by sending an e-mail before class. In Part II of the homework I want you to write a report (max: 2 typed pages) for the class on what you learned about your Facebook friends and the structure of your Facebook friends network from this report. Describe any aspects of the report you found surprising. Feel free to include plots/graphs produced by Wolfram Alpha in your report.



Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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