# What is meant by random graph?

I have read the definitions and basics of random graphs, but I don't really understand what is a random graph, and what's a "non-random" graph. A non mathematical explanation would be of great help.

• What about random graphs don't you understand? – Sycorax Aug 1 '16 at 14:08
• The Wikipedia article has clear answers, such as "A random graph is obtained by starting with a set of $n$ isolated vertices and adding successive edges between them at random." – whuber Aug 1 '16 at 14:42

Let $A01, A02, ... , A20$ be labels of $20$ people in an experiment. In the graph theory labels are equal to nodes. Suppose the $20$ people were allowed to nominate each other, these nominations let be edges.

Figure illustrates the original graph $G$ reflecting the structure of nominations. The graph $G$ is non-random because it was built on nominations.

We can compute different graph statistics, for instance, diameter. It’s seen that the diameter of graph $G$ equal to $6$ because the "longest shortest path" (green on Figure) between members $A15$, $A06$, $A12$, $A19$, $A11$, $A08$ and $A10$ takes $6$ edges.

The simulation of the random graphs can be used to evaluate the significance of the statistics. Based on topological properties (number of nodes, numbers of edges) of the original graph $G$ $1000$ random graphs were generated to compute their average diameter. These $1000$ graphs are random graphs. Btw, in my case the average diameter equals to $6$.

• I wonder what you mean by "diameter." Why don't paths like this qualify? A04-->A18-->A02-->A20-->A01-->A16-->A15-->A14-->A12-->A19-->A07-->A17-->A13 – whuber Aug 1 '16 at 14:51
• @whuber, thanks for the comment, I mean the longest shortest path, mathworld.wolfram.com/GraphDiameter.html – Nick Aug 1 '16 at 15:04
• @Nick, I understand now, so a random graph is just a representation of random variables that have random interactions between them, right? – Toney Shields Aug 1 '16 at 16:07
• @ToneyShields, I think it's the rough definition. What are you meant "random variable"? Nodes or edges? Graph can have a constant topology (numbers of nodes and edges are constant) or a dynamic topology (one or both of numbers of nodes and edges aren't constant). Initially You asked a non mathematical explanation. – Nick Aug 3 '16 at 8:48