Models of random graphs, for real computer networks

I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is selected with probability $p$) is good for studying real computer networks (is it?).

what models of random graphs are useful for understanding computer networks araising in practice?

More generally, what other models of finite random graphs (other than those equivalent to the $G(n,p)$ model) have been studied in the literature? (An ideal answer would be a pointer to a survey for studied models of finite random graphs.)

• Where do you need such models – is it just to generate some test inputs for algorithms, or do you want to analyse the models in order to learn something about computer networks? What kind of computer networks you are interested in; what is your scale (LAN vs. internet)? Why do you assume that real computer networks are generated by a random process – surprisingly often real-world networks are actually designed by an engineer, with fairly little coin-tossing? Apr 29 '11 at 4:34
• @Jukka, I am trying to see if I can apply the techniques developed for $G(n,p)$ to such those random models to obtain information about the real networks, I don't like to be more specific right now because it might give away the problem I am thinking about :). I am mainly interested in the IP layer of Internet. I have seen people use random graphs to analysis the graphs arising from social networks. I am not sure why these real networks share properties with random graphs, there might be a hidden random process behind the surface at work (it seems like an interesting question to ask :). Apr 29 '11 at 4:55
• I guess part of the interest in using the random models is that analyzing them is easier than analyzing real networks, so it is reasonable to consider them if they are good enough approximation to the real one. Apr 29 '11 at 4:55
• Thanks everyone for nice answers. (Now I have to spent sometime reading these papers. :) May 5 '11 at 0:01

In the last few years, the study of random graphs with "natural" structural constraints has gained traction. For example, one can consider a planar graph drawn u.a.r. from the class of all planar graphs with $n$ vertices and study how it behaves as $n \rightarrow \infty$. Unlike the Erdős-Rényi random graphs or other similar models, the edges in these graphs are highly dependent, so one of the pseudo-motivations for studying such distributions is to analyze network models with very limited independence between edges.

However, perhaps at present this goal seems quite far away as the limited independence makes it a lot harder to analyze the properties of such graphs. In fact, several basic questions which are very easily answered for $G(n, p)$, like the distribution of the degree sequence have only been resolved for random planar graphs very recently.

For a definitive reference, see the papers by Konstantinos Panagiotou and the citations contained therein. For convenience, here is a small sample of some relevant papers :

• On the Degree Distribution of Random Planar Graphs. Konstantinos Panagiotou and Angelika Steger. To appear in the Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11).
• On Properties of Random Dissections and Triangulations. Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), p. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
• On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs. Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger. In Proceedings of the 12th International Workshop on Randomized Techniques in Computation (RANDOM'08), p. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]
• An additional comment: this line of research actually goes back some 15 years, at least to a paper of Denise, Vasconcellos, and Welsh (1996), and one reason it is has "gained traction" now is the great success of the application of analytic combinatorics and asymptotic enumeration here, e.g. by Gimenez and Noy (2009).
– RJK
Apr 29 '11 at 13:17

This survey, The structure and function of complex networks by Newman, reviews techniques and models for real complex networks including concepts such as small-world effect, degree distributions, and random graph models. Also, the same author has a nice paper, Random graphs as models of networks, about adaptations of random graphs to model real networks.

References:

1) Random graphs as models of networks, M. E. J. Newman, in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.), Wiley-VCH, Berlin (2003)

2) The structure and function of complex networks, M. E. J. Newman, SIAM Review 45, 167-256 (2003)

• just curious: is this for "social" networks vs the internet ? Apr 29 '11 at 0:57
• I second this: the approaches to social networks should be highly useful, given that much of the study of these networks was originally focused on "universal" properties of networks, and included neural topology, the power grid, and road networks. Also, Barabasi-Albert and Watts-Strogatz nets, each with properties that real networks have and Erdos-renyi neglects, are very very very well-studied Apr 29 '11 at 6:14
• @Suresh, those complex networks covered in both references include computer networks such as the Internet and social networks. Apr 29 '11 at 7:58

Real computer networks at what layer? The Internet is, at the AS level (arguably the topmost level), a small-world network with some extremely high-degree nodes. As the layers get closer to actual wires, the graph becomes more linked to geography and less linked to the social layer (social is kind of the wrong word - is it really a social network when the entities being "friends" are multinational corporations?). In the extreme case, a local ethernet is a logical tree that is (probably) a subgraph of the physical pattern of wire connections, and that pattern of wire connections is probably not too many wires more than a tree.

"Real computer networks" come in lots of flavors and layers. Some of them look like social networks, some don't. For more on this, I immodestly refer you to chapter 2 of my dissertation - http://home.manhattan.edu/~peter.boothe/thesis.pdf

• I am mainly interested in physical networks (say IP layer). Thanks for the link, I will check it. Apr 29 '11 at 4:29
• The IP layer is not the physical layer. MPLS and other circuit-switching technologies break this assumption. The physical layer is the wires. We even have multi-wire links that appear to be single ethernet hops! This question of "what layer" is deeper than first inspection might suggest, and requires careful thought. I suggest that you think of the properties you might want a network to have, find the layer where the topology analysis will best help you analyze that property, and hope that data is available. Apr 29 '11 at 15:43

A very common network model has been proposed by Waxman (1988): choose $n$ vertices in the plane and connect vertices $u$ and $v$ with probability $\beta e^{-d/(L\alpha)}$, where $d$ is their Euclidean distance, and $L$ the maximum distance between any pair of vertices. Zegura et al. (1996) compare Waxman graph to several other network models.

Waxman, Routing of multipoint connections, IEEE J. Select. Areas Commun. 6(9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, How to Model an Internetwork, Proc. IEEE INFOCOM '96, 1996.

Walter Willinger has built a career on the use of scale-free graphs to model networks. There's too much to cite, so I'll point you to his DBLP entry. The key point in these models is that they have properties similar to "real" networks that are not captured by G(n,p).

You might want to check out Durrett's book. I believe you have a lot of reading to do.

Instead of laboriously finding, justifying and analysing a specific model, you might want to use what real life data you have (if you have any). That means defining a generic probabilistic model and training its parameters given your data (e.g. by maximum likelihood estimation).

For example, you can describe an SCFG for trees (e.g. $S \rightarrow p_1 : (S)S \mid p_2 : \varepsilon$) and assign probabilities ($p_1, p_2$) based on relative occurrences in your real life data set, which provably yields an MLE. You can even train probabilities using the inside-outside algorithm. As a bonus, you even have a concise description for your model which can be used in a variety of analyses.

Obviously, the specific grammar can (and should!) use domain knowledge. Consider e.g. different grammars used for RNA secondary structure prediction in Dowell, Eddy (2004) for a taste.

Find some details on this technique in Weinberg, Nebel (2010). I do not know how (well) it can be applied to general graphs, though.

If you need more power you can move to stuff like multidimensional (S)CFG (e.g. Seki, Kato (2008)) or length-/position-dependent SCFG (Weinberg, Nebel (2010)).

• this is cool, but doesn't the context-free nature of SCFG force your learner to neglect certain global structure the networks in your training set might have? Apr 30 '11 at 7:20
• Well, yea, non-context-free features get lost. But note that properties like (average) node degrees can be captured. For more, see my edit. Apr 30 '11 at 10:00
• Thanks! I will take a closer look. Can't Hidden MDPs also capture properties like average degree? That seems like something a regular language should be able to capture, or am I confused? (Also, minor point: the Weinberg, Nebel link has a trailing character that kills the link, it is obvious what link you intended, but if you make more edits it might be worth fixing). May 1 '11 at 10:06
• Sure, I just wanted to point out that you can cover some global characteristics using that model. REG can cover some, too, but will fail to model inherently non-regular structures. (thanks, fixed) May 1 '11 at 14:11

The problem with using Erdos-Renyi random graphs ($G(n,p)$ or $G(n,m)$) is that they follow a Poisson degree distribution, which gives them finite second moment. Many real world graphs, including the "Web graph" or the "Internet Graph", tend to not follow this degree distribution in favor of a degree distribution that has much more variability in it's second moment. In my opinion, one of the biggest differences is the power law degree distribution that many of them have. See Emergence of Scaling in Random Networks for example.

As you probably know, there appears to be a difference between the connectivity graph for the World Wide Web and opposed the connectivity graph for the Internet infrastructure. I certainly don't claim to be an expert, but I've seen Li, Alderson, Tanaka, Doyle and Willinger's paper "Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications" who introduce an 's-metric' to measure the 'scale-freeness' of a graph (with the definition of scale-free graphs still under debate as far as I know) that claim to have a graph model that creates graphs that are similar to the internet connectivity at a router level.

Here are a few more generative models that might be of interest:

Berger, Borgs, Chayes, D'Souza and Kleinberg's paper "Competition-Induced Preferential Attachement"

Carlson and Doyle's Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems

Molloy and Reed's A Critical Point for Random Graphs with a Given Degree Sequence which introduces the "Erased Configuration Model"

Newman's Clustering and preferential attachment in growing networks (which has been mentioned already)

One could also explicitly generate a degree distribution and create a graph this way, but it's unclear to me how close this models the internet graph at a router level.

There is, of course, much more literature on the subject and I've only given a few of (what I consider to be) the highlights.

As far as I understand, many results that worked for the Erdos-Renyi models of random graphs ($G(n,p)$ or $G(n,m)$) do not work precisely because the scale-free or power law degree distributed random graphs diverging second moment in the degree distribution. I don't claim to know enough about to the subject to categorically make claims about "most" proofs, but from what I've seen, one of the first few lines of proofs for properties on Erdos-Renyi random graphs explicitly assumes a finite second moment in the degree distribution. From my point of view, this makes sense as a finite second moment makes Erdos-Renyi graphs much more locally tree-like (see Mertens and Montanari's Information, physics, and computation) which effectively gives properties/paths/structures independence. Since power-law degree distributed random graphs have a diverging second moment, this local tree-like structure is destroyed (and thus requires different proof techniques?). I would be happy to have this intuition invalidated if someone with more knowledge or insight were to show why this is not so.

Hope that helps.

Although it's an old topic I'm replying since there are many people who still visit such posts. I'm motivated from a comment in another reply.

The Barabasi-Albert model and other models that produce scale-free graphs have been proposed to model the Internet at the router level and at the autonomous-system level. Although initially such models where considered accurate it turned out that we do not have a complete image of the Internet topology due to difficulties in discovering all the links. Although it is believed to be heavy tail it is pretty much work in progress.

For your reference you can read: RG Clegg, C Di Cairano-Gilfedder, S Zhou, A critical look at power law modelling of the Internet

There are several books about random graphs, like Bollobás' Book and there are several models of random graphs like small-world wikipedia's link or preferential attachment wikipedia's link, to model networks with small distances between computers or the ones with degree distribution following a power law, respectively.

I think there is no easy way to model a real computer network, but I'm pretty sure that G(n,p) would not model it very well. Unless you are working with a very specific organized network.

My recommendation is the survey paper written by the inventors of the R-MAT random graph generator. http://portal.acm.org/citation.cfm?id=1132954

The R-MAT random graph generator is very simple and widely used. For example, this generator is adopted in the Graph500 benchmark ( http://www.graph500.org/ ).