Graph Density of Undirected Network

Feb 12, 2013 at 3:15 PM
When calculating Graph Density for an undirected network, I get a value that is 2x what I believe it should be, and I'm trying to figure out if this is a bug, or a misunderstanding on my part.

I understand Graph Density to be Unique Edges / Total possible edges

In my example, I have 12 unique edges, and 11 vertices. Total possible edges should be 11 * 10, or 110.

110 / 12 = 0.109091, but I get 0.2181818

I get what I believe to be the correct Graph Density when I set the graph to Directed, however, when calculating Density on a undirected graph I still get 2x the value. So, what am I misunderstanding?

Thanks!!
Coordinator
Feb 12, 2013 at 7:56 PM
Edited Feb 15, 2013 at 5:07 PM
Curtis:

I'm not sure I understand the results you are reporting (2x what value?), and I think your equation got inverted. But let me tell you what should be happening.

The graph density for an undirected graph is defined at http://en.wikipedia.org/wiki/Dense_graph . For a directed graph, you have to divide the equation by two to account for the doubled number of possible edges.

If you set NodeXL, Graph, Type in the Excel ribbon to Undirected and use NodeXL, Analysis, Graph Metrics to calculate what we call Overall Metrics, and you have 11 vertices and 12 edges, then you should get a graph density of 0.109091. [These numbers are wrong; see my later post.] If you then set the Type to Directed and you calculate Overall Metrics again, you should get a graph density of 0.054545.

What are the actual results you are getting in these two cases? And are you recalculating Overall Metrics after you switch the Type to Directed? You have to do that; the overall metrics will not get recalculated automatically.

-- Tony
Feb 14, 2013 at 2:09 PM
Edited Feb 14, 2013 at 2:24 PM
Hey Tony,

Yeah, I inversed my equation when typing too fast. I meant to say 12/110.

Here are the results I get when calculating Overall Metrics for a network with 11 vertices and 12 edges;

Undirected - Graph Density 0.218181818
Directed - Graph Density 0.109090909

Here is a link to a sample file I uploaded to the Graph Gallary to maybe help better explain what I'm talking about. https://www.nodexlgraphgallery.org/Pages/Graph.aspx?graphID=2827

Thanks!
Coordinator
Feb 14, 2013 at 5:09 PM
Edited Feb 15, 2013 at 5:06 PM
Curtis:

You inverted your equation and I did the math wrong in my previous post.

For an undirected graph, the graph density is 2E/(V * (V-1)). In your case, this is (2 * 12)/(11 * 10) = 0.218182.

For a directed graph this has to be divided by 2, which yields 0.109091.

In both cases, NodeXL gives the correct results.

-- Tony