Network Density

up:: 041 MOC Graph Theory

Image from Sparse coding: A simple exploration | by Morgan | metaflow-ai.

Given a network $G$ with $N$ nodes and $m$ edges, we calculate its density (or connectance) as the fraction of all possible edges that it has.

That is,

$$\rho =\frac{m}{\left(\genfrac{}{}{0ex}{}{N}{2}\right)}$$

For undirected Simple Graphs, we have that

$$\rho =\frac{2m}{N(N-1)}=\frac{⟨k⟩}{N-1}$$

by the definition of Average Degree.

Miscellaneous

A network’s density points to how “interconnected” it is. In particular, one says that a network is sparse if

$$\underset{n\to \infty }{\lim }\rho =0$$

and dense if it isn’t sparse.

This seems to point to a Second Brain’s “effectiveness”: The best Second Brains are always dense networks, since it’s best to add new information by connecting it to previous knowledge; conversely, networks that grow with isolated (or poorly connected) nodes tend to be sparse.

---

References

• NEWMAN, Mark. Networks. Oxford university press, 2018.