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.
 A: 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$.
A: I think it's easier to understand if you understand what a random variable is. Intuitively, a random variable is an object that can take different states and each state takes a particular value.
A very simple example is the Bernoulli random variable:
$$
X = \begin{cases}
1 \text{ if } success \\
0 \text{ otherwise} 
\end{cases}
$$
Now we can apply the same reasoning to graphs, by thinking of a graph as an object that has different possible states. The different states of the graph object refer to different possible links between it's vertices. It's easier to understand if you look at the adjacency matrix representation of a graph. For example, a graph of three nodes can have $0,1,2$ edges in various combinations.
$$
Y = \begin{cases}
\begin{pmatrix}
000\\
000\\
000
\end{pmatrix}
\text{ if there are no edges between the nodes } \\
\begin{pmatrix}
010\\
000\\
000
\end{pmatrix}
\text{ if there is one edges between node 1 and 2 } \\
\begin{pmatrix}
001\\
000\\
000
\end{pmatrix}
\text{ if there is one edges between node 1 and 3 } \\
\quad \ \ \vdots \\
\begin{pmatrix}
011\\
101\\
110
\end{pmatrix}
\text{ if there are all possible connections } \\
\end{cases}
$$
Thus we can consider the graph as an object that has different possible states. What we gained with this perspective is the ability to assign probabilities to each state. This in turn allows us to answer questions such as: how likely is a particular realization $Y = y$ of the graph? In probability notation:
$$
\mathbb{P}(Y = y) = ?
$$
or a concrete example:
$$
\mathbb{P}(Y = \begin{pmatrix}
001\\
000\\
000
\end{pmatrix}
) = ?
$$
To sum it up, a particular (your observed) graph is one realization of many possible graphs with the same number of vertices. The set of all possible realization can be considered a random variable to which we can assigns probabilities to it's various states, hence a random graph. It's really just a different perspective of looking at the same thing.
