in the following answer https://math.stackexchange.com/a/1526421/28816 there are two formulas for computing the density of, respectively, simple undirected and simple directed graphs.
Simple undirected graphs:
$$D = \frac{2|E|}{|V|(|V| - 1)}$$
Simple directed graphs:
$$D = \frac{|E|}{|V|(|V| - 1)}$$
Now, I was thinking about multigraphs. How is the density of such graphs computed? What would be the formula for the density of, respectively, an undirected and directed multigraph which has multiple edges and possibly loops?
Thank you for the attention.
I mean, it really comes down to what you define density to be. In practice, it is simply shorthand for the fraction of edges in a graph to the maximum possible case. Let $f(n)$ be the maximum number of possible edges in a graph $G$ with $n$ nodes, then the “density” of $G$ would typically be defined as:
$$\frac{|E|}{f(|V|)}$$
There are $\binom{n}{m}$ possible $m$-edges in a graph with $n$ nodes. So in the undirected case, the density of $G$ with $n$ nodes is:
$$\frac{|E|}{\sum_{k=2}^n \binom{n}{k}}$$
If these are directed $m$-edges, each edge could go into any of the $m$ vertices it is between. For a 2-edge, there are 2 orientations, etc. With this we get:
$$\frac{|E|}{\sum_{k=2}^n k \cdot \binom{n}{k}}$$
But really, this is just a fraction. Density isn’t a particularly valuable graph property, it’s just convenient notation.
If you allow multiple edges, there are an infinite number of possible edges for the graph, unless you have a maximum number of times a given edge can be repeated. If each edge can have upto $x$ copies, there are $x$ times as many possible edges. It’s just a matter a simple combinatorics based upon whatever restricts you place upon $G$...