commit 9ad32868f0afd7fc92be86606aaa575a0131bc7b parent 2a25ac3aaac20fdb56d1e23efc0e20ea332d41c4 Author: Alex Balgavy <alex@balgavy.eu> Date: Sat, 26 Dec 2020 00:49:06 +0100 Networks & graphs notes Diffstat:
67 files changed, 690 insertions(+), 209 deletions(-)
diff --git a/content/_index.md b/content/_index.md @@ -41,4 +41,4 @@ title = "Alex's university course notes" * [Web tech](https://thezeroalpha.github.io/webtech-notes) * [Computer Networks](compnet-notes/) * [History of Science](history-science-notes/) -* [Networks & graphs](https://thezeroalpha.github.io/networksgraphs-notes) +* [Networks & graphs](networksgraphs-notes/) diff --git a/content/networksgraphs-notes/0f4a0b89454e0d874eafae79938429a2.jpg b/content/networksgraphs-notes/0f4a0b89454e0d874eafae79938429a2.jpg Binary files differ. diff --git a/content/networksgraphs-notes/214d9e2b0d23378e800b1449f2e28520.jpg b/content/networksgraphs-notes/214d9e2b0d23378e800b1449f2e28520.jpg Binary files differ. diff --git a/content/networksgraphs-notes/5be17db7825abe6d50eb84d85b256ea9.jpg b/content/networksgraphs-notes/5be17db7825abe6d50eb84d85b256ea9.jpg Binary files differ. diff --git a/content/networksgraphs-notes/7092a5efdde00ffce7b56ea19fc91056.jpg b/content/networksgraphs-notes/7092a5efdde00ffce7b56ea19fc91056.jpg Binary files differ. diff --git a/content/networksgraphs-notes/79fc463a5f36837d4858f5422fae1e57.jpg b/content/networksgraphs-notes/79fc463a5f36837d4858f5422fae1e57.jpg Binary files differ. diff --git a/content/networksgraphs-notes/8dbc3a38e3b9c81cf9af5d58c8b3e18e.jpg b/content/networksgraphs-notes/8dbc3a38e3b9c81cf9af5d58c8b3e18e.jpg Binary files differ. diff --git a/content/networksgraphs-notes/Cheat sheet of stuff I always forget.md b/content/networksgraphs-notes/Cheat sheet of stuff I always forget.md @@ -0,0 +1,78 @@ ++++ +title = 'Cheat sheet of stuff I always forget' ++++ +# Cheat sheet of stuff I always forget +γ = 0.5772 + +Harary: + +- forming a harary graph Hk,n: + - if k is odd and n is odd — make each vertex adjacent to (k-1)/2. then index nodes by integers mod n, and connect node to integer+(n-1)/2 for 0≤integer≤(n-1)/2 + - yes, one node will have an even degree — the one labelled (n-1)/2 + +ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking + +Euler’s formula for planar graphs: + +- n-m+r=2 +- n vertices, m edges, r regions + +condition for planar graph: m ≤ 3v-6 + +a graph is a tree if: + +- n vertices, n-1 edges +- there is exactly one path between any two vertices +- every edge is a cut edge (a loop is never a cut edge, a cycle has no cut edges) + +ε(u) — eccentricity. longest shortest path from u and to any other vertices +rad(G) — radius. minimum eccentricity + +clustering — when many neighbours of vertex are also each other’s neighbours +defined by: + +where mv is number of links between neighbours of v. + +network transitivity τ(G) = nΔ(G) / ntriple(G) + +vertex centrality of u cE(u) = 1 / ε(u) +betweenness centrality of u cB(u) = sum |S(x,u,y)| / |S(x,y)| for x≠u≠y + +- S(x,y) — set of shortest paths between x and y +- S(x,u,y) — shortest paths passing through u, S(x,u,y) ⊆ S(x,y) + +closeness of u cc(u) = 1 / (sum d(u,v) for all v in G) + +**Random graphs** +ER(n,p): + +- n vertices, edge exists with probability p +- expected clustering coefficient is p +- phase transition around p=1/n — a gigantic connected component appears + + + +WS(n,k,p): + +- construct Hn,k , replace edges with probability p +- “small world” — high clustering coefficients + - CC(G) ≈ 0.75 for G ∈ WS(n,k,0) + +BA(n, n0, m): + +- n vertices, m edges +- preferential attachment (a new node is more likely to connect to nodes with high degrees) leads to hubs +- P(v is linked to u) =  + +**Communities** + +proximity prestige: (fraction of vertices that can reach v) / (average distance of those vertices to v) + +a signed graph (edges labelled +/-) is balanced if all its cycles are positive (product of edge labels is positive) + +signed graph is balanced iff its vertices can be partitioned into two disjoint subsets such that: + +- each negative edge joins the subsets, and +- each positive edge joins vertices in the same subset + +affiliation networks are naturally bipartite, with two sets (Va actors, Ve events) diff --git a/content/networksgraphs-notes/Colourings.html b/content/networksgraphs-notes/Colourings.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.7313327193260193"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:07:01 +0000"/><meta name="latitude" content="52.3345077115161"/><meta name="longitude" content="4.866741210123743"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:46:40 +0000"/><title>Colourings</title></head><body><div>“colouring” is a way of labelling a graph</div><div><br/></div><div>Edge colourings</div><ul><li><div>assign colours to edges such that edges incident on same vertex always have different colours</div></li><li><div>a simple graph is k-edge colourable if E(G) can be partitioned into sets E<span style="vertical-align: sub;">1</span>…E<span style="vertical-align: sub;">k</span> such that each pair of distinct edges in an E(1..k) isn’t incident to same vertex</div></li><li><div>edge chromatic number Χ’(g) is minimal k for which G is edge-colourable</div></li><li><div>Χ’(G) = Δ(G) or Δ(G) +1</div></li><ul><li><div>Δ(G) is maximum degree in graph</div></li></ul></ul><div><br/></div><div>Vertex colourings</div><ul><li><div>simple graph..same as edge but with vertex</div></li><li><div>Χ(G) chromatic number is minimal k for which G is k-vertex colourable</div></li><li><div>Χ(G) ≤ Δ(G) + 1</div></li><li><div>for any planar graph G, Χ(G) ≤ 4</div></li><ul><li><div>weaker bound: for any planar G, Χ(G) ≤ 5</div></li><li><div>the proof for weaker bound can be asked</div></li></ul></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Colourings.md b/content/networksgraphs-notes/Colourings.md @@ -0,0 +1,22 @@ ++++ +title = 'Colourings' ++++ +# Colourings +“colouring” is a way of labelling a graph + +Edge colourings + +- assign colours to edges such that edges incident on same vertex always have different colours +- a simple graph is k-edge colourable if E(G) can be partitioned into sets E1…Ek such that each pair of distinct edges in an E(1..k) isn’t incident to same vertex +- edge chromatic number Χ’(g) is minimal k for which G is edge-colourable +- Χ’(G) = Δ(G) or Δ(G) +1 + - Δ(G) is maximum degree in graph + +Vertex colourings + +- simple graph..same as edge but with vertex +- Χ(G) chromatic number is minimal k for which G is k-vertex colourable +- Χ(G) ≤ Δ(G) + 1 +- for any planar graph G, Χ(G) ≤ 4 + - weaker bound: for any planar G, Χ(G) ≤ 5 + - the proof for weaker bound can be asked diff --git a/content/networksgraphs-notes/Communities.html b/content/networksgraphs-notes/Communities.html @@ -1,8 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.8620138168334961"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-26 12:39:15 +0000"/><meta name="latitude" content="52.37359333395369"/><meta name="longitude" content="4.83634531063313"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-26 12:56:08 +0000"/><title>Communities</title></head><body><div>Sociogram: graph-like representation of social structure</div><div>calculate stats like eccentricity, closeness, betweenness centrality</div><div><br/></div><div>proximity prestige</div><ul><li><div>D is digraph with n vertices</div></li><li><div>influence domain R<sup>-</sup>(v) of v is set of vertices from which v can be reached</div></li><li><div>proximity prestige: (fraction of vertices that can reach v) / (average distance of those vertices to v)</div></li></ul><div><br/></div><div>ranked prestige</div><ul><li><div>A is adjacency matrix for digraph</div></li><li><div>A[v,u] means how much v is appreciated by u</div></li></ul><div><br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="Communities.resources/55DEA60A-1653-4137-BADC-C27B9B01534D.png" height="47" width="280"/></div><div><br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="Communities.resources/6CB89EC0-D6C1-42F3-8261-997054B34AE4.png" height="47" width="286"/></div><div><br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="Communities.resources/B313FC5C-6F11-48DC-8B06-C9C398F50428.png" height="43" width="148"/></div><div><br/></div><div style="margin-left: 40px;">example:</div><div style="margin-left: 40px;"><img src="Communities.resources/screenshot_1.png" height="101" width="606"/></div><div><br/></div><div>structural balance</div><ul><li><div>a signed graph (edges labelled +/-) is balanced if all its cycles are positive (product of edge labels is positive)</div></li><li><div>if the graph has no cycles, it is balanced</div></li><li><div>signed graph is balanced iff its vertices can be partitioned into two disjoint subsets such that:</div></li><ul><li><div>each negative edge joins the subsets, and </div></li><li><div>each positive edge joins vertices in the same subset</div></li></ul></ul><div><br/></div><div>affiliation networks</div><ul><li><div>people are tied together through membership relations</div></li><li><div>social structures consist of actors and events</div></li><li><div>naturally bipartite, with two sets (V<sub>a</sub> actors, V<sub>e</sub> events)</div></li><li><div>represented with an actor-event matrix:</div></li></ul><div><br/></div><div style="margin-left: 40px;"><img src="Communities.resources/screenshot.png" height="184" width="582"/></div><div style=""><br/></div><ul><li><div style="">number of events in which a and b participated</div></li></ul><div><br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="Communities.resources/F7861E91-61F2-490E-BD0F-91FEE94A9DE1.png" height="46" width="299"/></div><ul><li><div style="">number of actors participating in events e and f</div></li></ul><div><br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="Communities.resources/4688D813-3907-4209-AE32-6002A873DF1E.png" height="46" width="307"/></div><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Communities.resources/4688D813-3907-4209-AE32-6002A873DF1E.png b/content/networksgraphs-notes/Communities.resources/4688D813-3907-4209-AE32-6002A873DF1E.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/55DEA60A-1653-4137-BADC-C27B9B01534D.png b/content/networksgraphs-notes/Communities.resources/55DEA60A-1653-4137-BADC-C27B9B01534D.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/6CB89EC0-D6C1-42F3-8261-997054B34AE4.png b/content/networksgraphs-notes/Communities.resources/6CB89EC0-D6C1-42F3-8261-997054B34AE4.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/B313FC5C-6F11-48DC-8B06-C9C398F50428.png b/content/networksgraphs-notes/Communities.resources/B313FC5C-6F11-48DC-8B06-C9C398F50428.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/F7861E91-61F2-490E-BD0F-91FEE94A9DE1.png b/content/networksgraphs-notes/Communities.resources/F7861E91-61F2-490E-BD0F-91FEE94A9DE1.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/screenshot_1.png b/content/networksgraphs-notes/Communities/87d425bcaf98351d8984e7eb8fa5db75.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities.resources/screenshot.png b/content/networksgraphs-notes/Communities/c310d078a34b26f7c74e800c66475f34.png Binary files differ. diff --git a/content/networksgraphs-notes/Communities/index.md b/content/networksgraphs-notes/Communities/index.md @@ -0,0 +1,54 @@ ++++ +title = 'Communities' +template = 'page-math.html' ++++ +# Communities +Sociogram: graph-like representation of social structure +calculate stats like eccentricity, closeness, betweenness centrality + +proximity prestige + +- D is digraph with n vertices +- influence domain R-(v) of v is set of vertices from which v can be reached +- proximity prestige: (fraction of vertices that can reach v) / (average distance of those vertices to v) + +ranked prestige + +- A is adjacency matrix for digraph +- A[v,u] means how much v is appreciated by u + + +$\sum_{v \neq u} A[v, u] = 1$ for each vertex u + +$p_{rank} (v) = \sum_{u \neq v} A[v, u] \times p_{rank} (u)$ + +$\sum_{v} p_{rank} (v)^2 = 1$ + +example: + + + +structural balance + +- a signed graph (edges labelled +/-) is balanced if all its cycles are positive (product of edge labels is positive) +- if the graph has no cycles, it is balanced +- signed graph is balanced iff its vertices can be partitioned into two disjoint subsets such that: + - each negative edge joins the subsets, and + - each positive edge joins vertices in the same subset + +affiliation networks + +- people are tied together through membership relations +- social structures consist of actors and events +- naturally bipartite, with two sets (Va actors, Ve events) +- represented with an actor-event matrix: + + + +- number of events in which a and b participated + + $NE[a, b] = \sum_{e \in V_e} AE[a, e] \times AE[b, e]$ + +- number of actors participating in events e and f + + $NA [e, f] = \sum_{a \in V_a} AE[a, e] \times AE[a, f]$ diff --git a/content/networksgraphs-notes/Connectivity.html b/content/networksgraphs-notes/Connectivity.html @@ -1,4 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.6527782082557678"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:01:04 +0000"/><meta name="latitude" content="52.33451044149249"/><meta name="longitude" content="4.866744062922999"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:21:52 +0000"/><title>Connectivity</title></head><body><div>Connectivity:</div><ul><li><div>vertices u,v are connected if there is a (u,v) path between them</div></li><li><div>graph is connected if all pairs of vertices are connected</div></li><li><div>graph is k-connected if κ(G) ≥ k</div></li><li><div>graph is k-edge-connected if λ(G) ≥ k</div></li><li><div>graph is optimally connected if λ(G) = κ(G) = min { δ(v) | v ∈ V(G) }</div></li><li><div>a component of G is a connected subgraph that isn’t contained in another connected subgraph of G</div></li></ul><div><br/></div><div>Vertex & edge cuts</div><ul><li><div>V* ⊂ V(G) is vertex cut if removing vertices V* disconnects the graph</div></li><li><div>E* ⊂ E(G) is edge cut if removing edges E* disconnects the graph</div></li><li><div>κ(G) is size of minimal vertex cut for G — the amount of vertices needed to disconnect G</div></li><li><div>λ(G) is size of minimal edge cut for G — the amount of edges needed to disconnect G</div></li><li><div><span style="font-size: 18px;" -/><img src="Connectivity.resources/665E9A03-7A1F-4FD2-8546-EC809CB11832.png" height="21" width="258"/></div></li><ul><li><div>in english, min vertex cut ≤ min edge cut ≤ smallest degree in graph</div></li></ul></ul><div><br/></div><div>Menger’s theorem:</div><ul><li><div>Let G be a connected graph, with u and v two non-adjacent vertices.</div></li><li><div>formal: “The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v equals the maximum size of a vertex-independent set P(u,v). The minimum size of an edge cut disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u,v)."</div></li><li><div>in english: the min number of vertices you need to remove to split vertices u and v into different components of the graph == the max number of paths from u to v that don’t share vertices. same shit for edges.</div></li><li><div><a href="https://www.youtube.com/watch?v=dUAeleBMRCQ">This is a good video explanation.</a></div></li></ul><div><br/></div><div>Harary graphs:</div><ul><li><div>k-connected graphs, of the form H<span style="vertical-align: sub;">k,n</span></div></li><li><div>forming a harary graph H<span style="vertical-align: sub;">k,n</span>:</div></li><ul><li><div>place n vertices around a circle</div></li><li><div>if k is even — make each vertex adjacent to k/2 neighbours in each direction around circle</div></li><li><div>if k is odd and n is even — make each vertex adjacent to (k-1)/2 neighbours in each direction, and diametrically opposite vertex</div></li><li><div>if k is odd and n is odd — make each vertex adjacent to (k-1)/2. then index nodes by integers mod n, and connect node to integer+(n-1)/2 for 0≤integer≤(n-1)/2</div></li><ul><li><div>yes, one node will have an even degree — the one labelled (n-1)/2</div></li></ul></ul></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Connectivity.md b/content/networksgraphs-notes/Connectivity.md @@ -0,0 +1,38 @@ ++++ +title = 'Connectivity' +template = 'page-math.html' ++++ +# Connectivity + +- vertices u,v are connected if there is a (u,v) path between them +- graph is connected if all pairs of vertices are connected +- graph is k-connected if κ(G) ≥ k +- graph is k-edge-connected if λ(G) ≥ k +- graph is optimally connected if λ(G) = κ(G) = min { δ(v) | v ∈ V(G) } +- a component of G is a connected subgraph that isn’t contained in another connected subgraph of G + +Vertex & edge cuts + +- V* ⊂ V(G) is vertex cut if removing vertices V* disconnects the graph +- E* ⊂ E(G) is edge cut if removing edges E* disconnects the graph +- κ(G) is size of minimal vertex cut for G — the amount of vertices needed to disconnect G +- λ(G) is size of minimal edge cut for G — the amount of edges needed to disconnect G +- $\kappa_{G} \leq \lambda (G) \leq \min_{v \in V(G)} {\delta (v)}$ + - in english, min vertex cut ≤ min edge cut ≤ smallest degree in graph + +Menger’s theorem: + +- Let G be a connected graph, with u and v two non-adjacent vertices. +- formal: “The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v equals the maximum size of a vertex-independent set P(u,v). The minimum size of an edge cut disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u,v)." +- in english: the min number of vertices you need to remove to split vertices u and v into different components of the graph == the max number of paths from u to v that don’t share vertices. same shit for edges. +- [This is a good video explanation.](https://www.youtube.com/watch?v=dUAeleBMRCQ) + +Harary graphs: + +- k-connected graphs, of the form Hk,n +- forming a harary graph Hk,n: + - place n vertices around a circle + - if k is even — make each vertex adjacent to k/2 neighbours in each direction around circle + - if k is odd and n is even — make each vertex adjacent to (k-1)/2 neighbours in each direction, and diametrically opposite vertex + - if k is odd and n is odd — make each vertex adjacent to (k-1)/2. then index nodes by integers mod n, and connect node to integer+(n-1)/2 for 0≤integer≤(n-1)/2 + - yes, one node will have an even degree — the one labelled (n-1)/2 diff --git a/content/networksgraphs-notes/Connectivity.resources/665E9A03-7A1F-4FD2-8546-EC809CB11832.png b/content/networksgraphs-notes/Connectivity.resources/665E9A03-7A1F-4FD2-8546-EC809CB11832.png Binary files differ. diff --git a/content/networksgraphs-notes/Digraphs & orientations.html b/content/networksgraphs-notes/Digraphs & orientations.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.7313327193260193"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:06:41 +0000"/><meta name="latitude" content="52.3345077115161"/><meta name="longitude" content="4.866741210123743"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 23:04:21 +0000"/><title>Digraphs & orientations</title></head><body><div>Directed graphs:</div><ul><li><div>to convert graph to digraph, represent each edge with two equally weighted arcs</div></li><li><div>digraph D consists of sets V(D) vertices and A(D) arcs</div></li><li><div>arc <u,v> joins vertex u (tail) to head v</div></li><li><div>has indegree and outdegree, where the sum of all outdegrees is the same as the sum of all indegrees, which equals the number of arcs in D.</div></li><li><div>adjacency matrix is not symmetric</div></li><li><div>strict if ∀ u,v: (A[u,v]) ≤ 1 and A(u,u)=0</div></li><ul><li><div>in english: no duplicate edges between vertices, no loops</div></li></ul></ul><div><br/></div><div>Connectivity with digraphs:</div><ul><li><div>strongly connected: there is a directed path "there and back" between any two vertices</div></li><li><div>weakly connected: the underlying graph is connected (i.e. if all edges were made undirected, the graph would be connected)</div></li><li><div>strongly connected digraphs form strongly connected components</div></li><li><div>vertex v is reachable from u if there is a path (u,v)</div></li><li><div>algorithm for reachability:</div></li><ul><li><div>Rt(u) is the set of reachable vertices from u, found after t steps.</div></li><li><div>steps:</div></li><ol><li><div>Set t ← 0 and R<span style="vertical-align: sub;">0</span>(u) ← {u}</div></li><li><div>Construct set R<span style="vertical-align: sub;">t+1</span>(u) ← R<span style="vertical-align: sub;">t</span>(u) U<span style="vertical-align: sub;">v ∈ Rt(u)</span> N<span style="vertical-align: sub;">out</span>(v)</div></li><li><div>If R<span style="vertical-align: sub;">t+1</span>(u) = Rt(u), stop: R(u) ← R<span style="vertical-align: sub;">t</span>(u). Else, increment t and repeat step 2.</div></li></ol></ul></ul><div><br/></div><div>Orientations</div><ul><li><div>orientation of a simple graph is a digraph where you give every edge a direction</div></li><li><div>there is strongly connected orientation iff λ(G) ≥ 2</div></li></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Digraphs & orientations.md b/content/networksgraphs-notes/Digraphs & orientations.md @@ -0,0 +1,33 @@ ++++ +title = 'Digraphs & orientations' ++++ +# Digraphs & orientations +Directed graphs: + +- to convert graph to digraph, represent each edge with two equally weighted arcs +- digraph D consists of sets V(D) vertices and A(D) arcs +- arc \<u,v> joins vertex u (tail) to head v +- has indegree and outdegree, where the sum of all outdegrees is the same as the sum of all indegrees, which equals the number of arcs in D. +- adjacency matrix is not symmetric +- strict if ∀ u,v: (A[u,v]) ≤ 1 and A(u,u)=0 + - in english: no duplicate edges between vertices, no loops + +Connectivity with digraphs: + +- strongly connected: there is a directed path "there and back" between any two vertices +- weakly connected: the underlying graph is connected (i.e. if all edges were made undirected, the graph would be connected) +- strongly connected digraphs form strongly connected components +- vertex v is reachable from u if there is a path (u,v) +- algorithm for reachability: + - Rt(u) is the set of reachable vertices from u, found after t steps. + - steps: + + 1. Set t ← 0 and R0(u) ← {u} + 2. Construct set Rt+1(u) ← Rt(u) Uv ∈ Rt(u) Nout(v) + + 3. If Rt+1(u) = Rt(u), stop: R(u) ← Rt(u). Else, increment t and repeat step 2. + +Orientations + +- orientation of a simple graph is a digraph where you give every edge a direction +- there is strongly connected orientation iff λ(G) ≥ 2 diff --git a/content/networksgraphs-notes/Drawing graphs.html b/content/networksgraphs-notes/Drawing graphs.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-1.767048716545105"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 13:00:35 +0000"/><meta name="latitude" content="52.33423205054267"/><meta name="longitude" content="4.867457702591858"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:27:30 +0000"/><title>Drawing graphs</title></head><body><div>Embeddings:</div><ul><li><div>circular embedding — vertices are spaced evenly around a circle</div></li><li><div>ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking</div></li></ul><div><br/></div><div>Planar graphs: graphs where no edges cross</div><ul><li><div>interior region: empty space enclosed by a cycle</div></li><li><div>exterior region: empty space not enclosed by a cycle</div></li><li><div>Euler’s formula for planar graphs:</div></li><ul><li><div>n-m+r=2</div></li><li><div>n vertices, m edges, r regions</div></li></ul><li><div>condition for planar graph: m ≤ 3v-6</div></li><li><div>every planar graph has a vertex <span style="font-style: italic;">v, </span>with δ(<span style="font-style: italic;">v</span>) ≤ 5</div></li></ul><div><br/></div><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Drawing graphs.md b/content/networksgraphs-notes/Drawing graphs.md @@ -0,0 +1,18 @@ ++++ +title = 'Drawing graphs' ++++ +# Drawing graphs +Embeddings: + +- circular embedding — vertices are spaced evenly around a circle +- ranked embedding — choose an arbitrary vertex u, rank other vertices by distance from u, put vertices on separate lines based on ranking + +Planar graphs: graphs where no edges cross + +- interior region: empty space enclosed by a cycle +- exterior region: empty space not enclosed by a cycle +- Euler’s formula for planar graphs: + - n-m+r=2 + - n vertices, m edges, r regions +- condition for planar graph: m ≤ 3v-6 +- every planar graph has a vertex *v, *with δ(*v*) ≤ 5 diff --git a/content/networksgraphs-notes/Euler: edges matter.html b/content/networksgraphs-notes/Euler: edges matter.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.5295528173446655"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:30:09 +0000"/><meta name="latitude" content="52.33449063255681"/><meta name="longitude" content="4.866731888842327"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:17:20 +0000"/><title>Euler: edges matter</title></head><body><div>mnemonic: <span style="text-decoration: underline;">E</span>uler starts with <span style="text-decoration: underline;">E</span>, so <span style="text-decoration: underline;">e</span>dges matter.</div><div><br/></div><div>Euler tour</div><ul><li><div>traverses <span style="text-decoration: underline;">each</span> edge exactly once, start=end</div></li><li><div>A connected graph has Euler tour iff all vertices have even degrees</div></li><li><div>Fleury’s algorithm for Euler tour:</div></li><ol><li><div>Trail P consists of single vertex u</div></li><li><div>While E(P) ≠ E(G) do:</div></li><ol><li><div>Let v be last vertex added to P</div></li><li><div>choose an edge <v,w> in (G-E(P)).</div></li><ul><li><div><v,w> is only allowed to be a cut edge if there is no other option.</div></li></ul><li><div>add it to P</div></li></ol></ol><li><div>Hierholzer’s algorithm for Euler tour</div></li><ul><li><div>First, find a closed trail from some vertex</div></li><li><div>for each vertex <span style="font-style: italic;">u</span> that has adjacent edges that are not part of the trail, find a closed trail on that vertex (starting and ending in <span style="font-style: italic;">u</span>), then add the trail to the tour</div></li><li><div><a href="https://www.youtube.com/watch?v=3k5_oooad8U">surreal video explaining this</a></div></li></ul></ul><div><br/></div><div>Euler trail</div><ul><li><div>traverses <span style="text-decoration: underline;">each</span> edge exactly once, but is open</div></li><li><div>connected graph G has Euler trail iff it has exactly 2 vertices of odd degree</div></li></ul><div><br/></div><div>Chinese postman problem (also, Bridges of Konigsberg)</div><ul><li><div>problem:</div></li><ul><li><div>in weighted graph, each edge has real-valued weight</div></li><li><div>all edges are passed <span style="text-decoration: underline;">at least</span> once, total travelled dist is minimal</div></li><li><div>find closed walk of minimal length</div></li></ul><li><div>Solution:</div></li><ul><li><div>let G be connected, weighted graph</div></li><li><div>Let 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;">2k</span> be odd degree vertices in G</div></li><li><div>Algorithm:</div></li><ol><li><div>For each pair of distinct odd-degree vertices v<span style="vertical-align: sub;">i</span> and v<span style="vertical-align: sub;">j</span>, find minimum-weight path P<span style="vertical-align: sub;">ij</span></div></li><li><div>Construct weighted complete graph on 2k vertices in which vertex v<span style="vertical-align: sub;">i</span> and v<span style="vertical-align: sub;">j</span> are joined by an edge having weight w(P<span style="vertical-align: sub;">ij</span>)</div></li><li><div>Find set E of k edges {e<span style="vertical-align: sub;">1</span>, …, e<span style="vertical-align: sub;">k</span>} such that:</div></li><ul><li><div>the sum of their weights is minimal</div></li><li><div>no two edges are incident on same vertex</div></li></ul><li><div>For each edge e ∈ E, with e=<v<span style="vertical-align: sub;">i</span>, v<span style="vertical-align: sub;">j</span>>, duplicate edges of P<span style="vertical-align: sub;">i,j</span> in graph G</div></li><li><div>Find Euler tour in resulting graph</div></li></ol></ul></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Euler_ edges matter.md b/content/networksgraphs-notes/Euler_ edges matter.md @@ -0,0 +1,54 @@ ++++ +title = 'Euler: edges matter' ++++ +# Euler: edges matter +mnemonic: Euler starts with E, so edges matter. + +Euler tour + +- traverses each edge exactly once, start=end +- A connected graph has Euler tour iff all vertices have even degrees +- Fleury’s algorithm for Euler tour: + + 1. Trail P consists of single vertex u + 2. While E(P) ≠ E(G) do: + 1. Let v be last vertex added to P + 2. choose an edge <v,w> in (G-E(P)). + + - <v,w> is only allowed to be a cut edge if there is no other option. + + 3. add it to P + +- Hierholzer’s algorithm for Euler tour + - First, find a closed trail from some vertex + - for each vertex *u* that has adjacent edges that are not part of the trail, find a closed trail on that vertex (starting and ending in *u*), then add the trail to the tour + - [surreal video explaining this](https://www.youtube.com/watch?v=3k5_oooad8U) + +Euler trail + +- traverses each edge exactly once, but is open +- connected graph G has Euler trail iff it has exactly 2 vertices of odd degree + +Chinese postman problem (also, Bridges of Konigsberg) + +- problem: + - in weighted graph, each edge has real-valued weight + - all edges are passed at least once, total travelled dist is minimal + - find closed walk of minimal length +- Solution: + - let G be connected, weighted graph + - Let v1, …, v2k be odd degree vertices in G + - Algorithm: + + 1. For each pair of distinct odd-degree vertices vi and vj, find minimum-weight path Pij + + 2. Construct weighted complete graph on 2k vertices in which vertex vi and vj are joined by an edge having weight w(Pij) + + 3. Find set E of k edges {e1, …, ek} such that: + + - the sum of their weights is minimal + - no two edges are incident on same vertex + + 4. For each edge e ∈ E, with e=<vi, vj>, duplicate edges of Pi,j in graph G + + 5. Find Euler tour in resulting graph diff --git a/content/networksgraphs-notes/Fundamentals.html b/content/networksgraphs-notes/Fundamentals.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.7322385907173157"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:00:08 +0000"/><meta name="latitude" content="52.33452599663043"/><meta name="longitude" content="4.86676147773762"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:38:18 +0000"/><title>Fundamentals</title></head><body><div><span style="font-weight: bold;">Basic definition</span></div><div>Graph G: consists of V(G) set of vertices and E(G) set of edges</div><div>Edge: consists of vertices u and v, denoted by (u, v)</div><div><br/></div><div>For vertex u ∈ V(G), neighbour set N(u) is set of vertices adjacent to u</div><div><br/></div><div>Simple graph: does not have multiple edges between pairs, or loops</div><div>Bipartite graph: where you can partition vertices into two subsets, with no edge incident to vertices from same subset </div><div>Tree: graph that has no cycles </div><div>Degree δ(v): number of edges on node, loops are counted twice.</div><div>Degree sequence: list of all vertices’ degrees in a graph. Ordered if it’s in descending order</div><div><br/></div><div>Handshaking lemma: sum of degrees of all vertices in a graph is twice the number of edges in the graph</div><div><br/></div><div><span style="font-weight: bold;">Traversal definitions</span></div><div>Least to most strict:</div><ul><li><div>walk: a sequence of vertices and edges (closed or open)</div></li><li><div>trail: a walk with no repeating edges (open)</div></li><li><div>tour: a walk with no repeating edges, start=end (closed)</div></li><li><div>path: a walk with no repeating vertices or edges (open)</div></li><li><div>cycle: a walk with no repeating vertices or edges, start=end (closed)</div></li></ul><div><br/></div><div>for digraphs, everything’s the same, just directed.</div><div><br/></div><div><span style="font-weight: bold;">Degree sequence</span></div><div>Sequence of numbers is graphic if it’s a degree sequence of a simple graph (could also have other non-simple)</div><div><br/></div><div>Show that a sequence is graphic — Havel-Hakimi theorem:</div><ul><li><div>Given sequence: (1, 2, 1, 3, 3, 2, 3, 5)</div></li><li><div>Order it descending: (5, 3, 3, 3, 2, 2, 1, 1)</div></li><li><div>Systematically remove vertices from start, subtract one from the rest:</div></li><ol><li><div>(2, 2, 2, 1, 1, 1, 1) — remove ‘5', subtract 1 from the next 5 elements</div></li><li><div>(1, 1, 1, 1, 1, 1) — remove ‘2', subtract 1 from the next 2 elements'</div></li><li><div>(1, 1, 1, 1, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>(1, 1, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>(0, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder</div></li><li><div>All ‘0', therefore sequence is graphic.</div></li></ol></ul><div><br/></div><div><br/></div><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Fundamentals.md b/content/networksgraphs-notes/Fundamentals.md @@ -0,0 +1,50 @@ ++++ +title = 'Fundamentals' ++++ +# Fundamentals +**Basic definition** +Graph G: consists of V(G) set of vertices and E(G) set of edges +Edge: consists of vertices u and v, denoted by (u, v) + +For vertex u ∈ V(G), neighbour set N(u) is set of vertices adjacent to u + +Simple graph: does not have multiple edges between pairs, or loops + +Bipartite graph: where you can partition vertices into two subsets, with no edge incident to vertices from same subset + +Tree: graph that has no cycles +Degree δ(v): number of edges on node, loops are counted twice. + +Degree sequence: list of all vertices’ degrees in a graph. Ordered if it’s in descending order + +Handshaking lemma: sum of degrees of all vertices in a graph is twice the number of edges in the graph + +**Traversal definitions** +Least to most strict: + +- walk: a sequence of vertices and edges (closed or open) +- trail: a walk with no repeating edges (open) +- tour: a walk with no repeating edges, start=end (closed) +- path: a walk with no repeating vertices or edges (open) +- cycle: a walk with no repeating vertices or edges, start=end (closed) + +for digraphs, everything’s the same, just directed. + +**Degree sequence** + +Sequence of numbers is graphic if it’s a degree sequence of a simple graph (could also have other non-simple) + +Show that a sequence is graphic — Havel-Hakimi theorem: + +- Given sequence: (1, 2, 1, 3, 3, 2, 3, 5) +- Order it descending: (5, 3, 3, 3, 2, 2, 1, 1) +- Systematically remove vertices from start, subtract one from the rest: + + 1. (2, 2, 2, 1, 1, 1, 1) — remove ‘5', subtract 1 from the next 5 elements + 2. (1, 1, 1, 1, 1, 1) — remove ‘2', subtract 1 from the next 2 elements' + + 3. (1, 1, 1, 1, 0) — remove ‘1', subtract 1 from the next 1 element, reorder + + 4. (1, 1, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder + 5. (0, 0, 0) — remove ‘1', subtract 1 from the next 1 element, reorder + 6. All ‘0', therefore sequence is graphic. diff --git a/content/networksgraphs-notes/Graph representations & morphisms.html b/content/networksgraphs-notes/Graph representations & morphisms.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.7865003943443298"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 11:06:56 +0000"/><meta name="latitude" content="52.33454307835949"/><meta name="longitude" content="4.866740711664674"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:00:55 +0000"/><title>Graph representations & morphisms</title></head><body><div>Graph representation</div><ul><li><div>Adjacency matrix: symmetric. Rows and columns are nodes, cells contain number of edges between nodes</div></li><li><div>Incidence matrix: rows are vertices, columns are edges. Cell is 1 if the edge is incident on the vertex.</div></li><li><div>Subgraph: H is subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and ∀ (u,v) ∈ E(H) there is u,v ∈ V(H)</div></li><ul><li><div>in english: a subgraph of G has a subset of vertices and subset of edges of G</div></li></ul></ul><div><br/></div><div><b>Homomorphism</b> is a function ϕ: V(G1) ➝ V(G2) such that for each edge <u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2)</div><div><br/></div><div><b>Isomorphism</b> is a <span style="font-style: italic;">one-to-one function</span> ϕ: V(G1) ➝ V(G2) such that for each edge <u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2). it has to be unique, one-to-one.</div><ul><li><div>in english: two graphs have essentially the same elements with the same organisation. it’s a structure-preserving mapping.</div></li><li><div>Graphs are not isomorphic if:</div></li><ul><li><div>|V(G1)| ≠ |V(G2)|</div></li><li><div>|E(G1)| ≠ |E(G2)|</div></li><li><div>ordered degree sequence of G1 is different from ordered degree sequence of G2</div></li></ul></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Graph representations & morphisms.md b/content/networksgraphs-notes/Graph representations & morphisms.md @@ -0,0 +1,20 @@ ++++ +title = 'Graph representations & morphisms' ++++ +# Graph representations & morphisms +Graph representation + +- Adjacency matrix: symmetric. Rows and columns are nodes, cells contain number of edges between nodes +- Incidence matrix: rows are vertices, columns are edges. Cell is 1 if the edge is incident on the vertex. +- Subgraph: H is subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and ∀ (u,v) ∈ E(H) there is u,v ∈ V(H) + - in english: a subgraph of G has a subset of vertices and subset of edges of G + +**Homomorphism** is a function ϕ: V(G1) ➝ V(G2) such that for each edge \<u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2) + +**Isomorphism** is a *one-to-one function* ϕ: V(G1) ➝ V(G2) such that for each edge \<u,v> ∈ E(G1) there is an edge \<ϕ(u), ϕ(v)> ∈ E(G2). it has to be unique, one-to-one. + +- in english: two graphs have essentially the same elements with the same organisation. it’s a structure-preserving mapping. +- Graphs are not isomorphic if: + - |V(G1)| ≠ |V(G2)| + - |E(G1)| ≠ |E(G2)| + - ordered degree sequence of G1 is different from ordered degree sequence of G2 diff --git a/content/networksgraphs-notes/Hamilton: vertices matter.html b/content/networksgraphs-notes/Hamilton: vertices matter.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.5295528173446655"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:31:01 +0000"/><meta name="latitude" content="52.33449063255681"/><meta name="longitude" content="4.866731888842327"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:35:15 +0000"/><title>Hamilton: vertices matter</title></head><body><div>a Hamilton cycle contains <span style="text-decoration: underline;">every</span> vertex <span style="text-decoration: underline;">exactly</span> once</div><div>G is Hamiltonian if it has a Hamilton cycle (but it’s hard to prove that it is, no efficient algorithm)</div><div>to show that G is not Hamiltonian:</div><ul><li><div>if G is Hamiltonian, then for any nonempty V* ⊆ V(G)</div></li><ul><li><div>the graph G-V* contains at most |V*| components</div></li><li><div>w(G-V*) ≤ |V*|</div></li></ul><li><div>if not true, graph not Hamiltonian</div></li></ul><div>Dirac’s criterion</div><ul><li><div>if G has n ≥ 3 vertices and ∀v: δ(v) ≥ n/2</div></li><li><div>then G is Hamiltonian</div></li></ul><div>Finding Hamilton cycles using Posa rotational transformations</div><ul><li><div>Pick starting vertex u. Initial path P=[u]</div></li><li><div>while P is not a Hamilton cycle:</div></li><ul><li><div>If possible, select y from N(last added vertex) excluding vertices already in path</div></li><ul><li><div>then add that y to the path</div></li></ul><li><div>else, pick a v from N(last added vertex). Because v is already in path, there is an edge from <i>v</i> to some other vertex <i>x</i>. </div></li><ul><li><div>do a switcherino — connect v to w, and reverse path from w to x:</div></li></ul><div style="margin-left: 40px;"><img src="Hamilton%3A%20vertices%20matter.resources/DE0A299C-0970-42AA-8FEE-B340BC1745E9.png" height="80" width="591"/><br/></div></ul></ul><div><br/></div><div>Traveling salesman problem:</div><ul><li><div>finding a shortest Hamilton cycle in a complete, weighted graph</div></li><li><div>because of Hamilton, there’s no efficient algorithm for this</div></li><li><div>greedy algorithm: start with arbitrary cycle, swap edges if it reduces overall weight</div></li></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Hamilton: vertices matter.resources/DE0A299C-0970-42AA-8FEE-B340BC1745E9.png b/content/networksgraphs-notes/Hamilton_ vertices matter/ba0b20e18d5e71412dc9848cf341f3ec.png Binary files differ. diff --git a/content/networksgraphs-notes/Hamilton_ vertices matter/index.md b/content/networksgraphs-notes/Hamilton_ vertices matter/index.md @@ -0,0 +1,36 @@ ++++ +title = 'Hamilton: vertices matter' ++++ +# Hamilton: vertices matter +a Hamilton cycle contains every vertex exactly once + +G is Hamiltonian if it has a Hamilton cycle (but it’s hard to prove that it is, no efficient algorithm) + +to show that G is not Hamiltonian: + +- if G is Hamiltonian, then for any nonempty V* ⊆ V(G) + - the graph G-V* contains at most |V*| components + - w(G-V*) ≤ |V*| +- if not true, graph not Hamiltonian + +Dirac’s criterion + +- if G has n ≥ 3 vertices and ∀v: δ(v) ≥ n/2 +- then G is Hamiltonian + +Finding Hamilton cycles using Posa rotational transformations + +- Pick starting vertex u. Initial path P=[u] +- while P is not a Hamilton cycle: + - If possible, select y from N(last added vertex) excluding vertices already in path + - then add that y to the path + - else, pick a v from N(last added vertex). Because v is already in path, there is an edge from *v* to some other vertex *x*. + - do a switcherino — connect v to w, and reverse path from w to x: + + + +Traveling salesman problem: + +- finding a shortest Hamilton cycle in a complete, weighted graph +- because of Hamilton, there’s no efficient algorithm for this +- greedy algorithm: start with arbitrary cycle, swap edges if it reduces overall weight diff --git a/content/networksgraphs-notes/Network analysis.html b/content/networksgraphs-notes/Network analysis.html @@ -1,4 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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;" -/><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>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Network analysis.resources/screenshot.png b/content/networksgraphs-notes/Network analysis/34c58d5a3e4dbf813a123e1c5aa35244.png Binary files differ. diff --git a/content/networksgraphs-notes/Network analysis.resources/screenshot_1.png b/content/networksgraphs-notes/Network analysis/889ea68b02076b45c13330d43ddb76ff.png Binary files differ. diff --git a/content/networksgraphs-notes/Network analysis/index.md b/content/networksgraphs-notes/Network analysis/index.md @@ -0,0 +1,56 @@ ++++ +title = 'Network analysis' +template = 'page-math.html' ++++ +# Network analysis +Distribution of vertex degrees: vertices with high respectively low degree + +<table> +<tr> +<th>Histogram</th> +<th>Ranked histogram</th> +</tr> +<tr> +<td><img src="889ea68b02076b45c13330d43ddb76ff.png"></td> +<td><img src="34c58d5a3e4dbf813a123e1c5aa35244.png"></td> +</tr> +</table> + +Distance stats: + +- d(u,v) — shortest distance between u and v +- ε(u) — eccentricity. longest shortest path from u and to any other vertices +- rad(G) — radius. minimum eccentricity +- diam(G) — diameter. longest path in graph. +- d̄(u) — average length of shortest paths from u to any other v. +- d̄(G) — average path length (average of all d̄(u)) +- characteristic path length — median over all d̄(u) + +clustering coefficient ([good video](https://www.youtube.com/watch?v=K2WF4pT5pFY)) + +- clustering — when many neighbours of vertex are also each other’s neighbours +- defined by: + + $cc(v) = \frac{2m_{v}}{\delta (v) \times (\delta (v) -1)}$ + +where mv is number of links between neighbours of v. + +- for triangles: + - triangle is complete subgraph of 3 vertices + - triple is subgraph of 3 vertices and 2 edges + - network transitivity τ(G) = nΔ(G) / ntriple(G) + - nΔ(v) — number of triangles of which v is a member + - ntriple(v) — number of triples at v (*v* is incident to both edges) + - essentially the same as clustering coefficient, but for whole graph + +Centrality: + +- center C(G) is set of vertices with min eccentricity +- vertex centrality of u cE(u) = 1 / ε(u) +- betweenness centrality of u cB(u) = sum |S(x,u,y)| / |S(x,y)| for x≠u≠y + - S(x,y) — set of shortest paths between x and y + - S(x,u,y) — shortest paths passing through u, S(x,u,y) ⊆ S(x,y) + +Closeness: + +- closeness of u cc(u) = 1 / (sum d(u,v) for all v in G) diff --git a/content/networksgraphs-notes/Random graphs.html b/content/networksgraphs-notes/Random graphs.html @@ -1,9 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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;"> -<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> -<img src="Random%20graphs.resources/0F800A22-FBC7-45A8-B32D-32D8A92992F3.png" height="15" width="315"/></div></div><ul><li><div>function -<img src="Random%20graphs.resources/5D352CF8-4A64-4E41-8771-09450DE0373B.png" height="14" width="8"/> is scale-free if -<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) = -<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;" -/><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>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Random graphs.md b/content/networksgraphs-notes/Random graphs.md @@ -0,0 +1,85 @@ ++++ +title = 'Random graphs' +template = 'page-math.html' ++++ +# Random graphs +Ok at this point I’m starting to give up on life. + +Erdos-Renyi graphs (random graphs) + +- ER(n,p) graph +- n vertices, random number of edges +- edge between a pair of vertices exists with probability p +- small avg shortest path length, low clustering coefficient +- expected clustering coefficient is p + - binomial distribution: + +$P[\delta (u) = k] = \binom{n-1}{K} p^k (1-p)^{n-1-k}$ + +since there are n-1 vertices to link with u. + +- for large G ∈ ER(n,p) the average shortest path length d̄(G) tends to: + + $\frac{\ln{n} - \gamma}{\ln{\delta}} + 0.5 \qquad \gamma \approx 0.5572$ + +- phase transition around p=1/n — a gigantic connected component appears + +Watts-Strogatz graphs (“small world”) + +- V = { v1, v2, v3, …, vn }. choose n >> (even k) >> ln(n) >> 1. +- to build: + + 1. construct Hn,k + 2. consider each edge \<u,v> + + - with probability p, replace it by \<u,w> + - w≠v, w randomly chosen from V \ N(u) + + 3. result is WS(n,k,p) + +- many vertices will be close to each other +- weak links are the long ones that cross the ring +- high clustering coefficients + - CC(G) ≈ 0.75 for G ∈ WS(n,k,0) +- average shortest path length for WS(n,k,0) + + $\hat{d}(u) \approx \frac{n}{2k}$ + +Scale-free networks + +- very few high-degree vertices +- degree distribution follows power law + + $P[\delta (u) = k] \alpha ∝ k^{-a}$ (usually 2 < a < 3) + +- function $f$ is scale-free if $f(bx) = C_{b} f(x)$ with Cb a constant +- scale-free function has the same shape everywhere +- built using growth process with preferential attachment (a new node is more likely to connect to nodes with high degrees) +- hubs make them vulnerable to targeted attacks +- example — BA graphs (below) + +Barabasi-Albert graphs (scale-free, dynamical growth, random graphs) + +- BA(n, n0, m) +- n vertices, m edges +- start with n0 nodes at t=0, on every step add node with m (≤ n0) edges +- constructing a graph + - start with n0 nodes, no edges + - while vertices < n + + 1. add a new node v + + 2. add edges to all other nodes, each with probability proportional to δ(u) + + 3. for constant c ≥ 0, add c × m edges between vertices excluding v. probability for each edge <x,y> is proportional to δ(x)×δ(y) + +- P(v is linked to u) = $\frac{\delta (u)}{\text{sum } \delta (\text{all other nodes})}$ + +- power law distribution: + + $P[\delta (u) = k] = \frac{2m^2}{k^3} \propto k^{-3}$ + +- there’s a bunch of complicated formulas connected to this so I’ll just hope they don’t show up +- clustering coefficient depends on sequence +- average shortest path lengths are shorter than ER because of vertices with high degree (“hubs”) +- tunable clustering — you might add more edges to one node, based on a probability diff --git a/content/networksgraphs-notes/Random graphs.resources/0F800A22-FBC7-45A8-B32D-32D8A92992F3.png b/content/networksgraphs-notes/Random graphs.resources/0F800A22-FBC7-45A8-B32D-32D8A92992F3.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/1825E72F-ED6D-40A8-A91B-C026E44EA514.png b/content/networksgraphs-notes/Random graphs.resources/1825E72F-ED6D-40A8-A91B-C026E44EA514.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/51A9CD56-C97F-4547-A52E-55FA145088E8.png b/content/networksgraphs-notes/Random graphs.resources/51A9CD56-C97F-4547-A52E-55FA145088E8.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/5D352CF8-4A64-4E41-8771-09450DE0373B.png b/content/networksgraphs-notes/Random graphs.resources/5D352CF8-4A64-4E41-8771-09450DE0373B.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/86D8B67D-3A40-4F79-9FE1-A57B47D5160A.png b/content/networksgraphs-notes/Random graphs.resources/86D8B67D-3A40-4F79-9FE1-A57B47D5160A.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/DF249098-9684-4ADE-952B-F1A8382E99EA.png b/content/networksgraphs-notes/Random graphs.resources/DF249098-9684-4ADE-952B-F1A8382E99EA.png Binary files differ. diff --git a/content/networksgraphs-notes/Shortest path algorithms.html b/content/networksgraphs-notes/Shortest path algorithms.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-1.118819952011108"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-25 22:58:35 +0000"/><meta name="latitude" content="52.37361942175082"/><meta name="longitude" content="4.836354558355512"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-26 16:06:59 +0000"/><title>Shortest path algorithms</title></head><body><div>Arcs in digraphs may carry negative weights. if there’s a cycle of negative weight, there are no shortest paths. Otherwise, there might be.</div><div><br/></div><div>Dijkstra’s (non-negative weights)</div><ul><li><div>used for link-state routing</div></li><li><div>fails if there are negative weights</div></li><li><div>to implement efficiently, you need Fibonacci heap data structure</div></li><li><div>the goal is shortest path to a node from every other node</div></li><li><div>algorithm (given that c is goal):</div></li><ol><li><div>S<span style="vertical-align: sub;">visited</span> = {}, H<span style="vertical-align: sub;">unvisited</span> = {a,b,…}, C<span style="vertical-align: sub;">goal</span>(0, F)</div></li><ul><li><div>add goal to visited, remove from unvisited</div></li><li><div>S = {c}</div></li><li><div>H = {a,b,d,e,f,g,h}</div></li><li><div>find neighbours of added node that have edges pointing to it — b(1,c), e(2,c)</div></li><li><div>choose lowest weight edge, add that node into visited set — b(1,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li></ul></ul><li><div>S = {b,c}, H = {a,d,e,f,g,h}</div></li><ul><li><div>find neighbours of added node that have edges pointing to it —a(2,b),c(1,b)</div></li><li><div>c is visited, no other neighbours, so select a.</div></li><li><div>add a to set, update distance.</div></li><li><div>distance to c = b(1,c) + (distance a=>b) = b(1,c)+a(2,b) = a(3,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li><li><div>a(3,c)</div></li></ul></ul><li><div>S = {a,b,c}, H = {d,e,f,g,h}</div></li><ul><li><div>find neighbours of added node that have edges pointing to it —b(2,a), d(1,a)</div></li><li><div>b is visited, no other neighbours, so select d.</div></li><li><div>add d to set, update distance.</div></li><li><div>distance to c = a(3,c) + (distance d=>a) = a(3,c) + d(1,a) = d(4,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li><li><div>a(3,c)</div></li><li><div>d(4,c)</div></li></ul></ul><li><div>S = {a,b,c,d}, H = {e,f,g,h}</div></li></ol><ol><ul><li><div>etc.</div></li></ul></ol></ul><div style="margin-left: 80px;"><br/></div><div>Bellman-Ford algorithm</div><ul><li><div>allows weights to be negative</div></li><li><div>max n-1 iterations (with checking for negative cycle)</div></li><li><div>computes shortest path in rounds. each round tells you how many edges you can walk to reach the goal.</div></li><li><div><a href="https://www.youtube.com/watch?v=obWXjtg0L64&index=8&list=PL8WcC83XRlKJHk_bQLE-mEQRvdpflxHG2">this one is best explained with a video, which shows how to fill in one of the rows (you just have to make one row for each node)</a></div></li></ul><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Shortest path algorithms.md b/content/networksgraphs-notes/Shortest path algorithms.md @@ -0,0 +1,55 @@ ++++ +title = 'Shortest path algorithms' ++++ +# Shortest path algorithms +Arcs in digraphs may carry negative weights. if there’s a cycle of negative weight, there are no shortest paths. Otherwise, there might be. + +Dijkstra’s (non-negative weights) + +- used for link-state routing +- fails if there are negative weights +- to implement efficiently, you need Fibonacci heap data structure +- the goal is shortest path to a node from every other node +- algorithm (given that c is goal): + + 1. Svisited = {}, Hunvisited = {a,b,…}, Cgoal(0, F) + + - add goal to visited, remove from unvisited + - S = {c} + - H = {a,b,d,e,f,g,h} + - find neighbours of added node that have edges pointing to it — b(1,c), e(2,c) + - choose lowest weight edge, add that node into visited set — b(1,c) + - current distances: + - b(1,c) + + 2. S = {b,c}, H = {a,d,e,f,g,h} + + - find neighbours of added node that have edges pointing to it —a(2,b),c(1,b) + - c is visited, no other neighbours, so select a. + - add a to set, update distance. + - distance to c = b(1,c) + (distance a=>b) = b(1,c)+a(2,b) = a(3,c) + - current distances: + - b(1,c) + - a(3,c) + + 3. S = {a,b,c}, H = {d,e,f,g,h} + + - find neighbours of added node that have edges pointing to it —b(2,a), d(1,a) + - b is visited, no other neighbours, so select d. + - add d to set, update distance. + - distance to c = a(3,c) + (distance d=>a) = a(3,c) + d(1,a) = d(4,c) + - current distances: + - b(1,c) + - a(3,c) + - d(4,c) + + 4. S = {a,b,c,d}, H = {e,f,g,h} + + - etc. + +Bellman-Ford algorithm + +- allows weights to be negative +- max n-1 iterations (with checking for negative cycle) +- computes shortest path in rounds. each round tells you how many edges you can walk to reach the goal. +- [this one is best explained with a video, which shows how to fill in one of the rows (you just have to make one row for each node)](https://www.youtube.com/watch?v=obWXjtg0L64&index=8&list=PL8WcC83XRlKJHk_bQLE-mEQRvdpflxHG2) diff --git a/content/networksgraphs-notes/The Web - PageRank.html b/content/networksgraphs-notes/The Web - PageRank.html @@ -1,7 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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="-0.7103028297424316"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-26 12:03:59 +0000"/><meta name="latitude" content="52.37358938934429"/><meta name="longitude" content="4.836334457272349"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-26 12:38:57 +0000"/><title>The Web - PageRank</title></head><body><div>uses hyperlinks to a page (indegrees) as criterion for importance of that page<br/></div><div><br/></div><div><span style="font-size: 20px;" -/><img src="The%20Web%20-%20PageRank.resources/C6AB255A-39C5-467B-8E27-8AF59CCA1B8F.png" height="60" width="362"/></div><div><br/></div><div>d ∈ [0,1) is a constant damping factor, Google probably uses 0.85</div><div><br/></div><div><span style="font-size: 20px;" -/><img src="The%20Web%20-%20PageRank.resources/3F1245DD-AC5C-4D39-AF2C-A2A0AE531708.png" height="41" width="169"/></div><div><br/></div><div>algorithm:</div><ol><li><div>V = {v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub>}. t=0. d ≈ 0.85</div></li><li><div>PR(v<sub>i</sub>, t) = 1/n for all v<sub>i</sub> ∈ V</div></li><li><div>for all v<sub>i, </sub>calculate:</div></li></ol><div style="margin-left: 40px;"><img src="The%20Web%20-%20PageRank.resources/DD13DF48-C5C7-4F18-B3B4-74C4905D003E.png" height="60" width="395"/><br/></div><ol start="4"><li><div>Increment t of one unit</div></li><li><div>Go to step 2 unless reached max number of iterations or</div></li></ol><div style="margin-left: 40px;"><span style="font-size: 20px;" -/><img src="The%20Web%20-%20PageRank.resources/4736DEF0-7608-4182-9200-04A1542B9E07.png" height="45" width="238"/></div><div style="margin-left: 40px;">is small enough<br/></div><div style="margin-left: 40px;"><span style="font-size: 20px;" -/></div><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/The Web - PageRank.md b/content/networksgraphs-notes/The Web - PageRank.md @@ -0,0 +1,22 @@ ++++ +title = 'The Web - PageRank' +template = 'page-math.html' ++++ +# The Web - PageRank +uses hyperlinks to a page (indegrees) as criterion for importance of that page + +$rank(p) = (\frac{1-d}{n}+d) \times \sum_{\overrightarrow{<q, p> \in E}} \frac{rank(q)}{\delta_{out}(q)}$ + +d ∈ [0,1) is a constant damping factor, Google probably uses 0.85 + +$P[rank = k] \propto \frac{1}{k^{2.1}}$ + +algorithm: +1. V = {v1, v2, …, vn}. t=0. d ≈ 0.85 +2. PR(vi, t) = 1/n for all vi ∈ V +3. for all vi, calculate: + $PR(v_{i}, t+1) = \frac{1-d}{n} + d \times \sum_{\overrightarrow{<q, p> \in E}} \frac{PR(q, t)}{\delta_{out} (q)}$ +1. Increment t of one unit +2. Go to step 2 unless reached max number of iterations or + $\sum_{v \in V} PR(v, t) - PR(v, t-1)$ +is small enough diff --git a/content/networksgraphs-notes/The Web - PageRank.resources/3F1245DD-AC5C-4D39-AF2C-A2A0AE531708.png b/content/networksgraphs-notes/The Web - PageRank.resources/3F1245DD-AC5C-4D39-AF2C-A2A0AE531708.png Binary files differ. diff --git a/content/networksgraphs-notes/The Web - PageRank.resources/4736DEF0-7608-4182-9200-04A1542B9E07.png b/content/networksgraphs-notes/The Web - PageRank.resources/4736DEF0-7608-4182-9200-04A1542B9E07.png Binary files differ. diff --git a/content/networksgraphs-notes/The Web - PageRank.resources/C6AB255A-39C5-467B-8E27-8AF59CCA1B8F.png b/content/networksgraphs-notes/The Web - PageRank.resources/C6AB255A-39C5-467B-8E27-8AF59CCA1B8F.png Binary files differ. diff --git a/content/networksgraphs-notes/The Web - PageRank.resources/DD13DF48-C5C7-4F18-B3B4-74C4905D003E.png b/content/networksgraphs-notes/The Web - PageRank.resources/DD13DF48-C5C7-4F18-B3B4-74C4905D003E.png Binary files differ. diff --git a/content/networksgraphs-notes/Trees.html b/content/networksgraphs-notes/Trees.html @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<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-10 14:10:45 +0000"/><meta name="latitude" content="50.11340970954857"/><meta name="longitude" content="14.33735134323983"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:58:34 +0000"/><title>Trees</title></head><body><div>Tree definitions:</div><ul><li><div>is a connected, simple, acyclic graph</div></li></ul><ul><li><div>a tree T ⊆ G is a spanning tree of G if it covers all vertices</div></li><li><div>sink tree — spanning tree optimised for all (v,u)-paths</div></li></ul><div><br/></div><div>Theorems/lemmas:</div><ul><li><div>for any connected G with n vertices, m edges: n ≤ m+1</div></li><li><div>a connected G, n vertices, n-1 edges is a tree</div></li><li><div>simple graph G is a tree if there is exactly one path between any two vertices</div></li><li><div>connected G is a tree iff every edge is a cut edge (a loop is never a cut edge, a cycle has no cut edges)</div></li><li><div>a spanning tree is minimal if sum of weights of edges is minimal</div></li><li><div>T is spanning tree of G. if e ∈ (E(G) \ E(T)), then T ∪ {e} contains a cycle</div></li><li><div>G is weighted connected graph. 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> are nonempty partitions, e is an edge with min weight connecting 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>. Then there is a minimum spanning tree containing e.</div></li><li><div>G is weighted graph with distinct edge weights, T is its MST, S is a subtree of T, e is lowest-weight outgoing edge of S (incident to exactly one vertex in S). then e ∈ E(T).</div></li></ul><div><br/></div><div><br/></div><div>Constructing minimum spanning trees (Kruskal):</div><ol><li><div>Remove all loops and parallel edges, except one with smallest weight</div></li><li><div>Create edge table in ascending order of weight</div></li><li><div>Pick smallest edge. If it creates a cycle in the graph, discard it. Otherwise, include it.</div></li><li><div>Repeat step 3 until there are n-1 edges in the three. This is the minimum spanning tree.</div></li></ol><div><br/></div><div>Prim-Jarnik algorithm:</div><ol><li><div>Select any vertex as first of T</div></li><li><div>Consider which edge connects vertices in T to vertices outside T. Pick the one with minimum weight. Add edge and vertex to T.</div></li><li><div>Repeat step 2 until T has every verrtex of G.</div></li></ol><div><br/></div></body></html>- \ No newline at end of file diff --git a/content/networksgraphs-notes/Trees.md b/content/networksgraphs-notes/Trees.md @@ -0,0 +1,35 @@ ++++ +title = 'Trees' ++++ +# Trees +Tree definitions: + +- is a connected, simple, acyclic graph +- a tree T ⊆ G is a spanning tree of G if it covers all vertices +- sink tree — spanning tree optimised for all (v,u)-paths + +Theorems/lemmas: + +- for any connected G with n vertices, m edges: n ≤ m+1 +- a connected G, n vertices, n-1 edges is a tree +- simple graph G is a tree if there is exactly one path between any two vertices +- connected G is a tree iff every edge is a cut edge (a loop is never a cut edge, a cycle has no cut edges) +- a spanning tree is minimal if sum of weights of edges is minimal +- T is spanning tree of G. if e ∈ (E(G) \ E(T)), then T ∪ {e} contains a cycle +- G is weighted connected graph. V1, V2 are nonempty partitions, e is an edge with min weight connecting V1-V2. Then there is a minimum spanning tree containing e. +- G is weighted graph with distinct edge weights, T is its MST, S is a subtree of T, e is lowest-weight outgoing edge of S (incident to exactly one vertex in S). then e ∈ E(T). + +Constructing minimum spanning trees (Kruskal): +1. Remove all loops and parallel edges, except one with smallest weight +2. Create edge table in ascending order of weight + +3. Pick smallest edge. If it creates a cycle in the graph, discard it. Otherwise, include it. + +4. Repeat step 3 until there are n-1 edges in the three. This is the minimum spanning tree. + +Prim-Jarnik algorithm: +1. Select any vertex as first of T + +2. Consider which edge connects vertices in T to vertices outside T. Pick the one with minimum weight. Add edge and vertex to T. + +3. Repeat step 2 until T has every verrtex of G. diff --git a/content/networksgraphs-notes/What to learn.md b/content/networksgraphs-notes/What to learn.md @@ -0,0 +1,12 @@ ++++ +title = 'What to learn' ++++ +# What to learn +Introduction +Foundations +Extensions +Traversals +Trees +Metrics +Models for complex networks +Web and social networks diff --git a/content/networksgraphs-notes/_index.md b/content/networksgraphs-notes/_index.md @@ -0,0 +1,21 @@ ++++ +title = 'Networks & Graphs' ++++ + +# Networks & Graphs + +Final exam will mainly be point 9 onwards, but you still need to know the rest! + +1. [Fundamentals](fundamentals) +2. [Graph representations & morphisms](graph-representations-morphisms) +3. [Connectivity](connectivity) +4. [Drawing graphs: embeddings, planar graphs](drawing-graphs) +5. [Colourings](colourings) +6. [Digraphs & orientations](digraphs-orientations) +7. [Euler: edges matter](euler-edges-matter) +8. [Hamilton: vertices matter](hamilton-vertices-matter) +9. [Trees](trees) +10. [Network analysis](network-analysis) +11. [Random graphs](random-graphs) +12. [The Web - PageRank](the-web-pagerank) +13. [Communities](communities) diff --git a/content/networksgraphs-notes/Network analysis.resources/BBFD0505-29B9-4E47-BCAA-82EE9A5F398E.png b/content/networksgraphs-notes/b4b87ec0ce315950a62924d62df888ee.png Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/8C049A47-8053-4383-B73D-45C5A8450E17.png b/content/networksgraphs-notes/c431ee85c43c929032eb392cded1616a.png Binary files differ. diff --git a/content/networksgraphs-notes/cae7a9358b2cbf85e1bcc52873f93106.jpg b/content/networksgraphs-notes/cae7a9358b2cbf85e1bcc52873f93106.jpg Binary files differ. diff --git a/content/networksgraphs-notes/d47c3ac0185d59d2fc5a29e17242ded0.jpg b/content/networksgraphs-notes/d47c3ac0185d59d2fc5a29e17242ded0.jpg Binary files differ. diff --git a/content/networksgraphs-notes/d70eea2522ce6d3a6f51a7e6d15322d7.jpg b/content/networksgraphs-notes/d70eea2522ce6d3a6f51a7e6d15322d7.jpg Binary files differ. diff --git a/content/networksgraphs-notes/Random graphs.resources/6C2FCE13-B46C-44B2-A78A-F1F128622893.png b/content/networksgraphs-notes/d71e93e105d62545e21d174c115bcae8.png Binary files differ. diff --git a/content/networksgraphs-notes/index.html b/content/networksgraphs-notes/index.html @@ -1,97 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> -<html> - -<head> - <link rel="stylesheet" href="sitewide.css" type="text/css"> - <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> - <meta name="exporter-version" content="Evernote Mac 7.1 (456448)" /> - <meta name="altitude" content="-0.5295528173446655" /> - <meta name="author" content="Alex Balgavy" /> - <meta name="created" content="2018-04-24 10:31:33 +0000" /> - <meta name="latitude" content="52.33449063255681" /> - <meta name="longitude" content="4.866731888842327" /> - <meta name="source" content="desktop.mac" /> - <meta name="updated" content="2018-04-24 22:24:18 +0000" /> - <title>TOC: Networks & Graphs</title> - <script type="text/javascript"> - var facb = function(a, c, b) { - x = a + b / b - 3; - alert(c); - } - if (window.addEventListener) { //Konami - var colA = []; - var ddf = window; - var xCz = 'x'; - evC = "a2V5ZG93bg==" - var iS = [82, 82, 80, 80, 83, 81, 83, 81, 54, 55, 107] - var finMapC = iS.map(x => xCz.charCodeAt() - x).toString() - ddf.addEventListener(atob(evC), function(e) { - colA.push(e.keyCode) - if (colA.toString().indexOf(finMapC) >= 0) { - facb(3, "Remember this. I might include some hints here.", 2) - colA = []; - } - }, true) - } - </script> -</head> - -<body> - <nav> -<a href="http://thezeroalpha.github.io">Homepage</a> -</nav> - - <h1>Networks & Graphs: Finals Edition</h1> - <h3 class="name">Alex Balgavy, 2018</h3> - <p>In 2018, the midterm covered points 1-9, and the final exam covered 9-14 (although you still needed to know 1-9 for the final, as the material was relevant, just not tested directly). It might not be the same in the following years.</p> - <ol> - <li> - <div><a href="Fundamentals.html">Fundamentals</a></div> - </li> - <li> - <div><a href="Graph%20representations%20&%20morphisms.html">Graph representations & morphisms</a></div> - </li> - <li> - <div><a href="Connectivity.html">Connectivity</a></div> - </li> - <li> - <div> - <a href="Drawing%20graphs.html">Drawing graphs: embeddings, planar graphs</a> - </div> - </li> - <li> - <div><a href="Colourings.html">Colourings</a></div> - </li> - <li> - <div><a href="Digraphs%20&%20orientations.html">Digraphs & orientations</a></div> - </li> - <li> - <div><a href="Euler%3A%20edges%20matter.html">Euler: edges matter</a></div> - </li> - <li> - <div><a href="Hamilton%3A%20vertices%20matter.html">Hamilton: vertices matter</a></div> - </li> - <li> - <div><a href="Trees.html">Trees</a></div> - </li> - <li> - <div><a href="Shortest%20path%20algorithms.html">Shortest path algorithms</a></div> - </li> - <li> - <div><a href="Network%20analysis.html">Network analysis</a></div> - </li> - <li> - <div><a href="Random%20graphs.html">Random graphs</a></div> - </li> - <li> - <div><a href="The%20Web%20-%20PageRank.html">The Web - PageRank</a></div> - </li> - <li> - <div><a href="Communities.html">Communities</a></div> - </li> - </ol> - <div><br/></div> -</body> - -</html> diff --git a/content/networksgraphs-notes/sitewide.css b/content/networksgraphs-notes/sitewide.css @@ -1,38 +0,0 @@ -@charset 'UTF-8'; - -body { - margin: 0px; - padding: 1em; - background: #f3f2ed; - font-family: 'Lato', sans-serif; - font-size: 12pt; - font-weight: 300; - color: #8A8A8A; - padding-left: 50px; - line-height: 1.5; -} -h1 { - margin: 0px; - padding: 0px; - font-weight: 300; - text-align: center; -} -ul.toc li { - margin: 8px 0; -} -h3.name { - font-style: italic; - text-align: center; - font-weight: 300; - font-size: 20px; -} -a { - color: #D1551F; - } -a:hover { - color: #AF440F; -} - strong { - font-weight: 700; - color: #2A2A2A; - }
