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.

  • 2
    en.wikipedia.org/wiki/Dense_graph - it looks reliable. The paper from 1976 is apparently outdated – HEKTO Nov 12 '15 at 21:28
  • Maybe the density of a graph and induced subgraph are different. According to Reid Andersen and Kumar Chellapilla (2009), Finding Dense Subgraphs with Size Bounds, the density of induced graph is that (density) = (the number of edges of induced subgraph) / (the number of nods of induced subgraph). – Woonghee Lee Nov 17 '15 at 0:03
up vote 3 down vote accepted

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}.$$

  • 1
    Thank you for comment. At the second definition what I mentioned, (the number of possible edges) implies |V|(|V|-1)/2. I expect there is another definition of the density of a graph. – Woonghee Lee Nov 12 '15 at 22:27
  • As I commented my question myself, there are different definitions of densities for graph and subgraph. Thank you again. – Woonghee Lee Nov 17 '15 at 0:05

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)

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.