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

<p>"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 - <a href="http://home.manhattan.edu/~peter.boothe/thesis.pdf">http://home.manhattan.edu/~peter.boothe/thesis.pdf</a></p>

CC BY-SA 3.0
2011-04-29T04:29:33.127Z
I am mainly interested in physical networks (say IP layer). Thanks for the link, I will check it.
Kaveh
CC BY-SA 3.0
2011-04-29T15:43:30.607Z
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.
Peter Boothe
CC BY-SA 3.0
2011-04-29T03:38:24.793Z
2011-04-29T15:39:57.367Z
2011-04-29T15:39:57.367Z
Peter Boothe
<p>This survey, <a href="http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf">The structure and function of complex networks</a> 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, <a href="http://www.santafe.edu/media/workingpapers/02-02-005.pdf">Random graphs as models of networks</a>, about adaptations of random graphs to model real networks.</p>

<p>References:</p>

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

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

CC BY-SA 3.0
2011-04-29T00:57:11.277Z
just curious: is this for "social" networks vs the internet ?
Suresh Venkat
CC BY-SA 3.0
2011-04-29T06:14:08.277Z
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
Elliot JJ
CC BY-SA 3.0
2011-04-29T07:58:34.233Z
@Suresh, those complex networks covered in both references include computer networks such as the Internet and social networks.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-28T23:04:09.243Z
2011-04-29T08:10:00.950Z
2011-04-29T08:10:00.950Z
Mohammad Al-Turkistany
<p>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.</p>

<p>Waxman, <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&amp;arnumber=12889"><em>Routing of multipoint connections</em></a>, IEEE J. Select. Areas Commun. 6(9), 1617-1622, 1988.
Zegura, Calvert, Bhattacharjee, <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&amp;arnumber=493353"><em>How to Model an Internetwork</em></a>, Proc. IEEE INFOCOM '96, 1996.</p>

CC BY-SA 3.0
2011-04-28T22:37:13.577Z
2011-04-28T22:37:13.577Z
Marcus Ritt
<p>You might want to check out <a href="http://www.math.cornell.edu/~durrett/RGD/RGD.html">Durrett's book</a>.  I believe you have a lot of reading to do.</p>

CC BY-SA 3.0
2011-04-29T11:04:18.543Z
2011-04-29T11:04:18.543Z
RJK
<p>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).</p>

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

<p>Obviously, the specific grammar can (and should!) use domain knowledge. Consider e.g. different grammars used for RNA secondary structure prediction in <a href="http://www.biomedcentral.com/1471-2105/5/71" rel="nofollow">Dowell, Eddy (2004)</a> for a taste.</p>

<p>Find some details on this technique in <a href="http://wwwagak.informatik.uni-kl.de/staff/nebel/www_nonuniform_random/NonUniformRandomGeneration.pdf" rel="nofollow">Weinberg, Nebel (2010)</a>. I do not know how (well) it can be applied to general graphs, though.</p>

<p>If you need more power you can move to stuff like multidimensional (S)CFG (e.g. <a href="http://portal.acm.org/citation.cfm?id=1522686" rel="nofollow">Seki, Kato (2008)</a>) or length-/position-dependent SCFG (<a href="http://wwwagak.informatik.uni-kl.de/research/publications/www_lSCFG/lscfg.pdf" rel="nofollow">Weinberg, Nebel (2010)</a>).</p>

CC BY-SA 3.0
2011-04-30T07:20:58.293Z
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?
Artem Kaznatcheev
CC BY-SA 3.0
2011-04-30T10:00:44.427Z
Well, yea, non-context-free features get lost. But note that properties like (average) node degrees can be captured. For more, see my edit.
Raphael
CC BY-SA 3.0
2011-05-01T10:06:41.797Z
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).
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-01T14:11:50.023Z
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)
Raphael
CC BY-SA 3.0
2011-04-29T17:29:10.597Z
2011-05-01T14:09:18.107Z
2011-05-01T14:09:18.107Z
Raphael
<p>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 <a href="http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Willinger%3aWalter.html">his DBLP entry</a>. The key point in these models is that they have properties similar to "real" networks that are not captured by G(n,p). </p>

CC BY-SA 3.0
2011-04-28T22:52:47.310Z
2011-04-28T22:52:47.310Z
Suresh Venkat
<p>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 <a href="http://www.barabasilab.com/pubs/CCNR-ALB_Publications/199910-15_Science-Emergence/199910-15_Science-Emergence.pdf" rel="nofollow">Emergence of Scaling in Random Networks</a> for example.</p>

<p>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 <a href="http://arxiv.org/pdf/cond-mat/0501169" rel="nofollow">"Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications"</a> who introduce an 's-metric' to measure the 'scale-freeness' of a graph (with the definition of <a href="http://en.wikipedia.org/wiki/Scale-free_network" rel="nofollow">scale-free graphs</a> 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.</p>

<p>Here are a few more generative models that might be of interest:</p>

<p>Berger, Borgs, Chayes, D'Souza and Kleinberg's paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.9405&amp;rep=rep1&amp;type=pdf" rel="nofollow">"Competition-Induced Preferential Attachement"</a> </p>

<p>Carlson and Doyle's <a href="http://www.cds.caltech.edu/~doyle/CmplxNets/PRE01412.pdf" rel="nofollow">Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems</a></p>

<p>Molloy and Reed's <a href="http://www.cs.toronto.edu/~molloy/webpapers/gc2.ps" rel="nofollow">A Critical Point for Random Graphs with a Given Degree Sequence</a> which introduces the "Erased Configuration Model"</p>

<p>Newman's <a href="http://arxiv.org/pdf/cond-mat/0104209" rel="nofollow">Clustering and preferential attachment in growing networks</a> (which has been mentioned already)</p>

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

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

<p>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 <a href="http://www.ens-lyon.fr/PHYSIQUE/Peyresq08/documents/Mezard_Peyresq.pdf" rel="nofollow">Information, physics, and computation</a>) 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.</p>

<p>Hope that helps.</p>

CC BY-SA 3.0
2011-05-01T23:01:06.513Z
2011-05-01T23:01:06.513Z
user834
<p>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.</p>

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

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

CC BY-SA 3.0
2013-01-18T16:36:30.170Z
2013-01-18T16:36:30.170Z
Vasilis
<p>There are several books about random graphs, like Bollobás' Book and there are several models of random graphs like small-world <a href="http://en.wikipedia.org/wiki/Small-world_network" rel="nofollow">wikipedia's link</a> or preferential attachment <a href="http://en.wikipedia.org/wiki/Scale-free_network" rel="nofollow">wikipedia's link</a>, to model networks with small distances between computers or the ones with degree distribution following a power law, respectively.</p>

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

CC BY-SA 3.0
2011-04-30T13:06:33.373Z
2011-04-30T13:06:33.373Z
dpufrj
<p>My recommendation is the survey paper written by the inventors of the R-MAT random graph generator.  <a href="http://portal.acm.org/citation.cfm?id=1132954" rel="nofollow">http://portal.acm.org/citation.cfm?id=1132954</a></p>

<p>The R-MAT random graph generator is very simple and widely used.  For example, this generator is adopted in the Graph500 benchmark ( <a href="http://www.graph500.org/" rel="nofollow">http://www.graph500.org/</a> ).</p>

CC BY-SA 3.0
2011-04-30T13:25:53.323Z
2011-04-30T13:38:57.967Z
2011-04-30T13:38:57.967Z
Snowie
<p>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. </p>

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

<p>For a definitive reference, see the papers by <a href="http://www.mpi-inf.mpg.de/~kpanagio/">Konstantinos Panagiotou</a> and the citations contained therein. For convenience, here is a small sample of some relevant papers :</p>

<ul>
<li><a href="http://www.mpi-inf.mpg.de/~kpanagio/DegreeSequencePlanar.pdf"><strong>On the Degree Distribution of Random Planar Graphs</strong></a>. <em>Konstantinos Panagiotou and Angelika Steger</em>. To appear in the Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11).</li>
<li><strong>On Properties of Random Dissections and Triangulations</strong>. <em>Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger</em>. 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]</li>
<li><strong>On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs</strong>. <em>Nicla Bernasconi, Konstantinos Panagiotou and Angelika Steger</em>. 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]</li>
</ul>

CC BY-SA 3.0
2011-04-29T13:17:04.673Z
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
CC BY-SA 3.0
2011-04-29T03:48:19.200Z
2011-04-29T03:48:19.200Z
Max
<p>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?).</p>

<blockquote>
  <p>what models of random graphs are useful for understanding computer networks araising in practice?</p>
</blockquote>

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

CC BY-SA 3.0
2011-04-29T04:34:24.433Z
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?
Jukka Suomela
CC BY-SA 3.0
2011-04-29T04:55:08.440Z
@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 :).
Kaveh
CC BY-SA 3.0
2011-04-29T04:55:43.430Z
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.
Kaveh
CC BY-SA 3.0
2011-05-05T00:01:36.967Z
Thanks everyone for nice answers. (Now I have to spent sometime reading these papers. :)
Kaveh
<reference-request><graph-theory><co.combinatorics>
Models of random graphs, for real computer networks
Kaveh
# Models of random graphs, for real computer networks

(Asked by: username_0 on 2011-04-28)

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

**Tags:** reference-request, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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 :).  
> **username_0**: 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.  
> **username_0**: Thanks everyone for nice answers. (Now I have to spent sometime reading these papers. :)  

---

## 11 answers

### Answer by username_14 on 2011-04-29. Score: 10 | Accepted answer

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](http://www.mpi-inf.mpg.de/~kpanagio/) and the citations contained therein. For convenience, here is a small sample of some relevant papers :

* [**On the Degree Distribution of Random Planar Graphs**](http://www.mpi-inf.mpg.de/~kpanagio/DegreeSequencePlanar.pdf). *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]

> **Comments:**
> **username_7**: 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).  

---

### Answer by username_3 on 2011-04-28. Score: 10

This survey, [The structure and function of complex networks](http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf) 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](http://www.santafe.edu/media/workingpapers/02-02-005.pdf), 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)

> **Comments:**
> **username_4**: just curious: is this for "social" networks vs the internet ?  
> **username_5**: 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  
> **username_3**: @Suresh, those complex networks covered in both references include computer networks such as the Internet and social networks.  

---

### Answer by username_2 on 2011-04-29. Score: 8

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>

> **Comments:**
> **username_0**: I am mainly interested in physical networks (say IP layer). Thanks for the link, I will check it.  
> **username_2**: 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.  

---

### Answer by username_6 on 2011-04-28. Score: 7

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*](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&arnumber=12889), IEEE J. Select. Areas Commun. 6(9), 1617-1622, 1988.
Zegura, Calvert, Bhattacharjee, [*How to Model an Internetwork*](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&arnumber=493353), Proc. IEEE INFOCOM '96, 1996.


---

### Answer by username_7 on 2011-04-29. Score: 5

You might want to check out [Durrett's book](http://www.math.cornell.edu/~durrett/RGD/RGD.html). I believe you have a lot of reading to do.


---

### Answer by username_8 on 2011-04-29. Score: 5

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)](http://www.biomedcentral.com/1471-2105/5/71) for a taste.

Find some details on this technique in [Weinberg, Nebel (2010)](http://wwwagak.informatik.uni-kl.de/staff/nebel/www_nonuniform_random/NonUniformRandomGeneration.pdf). 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)](http://portal.acm.org/citation.cfm?id=1522686)) or length-/position-dependent SCFG ([Weinberg, Nebel (2010)](http://wwwagak.informatik.uni-kl.de/research/publications/www_lSCFG/lscfg.pdf)).

> **Comments:**
> **username_9**: 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?  
> **username_8**: Well, yea, non-context-free features get lost. But note that properties like (average) node degrees can be captured. For more, see my edit.  
> **username_9**: 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).  
> **username_8**: 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)  

---

### Answer by username_4 on 2011-04-28. Score: 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](http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Willinger%3aWalter.html). The key point in these models is that they have properties similar to "real" networks that are not captured by G(n,p).


---

### Answer by username_10 on 2011-05-01. Score: 3

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](http://www.barabasilab.com/pubs/CCNR-ALB_Publications/199910-15_Science-Emergence/199910-15_Science-Emergence.pdf) 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"](http://arxiv.org/pdf/cond-mat/0501169) who introduce an 's-metric' to measure the 'scale-freeness' of a graph (with the definition of [scale-free graphs](http://en.wikipedia.org/wiki/Scale-free_network) 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"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.9405&rep=rep1&type=pdf)

Carlson and Doyle's [Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems](http://www.cds.caltech.edu/~doyle/CmplxNets/PRE01412.pdf)

Molloy and Reed's [A Critical Point for Random Graphs with a Given Degree Sequence](http://www.cs.toronto.edu/~molloy/webpapers/gc2.ps) which introduces the "Erased Configuration Model"

Newman's [Clustering and preferential attachment in growing networks](http://arxiv.org/pdf/cond-mat/0104209) (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](http://www.ens-lyon.fr/PHYSIQUE/Peyresq08/documents/Mezard_Peyresq.pdf)) 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 by username_11 on 2013-01-18. Score: 3

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 by username_12 on 2011-04-30. Score: 2

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](http://en.wikipedia.org/wiki/Small-world_network) or preferential attachment [wikipedia's link](http://en.wikipedia.org/wiki/Scale-free_network), 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 by username_13 on 2011-04-30. Score: 2

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


---

