What is the definition of the density of a graph?
I am reading a paper which is regarding to the graph theory.
It is applied theory to computer science.
My background was industrial and management engineering, and computer science and engineering right now.
I am freshman at a grad school. Maybe because of the reason, I don't fully understand and know about graph theory.
By the paper's author, the density of a graph seems like
(density) = (the number of edges) / (the number of nodes)
The authors followed E. Lawler (1976), Combinatorial Optimization: Networks and Matroids.
And they recommeded to see chapter 4 of that book.
I can't find about the density at the book.
So I searched google, maybe people say the density of a graph is
(density) = (the number of edges) / (the number of possible edges)
Those two definitions are different.
I would like to make it sure.
Thank you for your help in advance.
$\endgroup$ 23 Answers
$\begingroup$This Wikipedia link on dense graphs might contain what you're looking for.
In particular, for undirected simple graphs, the graph density is defined as $$D = \frac{2|E|}{|V|(|V| - 1)}.$$
While for directed simple graphs, the graph density is defined as $$D = \frac{|E|}{|V|(|V| - 1)},$$ where $|E|$ is the number of edges and $|V|$ is the number of vertices in the graph.
Note that the maximum number of edges is $$\frac{|V|(|V| - 1)}{2}.$$
$\endgroup$ 4 $\begingroup$Yeah! It's right that graph density = no of edges/total no of possible edges.
In directed graph total no of possible edges is |v|*|v-1|,
In undirected graph total no of possible edges is |v|*|v-1|/2.for e.g. -> let's say there are 3 nodes.All possible edges in undirected graph is 1-2,2-3,1-3 where as in directed graph all edges are 1->2,2->1, 2->3,3->2,1->3,3->1.
For undirected simple graphs, the graph density is defined as D=2|E|/|V|(|V|−1). While for directed simple graphs, the graph density is defined as D=|E|/|V|(|V|−1)
$\endgroup$ $\begingroup$There are several definitions of graph density out there. As we shall see, "number of edges / number of vertices" is the one that arises in Chapter 4 of Lawler's book.
[Goldberg 1984] introduced the notion of a densest subgraph: the subgraph that maximizes this ratio. This number is called the maximum density or sometimes (half the) maximum average degree. (The problem has interesting connections to the pseudoarboricity and smallest maximum indegree orientations.)
Several authors (e.g. [Charikar 2000]) point to Chapter 4 for a polynomial-time algorithm to compute the maximum density, but it's hard to spot. [Kortsatz and Peleg 1993] narrow it down to pp. 125-127. There, the provisioning problem is described (which can be solved with flow techniques).
In this problem, we have sets of items. If a set is to be selected, all its items must be bought. Each set has a value to us, each item cost. The objective is to "maximize sum values - sum cost". We can now transform the densest subgraph problem into several provisioning problems (a Cook reduction): Each vertex is an item and each edge is a set of two items. Each edge has value 1, and each vertex has cost d (this is maybe counterintuitive as one would like to count the vertices analogously by setting the cost to 1).
Let us distinguish the integral feasible solutions into the ones where the objective is >= 0 and the ones where it is < 0. For the former, we have sum values - sum cost = selected edges - selected vertices * d >= 0, so d >= sel. edges / sel. vertices. For the latter, d < sel. edges / sel. vertices, so this solution corresponds to a subgraph of density greater than d.
By finding the smallest d such that there is an integral feasible solution with objective >= 0, we determine the maximum density. This can be done in a binary search.
$\endgroup$
