1.11

# 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.

## If you’re really curious:

As we have seen in an undirected graph the degree of a node is simply the number of edges attached to it, we define this mathematically using the value k, so we might say that the degree of node j is written kj

However, a social network like Twitter is more complicated. Twitter is an example of a directed graph, one in which the edges are orientated (i.e. they have direction – in the following diagrams the direction is indicated by the arrows). If we look at Twitter’s Follow relationship, it is clear that the direction of the edges is important. In Twitter you could follow celebrities who are not following you back, or there might be people following you and you are not following them.

These kinds of relationships form what is classified as a directed graph, in which we cannot use node degree without distinguishing between the in-degree and the out-degree.

In this context, the in-degree is the number of directed edges that point into the node (more formally we say they are incident on a node), and the out-degree is the number of directed edges that originate from a node. The total degree of the node is the summation of the in-degree and the out-degree, given that we count double edges (where the arrow shows direction both in and out of a node) as one only. Consider the following directed graph.

For node i we can see that there are two edges pointing into the node, and four edges pointing out from the node. So we can say that for node i, the in-degree is 2, in mathematical terms, kiin = 2 and the out-degree is 4, in mathematical terms, kiout = 4. Finally the total degree of the node, in mathematical terms, is ki = 4.

The average degree of a graph is used to measure the number of edges compared to the number of nodes. Remember that to do this in an undirected graph we simply divide the summation of all nodes’ degree by the total number of nodes N.

This can be calculated using the following equation, where E is the number of edges, N is the number of nodes and ki is the degree of node i.

Note that we count each edge twice (the 2E in the equation above) this is because each edge links two nodes and counts in the degree of both nodes.

In a directed graph we must calculate the average degree differently as we no longer have to count each edge twice, instead we simply divide the total number of edges by the total number of nodes use the following equation:

We have also seen that in a graph, a path is a sequence of nodes in which each node is connected by an edge to the next. In a directed graph, paths are formed following the direction of the edges. Let’s consider the following directed graph:

There are two paths between A and F, ACDF or ACEF, the path length in both cases equals to 3. In a directed graph the paths are not necessary symmetric, which means that the paths you will need to get from any node X to another Y are not always the same when you travel backwards from Y to X and may have different lengths.

To illustrate this, if we look at the path between B and C in the graph above, following the direction of edges we get BAC and the path length equals 2, but the path back (from C to B) is CB with the length equal to 1.