2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What about random graphs don't you understand? $\endgroup$ – Sycorax Aug 1 '16 at 14:08
  • 2
    $\begingroup$ 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." $\endgroup$ – whuber Aug 1 '16 at 14:42
2
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – whuber Aug 1 '16 at 14:51
  • 1
    $\begingroup$ @whuber, thanks for the comment, I mean the longest shortest path, mathworld.wolfram.com/GraphDiameter.html $\endgroup$ – Nick Aug 1 '16 at 15:04
  • $\begingroup$ @Nick, I understand now, so a random graph is just a representation of random variables that have random interactions between them, right? $\endgroup$ – Toney Shields Aug 1 '16 at 16:07
  • $\begingroup$ @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. $\endgroup$ – Nick Aug 3 '16 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.