1. Overview

In this tutorial, we’ll discuss the density of a graph. We’ll present how to calculate the density of different graphs with examples.

2. What Is Density?

Graph density represents the ratio between the edges present in a graph and the maximum number of edges that the graph can contain. Conceptually, it provides an idea of how dense a graph is in terms of edge connectivity.

It’s particularly useful when we have a vast network and want to add new edges to the network. Moreover, graph density gives us an idea of how many edges we can still add to the network.

Now, before deriving the formula for graph density, let’s talk about how to calculate the maximum number of edges in a simple directed and undirected graph. Let’s look at a simple undirected graph G_1:

1.drawio

Here, the graph G_1 contains 4 nodes and 4 edges. We’re interested in knowing the maximum number of edges G_1 can contain. Can we still add edges? Let’s see:

2.drawio

We added 2 more edges to the graph G_1. Therefore, the graph now contains 4 nodes and 6 edges. We can’t add any more edges to it. Now, we want to derive a standard formula to calculate the maximum number of edges in a simple undirected graph:

    [Max_{U} = \frac{|V| * (|V| - 1)}{2}]

Let’s check the formula for G_1:

    [Max_{G_{1}} = \frac{|V| * (|V| - 1)}{2} = \frac{4 * (4 - 1)}{2} = \frac{12}{2} = 6]

Similarly, we can replace each undirected edge with two bidirectional edges in a directed graph. Hence, the maximum number of edges can be calculated using a similar formula:

    [Max_{D} = {|V| * (|V| - 1)}]

We can now define the graph density formula. The edges present in a graph G (V, E) are divided by the maximum number of edges that the graph can contain. Let’s see the formula for a simple undirected graph:

    [DEN_{U} = \frac{\frac{|E|}{|V| * (|V| - 1)}}{2} =\frac{2|E|}{|V| * (|V| - 1)}]

Similarly, we can rewrite the previous density formula for a directed graph:

    [DEN_{D} = \frac{|E|}{|V| * (|V| - 1)}]

3. Properties

For a complete directed or undirected graph, the density is always \textbf{1}. Therefore, if we recollect the definition, we can easily verify this property. The density is the ratio of edges present in a graph divided by the maximum possible edges. In the case of a complete directed or undirected graph, it already has the maximum number of edges, and we can’t add any more edges to it. Hence, the density will be 1. Additionally, it also indicates the graph is fully dense.

A graph with all isolated vertices has a density of \textbf{0}. Moreover, it denotes there are no edges in the graph, and the number of edges that can be added to the graph is equal to the maximum number of edges.

4. Example

In this section, we’ll calculate the density for a directed and an undirected graph. Let’s take a directed graph G_2 first:

fgdsgfg.drawio-2

The directed graph G_2 has 5 vertices and 6 edges. But in order to calculate density, first, we need to calculate the maximum number of edges possible in G_2:

    [Max_{G_{2}} = {|V| * (|V| - 1)} = 5 * (5 -1) = 20]

Finally, we divide the number of edge present in \mathbf{G_2} with the maximum number of edges in order to calculate density:

    [DEN_{G_{2}} = \frac{|E|}{|V| * (|V| - 1)} = \frac{6}{Max_{G_{2}}} = \frac{6}{20} = 0.3]

Similarly, let’s take an undirected graph G_3:

fgdsgfg.drawio-3

The undirected graph G_3 has 6 vertices and 8 edges. First, we’ll calculate the maximum number of edges for G_3:

    [Max_{G_{3}} = \frac{|V| * (|V| - 1)}{2} = \frac{6 * (6 - 1)}{2} = \frac{6 * 5}{2} = 15]

Finally, we divide the number of edges present in \mathbf{G_3} with the maximum number of edges in order to calculate density:

    [DEN_{G_{3}} = \frac{\frac{|E|}{|V| * (|V| - 1)}}{2} = \frac{8}{Max_{G_{3}}}= \frac{8}{15} = 0.53]

5. Conclusion

In this tutorial, we discussed graph density in detail. We first derived the graph density formula. We also explained the calculation using a directed and an undirected graph.