Of Notes
Network Densities
Table of Contents
The mean degree
To measure that we compare the number of edges we actually have to the number of edges we could possibly have.
Counting Possible Edges
We take a graph
The answer depends on whether the graph is directed and whether it is simple (no self-edges).
Directed Graphs
The adjacency matrix has
So the maximal number of edges is
Simple Directed Graphs
A simple graph has no self-edges, so we must exclude the diagonal entries
There are
Nondirected Graphs
For an undirected graph the matrix is symmetric,
We only sum one triangle of the matrix. Keeping the diagonal, we count the entries with
which is
Simple Nondirected Graphs
Removing the self-edges again drops the
which is the maximal number of edges of any simple graph. So we count the edges
In every case the recipe is the same: divide the number of edges present by the number of entries we set to one if the graph were complete, which is exactly the sum in the numerator.
Density from the Mean Degree
We can rewrite the simple nondirected case using the mean degree.
Since
which says that the density is the mean degree measured as a fraction of the
For directed graphs the same works with the mean in- or out-degree, giving
Sparse Networks
Real networks grow while each vertex keeps a finite number of connections, so
Fixing the mean degree and letting
so the density vanishes as
The number of possible edges grows like