Network analysis.html (4244B)
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="altitude" content="278"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-09 14:35:10 +0000"/><meta name="latitude" content="50.11335669646521"/><meta name="longitude" content="14.33736782997098"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 23:29:54 +0000"/><title>Network analysis</title></head><body><div>Distribution of vertex degrees: vertices with high respectively low degree</div><div><div><br/></div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 222px;"/><col style="width: 301px;"/></colgroup><tbody><tr><td style="border: 1px solid rgb(219, 219, 219); width: 222px; padding: 8px;"><div style="text-align: center;">Histogram</div><div style="text-align: center;"><br/></div><div style="text-align: center; "><img src="Network%20analysis.resources/screenshot_1.png" height="358" width="438"/><br/></div></td><td style="border: 1px solid rgb(219, 219, 219); width: 301px; padding: 8px;"><div style="text-align: center;">Ranked histogram</div><div style="text-align: center;"><br/></div><div style="text-align: center; "><img src="Network%20analysis.resources/screenshot.png" height="309" width="521"/><br/></div></td></tr></tbody></table><div><br/></div></div><div>Distance stats:</div><ul><li><div>d(u,v) — shortest distance between u and v</div></li><li><div>ε(u) — eccentricity. longest shortest path from u and to any other vertices</div></li><li><div>rad(G) — radius. minimum eccentricity</div></li><li><div>diam(G) — diameter. longest path in graph.</div></li><li><div>d̄(u) — average length of shortest paths from u to any other v. </div></li><li><div>d̄(G) — average path length (average of all d̄(u))</div></li><li><div>characteristic path length — median over all d̄(u)<br/></div></li></ul><div><br/></div><div>clustering coefficient (<a href="https://www.youtube.com/watch?v=K2WF4pT5pFY">good video</a>)</div><ul><li><div>clustering — when many neighbours of vertex are also each other’s neighbours</div></li><li><div>defined by:</div></li></ul><div style="margin-left: 40px;"><span style="font-size: 18px;" 4 /><img src="Network%20analysis.resources/BBFD0505-29B9-4E47-BCAA-82EE9A5F398E.png" height="42" width="195"/></div><div style="margin-left: 40px;">where m<sub>v</sub> is number of links between neighbours of v.</div><div><br/></div><ul><li><div>for triangles:</div></li><ul><li><div>triangle is complete subgraph of 3 vertices</div></li><li><div>triple is subgraph of 3 vertices and 2 edges</div></li><li><div>network transitivity τ(G) = n<span style="vertical-align: sub;">Δ</span>(G) / n<span style="vertical-align: sub;">triple</span>(G)</div></li><ul><li><div>n<span style="vertical-align: sub;">Δ</span>(v) — number of triangles of which v is a member</div></li><li><div>n<span style="vertical-align: sub;">triple</span>(v) — number of triples at v (<span style="font-style: italic;">v</span> is incident to both edges)</div></li><li><div>essentially the same as clustering coefficient, but for whole graph</div></li></ul></ul></ul><div><br/></div><div>Centrality:</div><ul><li><div>center C(G) is set of vertices with min eccentricity</div></li><li><div>vertex centrality of u c<span style="vertical-align: sub;">E</span>(u) = 1 / ε(u)</div></li><li><div>betweenness centrality of u c<span style="vertical-align: sub;">B</span>(u) = sum |S(x,u,y)| / |S(x,y)| for x≠u≠y</div></li><ul><li><div>S(x,y) — set of shortest paths between x and y</div></li><li><div>S(x,u,y) — shortest paths passing through u, S(x,u,y) ⊆ S(x,y)</div></li></ul></ul><div><br/></div><div>Closeness:</div><ul><li><div>closeness of u c<span style="vertical-align: sub;">c</span>(u) = 1 / (sum d(u,v) for all v in G)</div></li></ul><div><br/></div></body></html>