I’m often asked by my computer science/math pals about the research I’ve done as far as complex/social/small-world networks go. This is an attempt to answer the questions about where to start. What papers are the most important in this field?

Network Structure

To begin, the paper that basically kicked off the new network revolution was penned by Duncan Watts and Steve Strogatz and published in June of 1998. Their paper “Collective dynamics of ‘small-world’ networks” showed that many networks with a topology thought to be random don’t actually have a random underlying structure at all. Additionally, they introduced a simple model that captures the essence of most real-world networks. This paper is easy to read, and is a great starting point into the science of networks.

Next up is a paper by Barabási and Albert where they improved the understanding of network topology. In “Emergence of Scaling in Random Networks,” Barabási and Albert show that many networks with the “small-world” property actually have a power-law property. That is, the number of nodes with a certain degree distribution follows a power-law. For instance, in the World Wide Web many, many pages have zero or one other pages linking to them, whereas very few have hundreds of pages linking to them… and even fewer have thousands of pages linking to them. This event is called a power-law.

Ok so those are the two fundamental papers that the work I’ve done with networks is based on. Both papers are easy for any computer science or math major to understand, so I recommend giving them a read (they’re only a few pages each too). Tomorrow, I’ll look at another couple of important papers in this field.