Degree and Path Length

Essential knowledge:

• The degree of a node is the number of connections that it has to other nodes in the network. In a social network if you have 100 friends then the node that represents you has a degree of 100.

• Path length is simply the distance between two nodes, measured as the number of edges between them. If Amy is Brad’s friend, and Brad is Calvin’s friend, then the path length between Amy and Calvin is 2.

You may be interested that:

A graph is a mathematical representation of a network. To understand what the Degree and Path Length are, we need to consider graphs in greater detail.

Let’s start with Facebook which a relatively simple network as it is an example of an an undirected graph, meaning that the edges represent a relationship that is equally true in both directions. For example, consider collaboration networks or friendship relationships in Facebook; if you collaborate with someone or if you add someone as a friend in Facebook, it does not matter who initiated that relation, once you’ve added someone to your friend list you will appear as a friend in their friends’ lists as well. Therefore, in an undirected graph the edge direction is not important.

This means that in an undirected network the degree of a node is simply the summation of all the edges linked to it. For example, consider the following network:

The average degree of an undirected graph is used to measure the number of edges compared to the number of nodes. To do this we simply divide the summation of all nodes’ degree by the total number of nodes. For example in the graph above the nodes have the following degrees: A=2, B=2, C=4, D=2, E=3, F=2, G=2, H=1. Adding these all together we get 18, and since there are 8 nodes the average degree is 18 divided by 8, or 2.25.

In a graph, a path is a sequence of nodes in which each node is connected by an edge to the next. The path length corresponds to the number of edges in the path. For example, in the network above the paths between A and F are: ACDF, ACEF, ABCDF, ABCEF, with path lengths 3,3,4,4 respectively.

The shortest paths are the first two. Note that as the direction is not important the paths are symmetric, so the paths from A to F are simply the reverse of the paths from F to A.

LinkedIn is a good example of a social network that uses paths and path lengths to show how you might connect to other people. When you look at someone’s profile page, it will calculate the shortest path from you to them, and show you the first person in that path who might be able to introduce you.

Consider your node in your social network. What is your degree, and how does it compare with other people’s in the same network?

If you’re really curious:

Network structure can be more complicated than the example above.

In a directed network the edges between nodes have a source node and a destination node, in other words the relationship only works in one direction. Twitter is a social network that uses direction – in Twitter when you follow someone, it does not mean that they follow you. Facebook on the other hand is an undirected network – when you become someone’s friend, they become your friend as well. Figuring out the average degree on a directed network like Twitter is therefore a bit more complicated.

In some networks it also makes sense to place weights on the edges to show how strong or weak they are in relation to the other edges in the graph. For example, consider a network of film actors where actors are connected if they have appeared in the same film together. In this example the weight could represent the number of times they had co-starred together. Two actors connected with a high weight are more heavily connected (they have appeared in more films together) than two that are connected with a low weight.

Some networks are both directed and weighted. Ebay is a good example. In the Ebay network nodes are people, and edges represent a sale. It is directed because if I buy something from you it is different than if you buy something from me. And it is weighted, as I may have bought many times from one person, but only once from another person.

Modeling networks as edges and nodes, with and without direction and weight, is useful as it allows us to develop tools for analysing networks and understanding how they behave and then apply them to all sorts of real world networks regardless of what the nodes and edges actually represent.