Network analysis
Table of Contents
Network analysis ..............................................................................................................1
Lecture 1: Graph and network characteristics ............................................................................ 2
Lecture 2: Weak and strong ties ................................................................................................ 4
Lecture 3: Networks in context ................................................................................................. 8
Lecture 4: Networks and games .............................................................................................. 11
Lecture 5: The empirics of trade ............................................................................................. 13
Lecture 6: Games on networks ............................................................................................... 15
Lecture 7: Bipartite graphs & trade ......................................................................................... 19
Lecture 8: Modeling intermediate linkages and international dependence ............................... 22
Lecture 9: Follow the crowd ................................................................................................... 24
Lecture 10: Following the crowd ............................................................................................. 26
Lecture 11: Power-laws & superstars ...................................................................................... 30
Lecture 12: Clustering and agglomeration ............................................................................... 32
,Lecture 1: Graph and network characteristics
Transportation & logistics are intrinsically related with networks
• Operations research describes (near) optimal decisions given network structure
• Socio-economies theories describe decision taking into account changes in the
network structure
Increase in attention to network analysis:
• Decrease in transportation and information/communication costs
• Increase in availability of (transport) data (remote sensing, API’s, real time traffic
information)
Network: any collection of objects in which some pairs of these objects are connected
What is a graph: a set of nodes/vertices and
links/edges (lines) modeling a network
Symmetry: A is a relative of B
Asymmetry:
1. Hierarchical: A is the boss of B
2. Non-hierarchical: One way traffic
2
,Adjacency matrix
Neighbors: nodes i and j are neighbors is i and j have a direct link
Path: a sequence of nodes where each consecutive pair is a neighbor
Cycle: a path with at least three different nodes where the first and last node are the same
Connectivity: for every pair of nodes, there is a path between them
König index of a node: minimum number of links one has to pass when one goes to the node
furthest away
• Maximum of minimum: longest of all shortest
Diameter: maximum of König indices:
• Diffusion of information
• Centrality
How to find the shortest path:
1. Begin with a source node (current node with value 0). Set value of all other nodes to
infinity. Mark all 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 the value as is
3. If there are still some unvisited nodes, set the unvisited node with the smallest value
as the new current node, go to step 2
3
, Lecture 2: Weak and strong ties
Bridging capital: social network among group (same religion)
Bonding capital: connections you make from your own network to another group
General network characteristics:
• Diameter: longest of all the shortest paths (maximum of all Koenig indicec)
• Density:
o Actual connections/potential connections
o Potential connections depend on whether being directed
o Undirected network: can go between points (divide by 2)
• Average path length: average shortest path between any possible node pair
Random networks:
• Take a set of nodes
• Each pair of nodes (i, j) has probability p (density) to become connected
Probability is 0.02 Probability is 0.08
Dyads and triads
• Dyad: group of two things/people/firms
o Firm-customer
o Mother-child
o Giver-receiver
o Origin-destination
• Triad: network is a group of three things/people/firms
4
Table of Contents
Network analysis ..............................................................................................................1
Lecture 1: Graph and network characteristics ............................................................................ 2
Lecture 2: Weak and strong ties ................................................................................................ 4
Lecture 3: Networks in context ................................................................................................. 8
Lecture 4: Networks and games .............................................................................................. 11
Lecture 5: The empirics of trade ............................................................................................. 13
Lecture 6: Games on networks ............................................................................................... 15
Lecture 7: Bipartite graphs & trade ......................................................................................... 19
Lecture 8: Modeling intermediate linkages and international dependence ............................... 22
Lecture 9: Follow the crowd ................................................................................................... 24
Lecture 10: Following the crowd ............................................................................................. 26
Lecture 11: Power-laws & superstars ...................................................................................... 30
Lecture 12: Clustering and agglomeration ............................................................................... 32
,Lecture 1: Graph and network characteristics
Transportation & logistics are intrinsically related with networks
• Operations research describes (near) optimal decisions given network structure
• Socio-economies theories describe decision taking into account changes in the
network structure
Increase in attention to network analysis:
• Decrease in transportation and information/communication costs
• Increase in availability of (transport) data (remote sensing, API’s, real time traffic
information)
Network: any collection of objects in which some pairs of these objects are connected
What is a graph: a set of nodes/vertices and
links/edges (lines) modeling a network
Symmetry: A is a relative of B
Asymmetry:
1. Hierarchical: A is the boss of B
2. Non-hierarchical: One way traffic
2
,Adjacency matrix
Neighbors: nodes i and j are neighbors is i and j have a direct link
Path: a sequence of nodes where each consecutive pair is a neighbor
Cycle: a path with at least three different nodes where the first and last node are the same
Connectivity: for every pair of nodes, there is a path between them
König index of a node: minimum number of links one has to pass when one goes to the node
furthest away
• Maximum of minimum: longest of all shortest
Diameter: maximum of König indices:
• Diffusion of information
• Centrality
How to find the shortest path:
1. Begin with a source node (current node with value 0). Set value of all other nodes to
infinity. Mark all 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 the value as is
3. If there are still some unvisited nodes, set the unvisited node with the smallest value
as the new current node, go to step 2
3
, Lecture 2: Weak and strong ties
Bridging capital: social network among group (same religion)
Bonding capital: connections you make from your own network to another group
General network characteristics:
• Diameter: longest of all the shortest paths (maximum of all Koenig indicec)
• Density:
o Actual connections/potential connections
o Potential connections depend on whether being directed
o Undirected network: can go between points (divide by 2)
• Average path length: average shortest path between any possible node pair
Random networks:
• Take a set of nodes
• Each pair of nodes (i, j) has probability p (density) to become connected
Probability is 0.02 Probability is 0.08
Dyads and triads
• Dyad: group of two things/people/firms
o Firm-customer
o Mother-child
o Giver-receiver
o Origin-destination
• Triad: network is a group of three things/people/firms
4
