index.md (1866B)
1 +++ 2 title = 'Network analysis' 3 template = 'page-math.html' 4 +++ 5 # Network analysis 6 Distribution of vertex degrees: vertices with high respectively low degree 7 8 <table> 9 <tr> 10 <th>Histogram</th> 11 <th>Ranked histogram</th> 12 </tr> 13 <tr> 14 <td><img src="889ea68b02076b45c13330d43ddb76ff.png"></td> 15 <td><img src="34c58d5a3e4dbf813a123e1c5aa35244.png"></td> 16 </tr> 17 </table> 18 19 Distance stats: 20 21 - d(u,v) — shortest distance between u and v 22 - ε(u) — eccentricity. longest shortest path from u and to any other vertices 23 - rad(G) — radius. minimum eccentricity 24 - diam(G) — diameter. longest path in graph. 25 - d̄(u) — average length of shortest paths from u to any other v. 26 - d̄(G) — average path length (average of all d̄(u)) 27 - characteristic path length — median over all d̄(u) 28 29 clustering coefficient ([good video](https://www.youtube.com/watch?v=K2WF4pT5pFY)) 30 31 - clustering — when many neighbours of vertex are also each other’s neighbours 32 - defined by: 33 34 $cc(v) = \frac{2m_{v}}{\delta (v) \times (\delta (v) -1)}$ 35 36 where mv is number of links between neighbours of v. 37 38 - for triangles: 39 - triangle is complete subgraph of 3 vertices 40 - triple is subgraph of 3 vertices and 2 edges 41 - network transitivity τ(G) = nΔ(G) / ntriple(G) 42 - nΔ(v) — number of triangles of which v is a member 43 - ntriple(v) — number of triples at v (*v* is incident to both edges) 44 - essentially the same as clustering coefficient, but for whole graph 45 46 Centrality: 47 48 - center C(G) is set of vertices with min eccentricity 49 - vertex centrality of u cE(u) = 1 / ε(u) 50 - betweenness centrality of u cB(u) = sum |S(x,u,y)| / |S(x,y)| for x≠u≠y 51 - S(x,y) — set of shortest paths between x and y 52 - S(x,u,y) — shortest paths passing through u, S(x,u,y) ⊆ S(x,y) 53 54 Closeness: 55 56 - closeness of u cc(u) = 1 / (sum d(u,v) for all v in G)