Of Notes

Network Densities

2 min read · revised 19 October 2026 · referred to by 1 note · ·

The mean degree from Macroscopic Mean Values counts how many edges a typical vertex has, but it does not tell us how full the graph is.

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 with adjacency matrix and order .

The answer depends on whether the graph is directed and whether it is simple (no self-edges).

Directed Graphs

The adjacency matrix has entries , and each entry is one possible edge.

So the maximal number of edges is and the density is the fraction of entries which are one:

Simple Directed Graphs

A simple graph has no self-edges, so we must exclude the diagonal entries .

There are diagonal entries in an matrix, which leaves possible edges:

Nondirected Graphs

For an undirected graph the matrix is symmetric, , so counting every entry would count each edge twice.

We only sum one triangle of the matrix. Keeping the diagonal, we count the entries with :

which is diagonal entries plus off-diagonal ones. The density is then:

Simple Nondirected Graphs

Removing the self-edges again drops the diagonal entries, leaving:

which is the maximal number of edges of any simple graph. So we count the edges and divide by this maximum:

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 , we substitute :

which says that the density is the mean degree measured as a fraction of the other vertices each vertex could connect to.

For directed graphs the same works with the mean in- or out-degree, giving , since each vertex has possible targets instead of .

Sparse Networks

Real networks grow while each vertex keeps a finite number of connections, so as grows.

Fixing the mean degree and letting grow in the expression above:

so the density vanishes as even though the number of edges grows linearly with .

The number of possible edges grows like , much faster than the number of real edges, so large networks are sparse graphs: only a vanishing fraction of all possible edges is present.

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card