Although we’ve seen many illustrations and schematics of networks in class, there hasn’t been much discussion of how we might analyze or model large networks, which are seemingly impossible to understand at a glance. The importance of being able to model large networks rather than simply looking at many examples of large networks is because in most cases merely looking at a visualization of a very large network doesn’t provide much insight into the behavior and structure of the network, as is obvious from looking at the diagrams that attempt to show the Internet as an confusingly entangled mass of connected nodes.

Thus, one approach is to view large networks as random graphs with particular characteristics. There are many papers on this subject, two of which I bring up in this post, mostly because they’re relatively readable for anyone who has any sort of computer science or math background.

The first paper is The Structure and Function of Complex Networks, M. E. J. Newman. Newman gives an introductory description of the role of networks in the real-world and then provides slightly more technical explanations that are useful in analyzing networks of all sorts. The one I found most relevant to this course is the Watts-Strogatz model for small-world networks (Section VI, pp. 27-29). In short, Watts and Strogatz propose a way to model small-world networks that makes them simpler and easier to understand. In general, the Watts-Strogatz model only applies to small-world networks, but in this course, those are just the kinds of networks that we’re studying.

As an additional note, the paper also references the idea of “interlocks” among corporate board members (Section IV.B.4, p. 25), which was the topic of penguin21’s post They Rule, which Professor Kleinberg linked to the paper What do Interlocks do? in the parallel digest blog for this course.

The second paper is Random Graphs with Arbitrary Degree Distributions and Their Applications, M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Although this paper is a little more technical than the one I mentioned above, it’s definitely readable after reading through the previous paper, which gives enough background to understand this paper. The focus of the paper is on random graphs with arbitrary degree distributions, which is in contrast to the small-world network model. In the small-world network model, we make several assumptions about the structure of the network (thus, making it a small-world network), while this paper addresses random graphs where the assumptions are not so constrictive (thus, the “arbitrary degree distributions” part of the paper’s title). As the paper points out, many kinds of networks in the world don’t follow the small-world model, and in other cases, the small-world model misses out on capturing some essential information when used in certain situations and on some types of networks. Therefore, understanding a broader range of random graphs greatly helps in the analysis of many kinds of networks that we find in the real world.

Again, the paper mentions the corporate interlocks (Section V.A, p. 14), which were first mentioned on this blog by penguin21. Keep in mind that there are many other important examples of real-world networks. It’s not that corporate interlocks are the only important example; it’s just that this example is the only one that has been posted on the blog that I’ve been able to connect to the papers (mostly because there aren’t many posts on the blog yet).  Another example the paper mentions that we’ve seen in the class is the relationships among actors and the average degree of separation in the movie industry, which was described in The Tipping Point, Malcolm Gladwell (pp. 46 - 49).

In summary, analyzing networks as random graphs is one of the most effective and practical ways of understanding how networks behave, operate and grow. Most of the analysis requires background knowledge in graph theory and probability. Even those without technical backgrounds can still appreciate the introductory sections to the papers, which outline the significance of understanding networks and their applications, from social networks to information networks to biological networks.