Models of random graphs, for real computer networks

Question

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.)

Answer 1

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]

Answer 2

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)

Answer 3

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

Answer 4

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.

Answer 5

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).

Answer 6

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

Answer 7

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)).

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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/ ).