Random graphs.md (2833B)
1 +++ 2 title = 'Random graphs' 3 template = 'page-math.html' 4 +++ 5 # Random graphs 6 Ok at this point I’m starting to give up on life. 7 8 Erdos-Renyi graphs (random graphs) 9 10 - ER(n,p) graph 11 - n vertices, random number of edges 12 - edge between a pair of vertices exists with probability p 13 - small avg shortest path length, low clustering coefficient 14 - expected clustering coefficient is p 15 - binomial distribution: 16 17 $P[\delta (u) = k] = \binom{n-1}{K} p^k (1-p)^{n-1-k}$ 18 19 since there are n-1 vertices to link with u. 20 21 - for large G ∈ ER(n,p) the average shortest path length d̄(G) tends to: 22 23 $\frac{\ln{n} - \gamma}{\ln{\delta}} + 0.5 \qquad \gamma \approx 0.5572$ 24 25 - phase transition around p=1/n — a gigantic connected component appears 26 27 Watts-Strogatz graphs (“small world”) 28 29 - V = { v1, v2, v3, …, vn }. choose n >> (even k) >> ln(n) >> 1. 30 - to build: 31 32 1. construct Hn,k 33 2. consider each edge \<u,v> 34 35 - with probability p, replace it by \<u,w> 36 - w≠v, w randomly chosen from V \ N(u) 37 38 3. result is WS(n,k,p) 39 40 - many vertices will be close to each other 41 - weak links are the long ones that cross the ring 42 - high clustering coefficients 43 - CC(G) ≈ 0.75 for G ∈ WS(n,k,0) 44 - average shortest path length for WS(n,k,0) 45 46 $\hat{d}(u) \approx \frac{n}{2k}$ 47 48 Scale-free networks 49 50 - very few high-degree vertices 51 - degree distribution follows power law 52 53 $P[\delta (u) = k] \alpha ∝ k^{-a}$ (usually 2 < a < 3) 54 55 - function $f$ is scale-free if $f(bx) = C_{b} f(x)$ with Cb a constant 56 - scale-free function has the same shape everywhere 57 - built using growth process with preferential attachment (a new node is more likely to connect to nodes with high degrees) 58 - hubs make them vulnerable to targeted attacks 59 - example — BA graphs (below) 60 61 Barabasi-Albert graphs (scale-free, dynamical growth, random graphs) 62 63 - BA(n, n0, m) 64 - n vertices, m edges 65 - start with n0 nodes at t=0, on every step add node with m (≤ n0) edges 66 - constructing a graph 67 - start with n0 nodes, no edges 68 - while vertices < n 69 70 1. add a new node v 71 72 2. add edges to all other nodes, each with probability proportional to δ(u) 73 74 3. for constant c ≥ 0, add c × m edges between vertices excluding v. probability for each edge <x,y> is proportional to δ(x)×δ(y) 75 76 - P(v is linked to u) = $\frac{\delta (u)}{\text{sum } \delta (\text{all other nodes})}$ 77 78 - power law distribution: 79 80 $P[\delta (u) = k] = \frac{2m^2}{k^3} \propto k^{-3}$ 81 82 - there’s a bunch of complicated formulas connected to this so I’ll just hope they don’t show up 83 - clustering coefficient depends on sequence 84 - average shortest path lengths are shorter than ER because of vertices with high degree (“hubs”) 85 - tunable clustering — you might add more edges to one node, based on a probability