Talk:Random graph

Equivalence of G(n,p) and G(n,M)

I corrected the statement the models are interchangable for $M\simeq pn$. The cited source states capital $N$ instead of the number of vertices $n$ in this formula, previously introduced as the maximal possible amount of edges. Also everything else makes no sense, because the decision to add the edge or not is made "the number of possible edges" times and not "number of vertices" times, which would much less... — Preceding unsigned comment added by 131.111.7.91 (talk) 23:05, 7 April 2013 (UTC)

Erdös-Rényi and Gilbert model

Hey guys/girls, I'm quite sure that the original Erdös-Rényi model is the G(n,m) model and the other one was first promoted by Gilbert. What do you think? I'll check tomorrow with my good old Bollobás (the book not the scientist!) :-) Netzwerkerin (talk) 20:19, 18 July 2010 (UTC)

I checked it, changed it and added the source. Netzwerkerin (talk) 09:33, 24 July 2010 (UTC)

I'm linking here from quantifier elimination, but there random graph seems to have somewhat different meaning: it's the graph which contains every finite graph as a subgraph or something like that. I would expect that there is a correlation between them, but these do not seem to be entirely identical notions. Anyone has insight into this? I hope to check this at some point. -- vkuncak

Oh yes vkuncak: on the one hand *THE* random graph is certain specific (unique up to isomorphism) graph with an infinite number (more specifically $\aleph _{0}$) of vertices, on the other hand (informally) *A* random graph is a graph generated by some random process. More formally, it is any graph when viewed as a point in some probability space... in this latter view it's more common to talk about *random graphs* in plural, like in "random graphs have diameter 2"... however, most specialist would say "almost every graph have diameter 2" instead.

There is a very nice *equivalence* (so to speak, under certain restrictions) of both pictures, thanks to a marvelous theorem discovered independently by Fagin (on the one hand) and Glebskii, Kogan, Liogon and Talanov (on the other). In my opinion, the best source for this theorem is the excellent book by Joel Spencer "The Strange Logic of Random Graphs"... needless to say this is not but the tip of the iceberg. Xaman 23:32, 3 May 2006 (UTC)

What does percolation have to do with random graphs ?

And why is there a "blah blah blah etc." ? Is this a case of vandalism ? I'm writing this on 29-4-2006. I'll wait for a couple of months and if the percolation part has not been explained by then, I'll erase it.

29-6-2006: I'm glad to see that the "blah blah" part has been erased but the reference to percolation has not been explained. I've read the article on "percolation" and although some things mentioned there do have a graph structure no connection is mentioned or is obvious specifically with random graphs. A lot of things have a graph structure and there's no more reason for percolation to be there than for dozens of other things. So I'm erasing the reference to it. I'll check again in the future to see if anyone objects.

04-11-2006: Percolation indeed has to do with random graphs. Suppose the graph grows with small-sized edges in something solid. What's the probability of any vertex touching the other side of the solid wall? That's percolation. And that's also r.g.62.118.128.63 01:12, 4 November 2006 (UTC)

Erdos-Renyi model

Is the Erdos-Renyi model related to random graphs? It would be great if the Erdos-Renyi model article would be created, as there are a bunch of articles which link to it. Oleg Alexandrov (talk) 16:45, 28 January 2007 (UTC)

visualizations

What this page really needs are some visualizations of random graphs versus other more organized graphs. You can see the difference when you look at them. Pwoolf (talk) 19:18, 8 May 2008 (UTC)

Snapshots

The text says that an Erdos-Renyi graph is a snapshot of the "random graph process" at a particular time. It seems to me that it is a snapshot at a (binomially-distributed?) random time. Is that correct? LachlanA (talk) 21:15, 13 June 2008 (UTC)

The article says: "Both models can be viewed as snapshots at a particular time of the random graph process , which is a stochastic process that starts with n vertices and no edges and at each step adds one new edge chosen uniformly from the set of missing edges." There is a problem with this sentence. For example, consider the Erdos-Renyi model G(n,p) and consider a fixed triangle in K_n. The probability that our fixed triangle will appear in G(n,p) is exactly p^3. Now consider the random process above. Suppose also that you stop adding edges to the random process once you've added a fraction of p of all possible edges. Then in general, it is not true that our fixed triangle will appear in the final random graph with probability p^3 (although our fixed triangle will appear with probability very close to p^3 for many values of p). I do agree however that the random graph G(n,M) can be viewed as a form of the above random process. So, to sum things up, G(n,M) can be viewed as the above random process, while G(n,p) can not. —Preceding unsigned comment added by 132.74.1.4 (talk) 12:02, 18 September 2008 (UTC)

Other models?

In the language of probability it is customary to call "random object $X$ of the set $S$" any measurable map $X:\Omega \to S$, from a base probability space $\textstyle (\Omega ,{\mathcal {F}},P)$ to $S$ (once a sigma algebra has been fixed in $S$). According to this, I would expect that "random graph", say with (possibly infinite) vertex set $V$, in the most general meaning should refer to any measurable map $X:\Omega \to 2^{K}$, where $K$ is the set of all unordered pairs of $V$, and of course, the power set $2^{K}$ is equipped with the product sigma algebra. In other words, in this wider definition any probability distribution of edges is allowed, not assuming independency of edges, nor that they are i.d., like e.g. in the Erdos-Renyi model. I am not a probabilist, and I wonder if random graphs are studied in this generality...Thanks. PMajer79.38.22.37 (talk) 17:47, 16 October 2008 (UTC)

Ameen Nawaz Khan

#REDIRECT Strike-through text

---

--116.71.49.85 (talk) 09:21, 18 August 2009 (UTC)<math>Insert non-formatted text here</math>[[Media:[[File:Example.ogg]][http://www.example.com link title]]]

Why interdependent graphs?

I do not understand how the section "Interdependent Graphs" fits on the "Random graph" page. Why this is relevant to random graphs? 128.194.239.166 (talk) 21:44, 26 November 2012 (UTC)Austin B.

I took it out. If someone comes here with a good argument of why it is relevant, we can reconsider. McKay (talk) 05:39, 6 May 2013 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Random graph/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

The "Properties of random graphs" section needs to be expanded to say much more about the main results known for random graphs. The article could also do with some discussion of pseudorandom/quasirandom graphs, and should mention the random graph models used to generate small-world networks / scale-free networks (with links to those articles for more detail). Joseph Myers 01:19, 21 May 2007 (UTC)

Last edited at 01:19, 21 May 2007 (UTC). Substituted at 20:12, 1 May 2016 (UTC)