These are lecture notes and basically a summary of the course Network Analysis made in the academic year of 2020/2021. I got an 8.5 for my exam using this notes.
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper jillvandertuin. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,99. Je zit daarna nergens aan vast.
