Network distance – Hugo Contreras

0 3


In my previous posts (one and two), I discussed networks and the degree of a node to better understand how networks can be a useful tool in relating characters and dialogue from my favorite movie, Die Hard. Today, I’ll discuss edges, another metric that can help understand the characteristics
of a network.

An edge represents a connection between two nodes, and the distance between these two nodes in a given network is defined as the shortest sequence of edges connecting them. To get a better idea of the distance in a network, I can average the distance over all possible pairings. This is known as the characteristic path length.

Fig. 1 Dialog network for Hans’ crew and McClane counting all the edges

I’ve labeled the edges with numbers so we can study the network. This particular network has 13 edges. Let’s consider the maximum number or edges in a network. For example, in the network above, there are 10 characters and a possible 45 pairs of nodes. In a network with “N” nodes, there are N(N-1)/2 possible pairings. So, as the number of nodes N grows, the number of possible connections grows as N². See below for a more “rigorous” argument. I will recall this fact when I discuss Metcalfe’s law on
telecommunication networks.

Hans, being a star (see previous post for the definition of a star) keeps the distance between the nodes in the network relatively small. The distance between Hans and any other character in the network is 1 (except for Tony where the distance between he and Hans is two). There are two paths for the shortest connection between Tony and any other member of Hans’
crew:

  • Tony to Hans to crew member
  • Tony to McClane (the bridge) to Franco

The longest distance between nodes is three. It belongs to Tony and any of the members of Hans’ crew, except Franco. I won’t bore you with the details (but you can perform the computation by hand or using Python), but the characteristic path length is 1.84. This is the result of adding all possible distances and then dividing them by the number of all possible pairs. On average, it takes 1.84 steps to move between any two pairs.

I’ve gone over the notion of edges in a network, the distance between nodes and the characteristic path length (that’s to say the average distance between all possible pairs of nodes). In the next post, I’ll cover an interesting result about edges and nodes, so stay tuned!

You might also like

Pin It on Pinterest

Share This

Share this post with your friends!

WhatsApp chat