Lecture 1 – Introduction – 26-10-2020
1.2 – What is a network?
A graph
- = a set of nodes/vertices and links/edges
(lines) modeling a network
- Between the nodes, a set of links
Adjacency matrix: symmetric network
- 1 = direct connection
- 0 = no direct connection
Symmetry versus a-symmetry
- Symmetry: (-)
o A is relative of B
o Road between two cities
- Asymmetry (→)
o Hierarchical: A is boss of B
o Nonhierarchical: one way traffic
▪ Intransitivity
▪ Examples: roundabout, ringways (one
direction)
▪ From a to b to c to d.
Adjacency matrix: non symmetric network
- From A to C and from C to B.
- From C to A no relation
Neighbors, paths and cycles
- Neighbors: Nodes i and j are neighbors if i and j have a direct link
- Path: a sequence of nodes where each consecutive pair is a neighbor
- Cycle: is a path with at least three different nodes where the first and the last node
are the same
Distance: Koenig index
- Minimum number of links one has to pass when one
goes to the node furthest away.
- Maximum of minimum: longest of all shortest routes
- KI(A) = 9, G is furthest away and it takes 9 steps to go
from A to G
- KI(A) = 4, I and J are nodes furthest away, so it is 4.
1
,The Koenig index: the Diameter
- Number of links (edges) in the shortest path between the two most remote nodes
- Diameter: maximum of all Koenig indexes (maximum of minimums)
o Diffusion of information
o Connectedness of the network: how well related the network is
After knowledge clip:
Give the Koenig index of b:
- Furthest node away: e
- b -> d -> e = 11
The six degrees of Kevin Bacon
- Everybody on this planet is separated by only six other
people. Six degrees of separation.
Lecture 2: Network characteristics – 27-10-2020
1.3 Shortest path
Path length:
- In book of EK, all paths have equal lengths
- In general: paths have different lengths (weight/cost/times)
- Shortest path algorithm: Edsger Dijkstra
Dijkstra algorithm
- Phases of algorithm
o Initialization
o Do something
o If something not satisfied, go to the 2. Else stop
1. Source node = current node: Set its value to zero and set the value of all other nodes
to infinity. Mark nodes as unvisited
2. For each unvisited node that is adjacent to the current node: if the value of the
current node plus the value of the edge is less than the value of the adjacent node,
change the value of the adjacent node to this value. Otherwise, leave value as it is
3. Set the current node to visited. If there are still some unvisited nodes, set the
unvisited node with the smallest value as the new current node, and go to step 2. If
there are no unvisited nodes, then we are done.
o Stopping criteria: are there still unvisited nodes, go to step 2.
2
,Example Dijkstra’s algorithm
Initialization Step 1: a-b = 0+2, a-d = 0+4
Step 2: b-d = 8 and 4 is smaller so leave d as Step 3: b-e = 9 is bigger than d-e = 6 so set it
4 so 6
Step 4: e-c = 9 is smaller than b-c = 10 so set Step 5: set it as visited
is to 9
Remarks
- Shortest path algorithm: find shortest path of node to all other nodes
o Relatively fast (P-problem)
o Routing problems (NP-hard problem)
o P = polynomial = t+t^2+t^3
- Algorithm basis for Tomtom/Garmin/google route applications
- Most network problems are NP-hard (need quite a lot of computer power to solve it)
o Routing
o Scheduling
o Assignment
- You are always talking about shortest path, so you need an algorithm to come up
with the shortest path.
3
, After knowledge clip:
Question: in what way is the shortest path different from the
travelling salesmen algorithm (you have to go from A-B-C-D-E-A)
- Travelling Salesmen: Every node has to be visited.
- Dijkstra: does not matter how many points you visit, only need
to go the fastest to your end destination.
Example: Can you apply Dijkstra’s Algorithm?
- 9 nodes
- How many evaluations do we need than in total?
o O(N^2) = second order polynomial.
1.4 – Network characteristics
General network characteristics
- Diameter: the maximum of all the Koenig indexes
o How well the network is connected: very big = good connected
o Sum: the edges between the nodes
- Density
o Actual connections divided by the number of potential connections
o Potential connections depends on whether the network is directed
▪ (n*(n-1) /2 = n2-n / 2 (symmetric relations, half of the
matrix)
- Average path length
o Average shortest path between any possible node pair
o Let computers do this.
o How connected a network is
Random networks
- Take a set of nodes and randomly assign some lines.
- Each pair of nodes (I,j) has probability p(density) to become connected
o Already with a small probability, the network becomes good connected
- For example, with 3 nodes complete network forms with p^3
- Result: random network
o Large degree of connectivity
o However, no central hubs
4
1.2 – What is a network?
A graph
- = a set of nodes/vertices and links/edges
(lines) modeling a network
- Between the nodes, a set of links
Adjacency matrix: symmetric network
- 1 = direct connection
- 0 = no direct connection
Symmetry versus a-symmetry
- Symmetry: (-)
o A is relative of B
o Road between two cities
- Asymmetry (→)
o Hierarchical: A is boss of B
o Nonhierarchical: one way traffic
▪ Intransitivity
▪ Examples: roundabout, ringways (one
direction)
▪ From a to b to c to d.
Adjacency matrix: non symmetric network
- From A to C and from C to B.
- From C to A no relation
Neighbors, paths and cycles
- Neighbors: Nodes i and j are neighbors if i and j have a direct link
- Path: a sequence of nodes where each consecutive pair is a neighbor
- Cycle: is a path with at least three different nodes where the first and the last node
are the same
Distance: Koenig index
- Minimum number of links one has to pass when one
goes to the node furthest away.
- Maximum of minimum: longest of all shortest routes
- KI(A) = 9, G is furthest away and it takes 9 steps to go
from A to G
- KI(A) = 4, I and J are nodes furthest away, so it is 4.
1
,The Koenig index: the Diameter
- Number of links (edges) in the shortest path between the two most remote nodes
- Diameter: maximum of all Koenig indexes (maximum of minimums)
o Diffusion of information
o Connectedness of the network: how well related the network is
After knowledge clip:
Give the Koenig index of b:
- Furthest node away: e
- b -> d -> e = 11
The six degrees of Kevin Bacon
- Everybody on this planet is separated by only six other
people. Six degrees of separation.
Lecture 2: Network characteristics – 27-10-2020
1.3 Shortest path
Path length:
- In book of EK, all paths have equal lengths
- In general: paths have different lengths (weight/cost/times)
- Shortest path algorithm: Edsger Dijkstra
Dijkstra algorithm
- Phases of algorithm
o Initialization
o Do something
o If something not satisfied, go to the 2. Else stop
1. Source node = current node: Set its value to zero and set the value of all other nodes
to infinity. Mark nodes as unvisited
2. For each unvisited node that is adjacent to the current node: if the value of the
current node plus the value of the edge is less than the value of the adjacent node,
change the value of the adjacent node to this value. Otherwise, leave value as it is
3. Set the current node to visited. If there are still some unvisited nodes, set the
unvisited node with the smallest value as the new current node, and go to step 2. If
there are no unvisited nodes, then we are done.
o Stopping criteria: are there still unvisited nodes, go to step 2.
2
,Example Dijkstra’s algorithm
Initialization Step 1: a-b = 0+2, a-d = 0+4
Step 2: b-d = 8 and 4 is smaller so leave d as Step 3: b-e = 9 is bigger than d-e = 6 so set it
4 so 6
Step 4: e-c = 9 is smaller than b-c = 10 so set Step 5: set it as visited
is to 9
Remarks
- Shortest path algorithm: find shortest path of node to all other nodes
o Relatively fast (P-problem)
o Routing problems (NP-hard problem)
o P = polynomial = t+t^2+t^3
- Algorithm basis for Tomtom/Garmin/google route applications
- Most network problems are NP-hard (need quite a lot of computer power to solve it)
o Routing
o Scheduling
o Assignment
- You are always talking about shortest path, so you need an algorithm to come up
with the shortest path.
3
, After knowledge clip:
Question: in what way is the shortest path different from the
travelling salesmen algorithm (you have to go from A-B-C-D-E-A)
- Travelling Salesmen: Every node has to be visited.
- Dijkstra: does not matter how many points you visit, only need
to go the fastest to your end destination.
Example: Can you apply Dijkstra’s Algorithm?
- 9 nodes
- How many evaluations do we need than in total?
o O(N^2) = second order polynomial.
1.4 – Network characteristics
General network characteristics
- Diameter: the maximum of all the Koenig indexes
o How well the network is connected: very big = good connected
o Sum: the edges between the nodes
- Density
o Actual connections divided by the number of potential connections
o Potential connections depends on whether the network is directed
▪ (n*(n-1) /2 = n2-n / 2 (symmetric relations, half of the
matrix)
- Average path length
o Average shortest path between any possible node pair
o Let computers do this.
o How connected a network is
Random networks
- Take a set of nodes and randomly assign some lines.
- Each pair of nodes (I,j) has probability p(density) to become connected
o Already with a small probability, the network becomes good connected
- For example, with 3 nodes complete network forms with p^3
- Result: random network
o Large degree of connectivity
o However, no central hubs
4
