Náhodný (binomický) graf $G_{n,p}$ má jako parametry $n$ počet vrcholů a $p$ pravděpodobnost každé hrany. Z množiny $\mathcal{G}_n$ všech (číslovaných) grafů velikosti $n$ je každé $G$ vybráno se stejnou pravděpodobností $$\mathbf{Pr}[G] = p^{|E(G)|}(1-p)^{{n \choose 2}-|E(G)|}$$
Náhodný (uniformní) graf $G_{n,m}$ má jako parametry $n$ počet vrcholů a $m$ počet hran. Z množiny $\mathcal{G}_n$ všech (číslovaných) grafů velikosti $n$ každý $G$ je vybrán se stejnou pravděpodobností $$\mathbf{Pr}[G] = {{n \choose 2} \choose m}^{-1}$$ pokud $|E(G)| = m$ a $0$ jinak.
Střední hodnota počtu hran $\langle m \rangle = p \cdot {n \choose 2}$ Střední hodnota stupně vrcholu $\langle k \rangle = \frac{2m}{n} = \frac{2}{n}{n \choose 2} p = p(n - 1)$
$p_k$ je pravděpodobnost, že vrchol náhodného grafu má stupeň právě k. $$p_k = {n - 1 \choose k} p^k (1-p)^{n - 1 - k}$$
Úpravami a za předpokladu $n \gg k$ dostáváme $$p_k = {n - 1 \choose k} p^k (1-p)^{n - 1 - k} = \frac{\langle k \rangle^k}{k!} e^{\langle k \rangle}$$
Komponenta $C$ grafu $G$ je velká (giant) pokud $|C| \sim |V|$.
Věta Pro graf $G = (V,E)$ se středním stupněm $\langle k \rangle$ existuje největší komponenta právě tehdy když $\langle k \rangle > 1$.
Tvrzení Počet velkých komponent řídkého náhodného grafu je 1, neboli pravděpodobnost vzniku dvou a více velkých komponent řídkého náhodného grafu konverguje k 0.
Pozorování Buď $C$ malá komponenta grafu $G_{n,p}$. Potom s vysokou pravděpodobností bude tato komponenta isomorfní stromu.
Tvrzení Náhodný graf $G_{n,p}$ s $m$ hranami nastane se stejnou pravděpodobností jako libovolný graf ze všech ${{n \choose 2} \choose m}$ grafů majících $m$ hran.
Důsledek Modely $G_{n,p}$ s $m$ hranami a $G_{n,m}$ mají stejnou distribuci.
Uvažujeme $G_{n,p}$ s počtem hran $m$, tj. $p = \frac{m}{{n \choose 2}}$. Globální klusterovací coefficient vychází jako $$\frac{\#\text{trojúhelníků}}{\#\text{souvislých trojic}} = \frac{{n\choose 3}p^3}{{n\choose 3}p^2} = p = \frac{\langle k \rangle}{n - 1}$$
Průměr náhodného grafu $\text{diam}(G)$ počítáme pomocí pozorování, že $n = |N(\text{diam}(G)(G))|$, kde $N(\text{diam}(G))$ značí vrcholy ve vzdálenosti nejvýše $\text{diam}(G)$. Spočítáme $|N(\text{diam}(G))| \sim \langle k \rangle^{\text{diam}(G)}$ z čehož $\text{diam}(G) \sim \frac{\ln n}{\ln c}$ kde $c$ je konstanta.
Pro reálnou síť $G = (V,E)$ spočítáme míru small-world vlastnosti následovně: Spočítáme průměrnou délku cesty $L$ a klusterovací koeficient $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)$$ kde $a_{x,y}$ jsou prvky matice sousednosti a $k_u$ stupeň vrcholu $u$.
Generujeme sítě srovnatelné s aktuální neboli $G_{n,p}$ resp. $G_{n,m}$ takový že $m=|E|$. Vygenerujeme dostatečný sample náhodných sítí $G_{n,p}^i$ a z něj stanovíme robustně hodnoty $L_{rand}, C_{rand}$. Vypočteme normovanou průměrnou vzdálenost a normovaný klustering $$\lambda = \frac{L}{L_{rand}}$$ $$\gamma = \frac{C}{C_{rand}}$$
Požadavek small-world vlastnosti jsou krátké cesty $\lambda \gtrsim 1$ a velké klustrování $\gamma \gg 1$. Z toho odvodíme podmínku pro koeficient malého světa $$\sigma = \frac{\gamma}{\lambda} \gg 1$$.
Úlohy:
Budeme uvažovat následující náhodný model. Máme $n$ vrcholů a každá z ${n \choose 3}$ trojic tvoří trojúhelník s pravděpodobností $p = \frac{c}{{n-1 \choose 2}}$, kde $c$ je konstanta.