Random (binomial) graph $G_{n,p}$ has as its parameters $n$ the number of vertices and $p$ the probability of each edge. From the set $\mathcal{G}_n$ of all (labelled) graphs of order $n$ is each graph $G$ chosen with the same probability. $$\mathbf{Pr}[G] = p^{|E(G)|}(1-p)^{{n \choose 2}-|E(G)|}$$
Random (uniform) graph $G_{n,m}$ has parameters $n$ giving the number of vertices and $m$ giving the number of edges. From the set $\mathcal{G}_n$ of all (labelled) graphs of size $n$, each is chosen with equal probability $$\mathbf{Pr}[G] = {{n \choose 2} \choose m}^{-1}$$ if $|E(G)| = m$ and $0$ otherwise.
Expected number of edges $\langle m \rangle = p \cdot {n \choose 2}$ Mean degree of a vertex $\langle k \rangle = \frac{2m}{n} = \frac{2}{n}{n \choose 2} p = p(n - 1)$ We can use this to express the probability in terms of mean degree: $p = \frac{\langle k \rangle}{(n-1)}$.
$p_k$ is probability that given vertex of a random graph has degree exactly $k$. $$p_k = {n - 1 \choose k} p^k (1-p)^{n - 1 - k}$$
By manipulations with this expressions and assuming $n \gg k$ we obtain $$p_k = {n - 1 \choose k} p^k (1-p)^{n - 1 - k} = \frac{\langle k \rangle^k}{k!} e^{\langle k \rangle}$$
Component $C$ of a graph $G$ is giant if $|C| \sim |V|$.
Theorem For a graph $G = (V,E)$ with mean degree $\langle k \rangle$ exists giant component if and only if $\langle k \rangle > 1$.
Proposition The number of components of a sparse graph is one. In other words, the probability of creation of two or more giant components in a sparse graph converges to zero.
Observation Let $C$ be a small component of a graph $G_{n,p}$. Then with high probability this component will be isomorphic to a tree.
Proposition Random graph $G_{n,p}$ with $m$ edges occurs with the same probability as any graph from all ${{n \choose 2} \choose m}$ graphs having $m$ edges.
Corollary Models $G_{n,p}$ with $m$ edges and $G_{n,m}$ have the same probability distribution.
Consider $G_{n,p}$ with $m$ edges, i.e. $p = \frac{m}{{n \choose 2}}$. Global clustering coefficient is then $$\frac{\#\text{triangles}}{\#\text{connected triples}} = \frac{{n\choose 3}p^3}{{n\choose 3}p^2} = p = \frac{\langle k \rangle}{n - 1}$$
Diameter of a random graph $\text{diam}(G)$ can be computed using the observation that $n = |N(\text{diam}(G))|$, where $N(\text{diam}(G))$ denotes vertices in distance at most $\text{diam}(G)$. We count $|N(\text{diam}(G))| \sim \langle k \rangle^{\text{diam}(G)}$ from which
$\text{diam}(G) \sim \frac{\ln n}{\ln c}$ where $c$ is a constant.
For real network $G = (V,E)$ we express the level of small-world property as follows: We count the average path length $L$ and the clustering coeficient $C$ $$L = \frac{1}{n(n-1)}$$ $$C = \sum_{u\in V(G)} \left(\sum_{v,w\neq u} \frac{a_{u,v}a_{v,w}a_{w,u}}{k_u(k_u - 1)} \right)$$ where $a_{x,y}$ are elements of the adjacency matrix and $k_u$ is degree of vertex $u$.
We generate networks comparable with our network in hand, so $G_{n,p}$ respectively $G_{n,m}$ such that $m=|E|$. After generating sample big enough $G_{n,p}^i$, we use them to robustly compute values $L_{rand}, C_{rand}$. We compute the normalized average distance and normalized clustering $$\lambda = \frac{L}{L_{rand}}$$ $$\gamma = \frac{C}{C_{rand}}$$
Graph has the small-world property if the paths are short $\lambda \gtrsim 1$ and the clustering is big $\gamma \gg 1$. From this we conclude the condition for small-world coefficient $$\sigma = \frac{\gamma}{\lambda} \gg 1.$$
A graph property $\mathcal{P}$ is a subset of the set od all labelled graphs over the set $\{1, \dots, n\}$, i.e. $\mathcal{P} \subseteq 2^{{V \choose 2}}$.
Monotone (increasing) property is a property $\mathcal{P}$ for which it holds $\forall e\in {n \choose 2} ~ G \in \mathcal{P} \Rightarrow G + e \in \mathcal{P}$.
Lemma: Let $\mathcal{P}$ be monotone increasing graph property and $0 \leq p_1 < p_2 \leq 1$. Furthermore let $G_i = G(n,p_i)~i=1,2$. Then $$\mathbb{P}[G_1 \in \mathcal{P}] \leq \mathbb{P}[G_2 \in \mathcal{P}].$$
Lemma: Let $\mathcal{P}$ be a graph property and $p = \frac{m}{{n \choose 2}}$, where $m=m(n)\rightarrow\infty$ a ${n\choose 2} - m\rightarrow\infty$. Then for large $n$, $$\mathbb{P}[G(n,m) \in \mathcal{P}] \leq \sqrt{2\pi m}\mathbb{P}[G(n,p) \in \mathcal{P}].$$
Lemma: Let $\mathcal{P}$ be monotone increasing graph property and $p = \frac{m}{N}$, where $N = {n \choose 2}$. Then for large $n$ and $p$ such that $Np$, $N(1-p)/\sqrt{Np} \rightarrow \infty$ we have $$\mathbb{P}[G(n,m) \in \mathcal{P}] \leq 3\mathbb{P}[G(n,p) \in \mathcal{P}].$$
Function $p^* = p^*(n)$ is a threshold for an increasing graph property $\mathcal{P}$ in a random graph $G(n,p)$ if $$\lim_{n\rightarrow\infty}\mathbb{P}[G(n,p) \in \mathcal{P}] = \begin{cases} 0 & \text{ if } p/p^* \rightarrow 0\\ 1 & \text{ if } p/p^* \rightarrow \infty \end{cases}$$
Markov inequality Let $X$ be nonnegative random variable. Then for all $t > 0$ it holds $$\mathbb{P}[X \geq t] \leq \frac{\mathbb{E}[X]}{t}.$$
First moment method Let $X$ be nonnegative random integer variable. Then $$\mathbb{P}[X > 0] \leq \mathbb{E}[X].$$
Chebyshev inequality Let $X$ be random variable with finite expectation and variance. Then for $t > 0$ it holds $$\mathbb{P}[|X -\mathbb{E}[X]|\geq t] \leq \frac{\text{Var}(X)}{t^2}.$$
Second moment method Let $X$ be nonnegative random integer variable. Then $$\mathbb{P}[X = 0] \leq \frac{\text{Var} X}{(\mathbb{E}[X])^2} = \frac{\mathbb{E}[X^2]}{(\mathbb{E}[X])^2} - 1.$$
Lemma: Let $\mathcal{P}$ be a graph property claiming that the graph $G$ contains at least one edge. Then $$\lim_{n\rightarrow\infty}\mathbb{P}[G(n,p) \in \mathcal{P}] = \begin{cases} 0 & \text{ if } p \gg n^{-2}\\ 1 & \text{ if } p \ll n^{-2} \end{cases}$$
We say that a sequence of events $\mathcal{X}_n$ occurs asymptotically almost surely if it occurs with probability $1 - o(1)$ or equivalently, $$\lim_{n\rightarrow\infty}\mathbb{P}[\mathcal{X}_n] = 1.$$
Theorem: If $m/n\rightarrow\infty$ then asymptotiacally almost surely $G(n,m)$ contains at least one triangle.
Task 1: For random binomial graph $G_{n,p}$ and fixed vertices $1, 2, \dots, 5$ express the probability that these vertices form a wheel
Task 2: Let us have $G_{n,m}$ with $n = 4$ and $m = 3$. What is the probability that such graph contains a triangle?
Task 3: We say that a graph has an Eulerian cycle if there exists a walk containing every edge of the graph exactly once. We say that a graph has an Eulerian trail if there exists a walk containing every edge of the graph exactly once. Decide if having an
is a monotone increasing graph property.
Task 4: Suppose we have a random model where instead of connecting any of the ${n \choose 2}$ pairs of vertices by an edge with probability $p$, we connect any of the ${n \choose 3}$ triples of vertices into a triangle with probability $p = \frac{c}{{n-1 \choose 2}}$. Show that the mean degree of a vertex in the resulting multigraph is $2c$.