
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!!


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!


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 * (V1)). 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



FYI, I am having this problem too. I imported a Facebook network, and then set the type as undirected. There are 121 vertices and 1724 edges. The density should be 0.237 and it is giving 0.119

