Graph density denotes the proportion of edges in a graph that are connected vs unconnected. A simple graph with near the maximum amount of possible edges will have high density, while a simple graph with almost no edges will have low density.
Definition
Let E be the number of edges in a graph, V the number of vertices. Density is defined by the following formula for simple undirected graphs:
And half that for directed graphs.
Properties
The maximum possible density is 1, and the minimum density is zero. The definitions for what delimits a sparse graph vs a dense one doesn’t have a clear delimitation, but as density approaches zero it becomes more and more sparse, while the more it approaches one it becomes more and more dense.
Applications
Graph density can help with determining the breaking point in space efficiency for different data structures, for example at what density does an adjacency list become more efficient than an adjacency matrix.