Random graphs.html (5564B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="created" content="2018-05-02 10:26:40 +0000"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 23:47:16 +0000"/><title>Random graphs</title></head><body><div>Ok at this point I’m starting to give up on life.</div><div><br/></div><div>Erdos-Renyi graphs (random graphs)</div><ul><li><div>ER(n,p) graph</div></li><li><div>n vertices, random number of edges</div></li><li><div>edge between a pair of vertices exists with probability p</div></li><li><div>small avg shortest path length, low clustering coefficient</div></li><li><div>expected clustering coefficient is p</div></li><ul><li><div>binomial distribution:</div></li><div><img src="Random%20graphs.resources/8C049A47-8053-4383-B73D-45C5A8450E17.png" height="88" width="599"/><br/></div><div>since there are n-1 vertices to link with u.</div></ul><li><div>for large G ∈ ER(n,p) the average shortest path length d̄(G) tends to:</div></li><div><img src="Random%20graphs.resources/86D8B67D-3A40-4F79-9FE1-A57B47D5160A.png" height="86" width="681"/><br/></div><li><div>phase transition around p=1/n — a gigantic connected component appears</div></li></ul><div><br/></div><div>Watts-Strogatz graphs (“small world”)</div><ul><li><div>V = { v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">1</span>, v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">2</span>, v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">3</span>, …, v<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">n</span> }. choose n >> (even k) >> ln(n) >> 1.</div></li><li><div>to build:</div></li><ol><li><div>construct Hn,k</div></li><li><div>consider each edge <u,v></div></li><ul><li><div>with probability p, replace it by <u,w></div></li><li><div>w≠v, w randomly chosen from V \ N(u)</div></li></ul><li><div>result is WS(n,k,p)</div></li></ol><li><div>many vertices will be close to each other</div></li><li><div>weak links are the long ones that cross the ring</div></li><li><div>high clustering coefficients</div></li><ul><li><div>CC(G) ≈ 0.75 for G ∈ WS(n,k,0)</div></li></ul><li><div>average shortest path length for WS(n,k,0)</div></li></ul><div><div style="margin-left: 40px;"> 4 <img src="Random%20graphs.resources/DF249098-9684-4ADE-952B-F1A8382E99EA.png" height="26" width="62"/></div></div><div><br/></div><div>Scale-free networks</div><ul><li><div>very few high-degree vertices</div></li><li><div>degree distribution follows power law</div></li></ul><div style="margin-left: 40px;"><div> 5 <img src="Random%20graphs.resources/0F800A22-FBC7-45A8-B32D-32D8A92992F3.png" height="15" width="315"/></div></div><ul><li><div>function 6 <img src="Random%20graphs.resources/5D352CF8-4A64-4E41-8771-09450DE0373B.png" height="14" width="8"/> is scale-free if 7 <img src="Random%20graphs.resources/51A9CD56-C97F-4547-A52E-55FA145088E8.png" height="15" width="93"/> with C<span style="vertical-align: sub; font-size: smaller; font-size: smaller;">b</span> a constant</div></li><li><div>scale-free function has the same shape everywhere</div></li><li><div>built using growth process with preferential attachment (a new node is more likely to connect to nodes with high degrees)</div></li><li><div>hubs make them vulnerable to targeted attacks</div></li><li><div>example — BA graphs (below)</div></li></ul><div><br/></div><div/><div>Barabasi-Albert graphs (scale-free, dynamical growth, random graphs)</div><ul><li><div>BA(n, n<span style="vertical-align: sub;">0</span>, m)</div></li><li><div>n vertices, m edges</div></li><li><div>start with n<span style="vertical-align: sub;">0</span> nodes at t=0, on every step add node with m (≤ n<span style="vertical-align: sub;">0)</span> edges</div></li></ul><ul><li><div>constructing a graph</div></li><ul><li><div>start with n<span style="vertical-align: sub;">0</span> nodes, no edges</div></li><li><div>while vertices < n</div></li><ol><li><div>add a new node v</div></li><li><div>add edges to all other nodes, each with probability proportional to δ(u)</div></li><li><div>for constant c ≥ 0, add c × m edges between vertices excluding v. probability for each edge <x,y> is proportional to δ(x)×δ(y)</div></li></ol></ul><li><div>P(v is linked to u) = 8 <img src="Random%20graphs.resources/6C2FCE13-B46C-44B2-A78A-F1F128622893.png" height="34" width="139"/></div></li></ul><div><br/></div><ul><li><div>power law distribution:</div></li></ul><div style="margin-left: 40px;"><span style="font-size: 16px;" 9 /><img src="Random%20graphs.resources/1825E72F-ED6D-40A8-A91B-C026E44EA514.png" height="37" width="181"/><br/></div><ul><li><div style="">there’s a bunch of complicated formulas connected to this so I’ll just hope they don’t show up</div></li></ul><ul><li><div>clustering coefficient depends on sequence</div></li><li><div>average shortest path lengths are shorter than ER because of vertices with high degree (“hubs”)</div></li><li><div>tunable clustering — you might add more edges to one node, based on a probability</div></li></ul><div><br/></div></body></html>