Getting graph density on a graph with multiple edges

Usage
1

Hello everyone!

I am working on a swine movement network analysis. I am analyzing the inter-city movement of pigs in my country.

In the inter-city movement of pigs, I have 685 cities and 37138 shipments (name of network is Swine_Graph). Each city can have 1 or more pig shipment creating multiple edges in each node.

When I ran my graph density in R, I wrote the following:
graph.density(SwinePH_Graph)

It gave me a value of 0.079 (does this mean my graph density is 7.9%)

However, when I looked into the igraph R manual, I saw this statement in graph.density → “Note that this function may return strange results for graph with multiple edges, density is ill-defined for graphs with multiple edges”

If this is the case, how should I properly compute my graph density if I have multiple edges in one node?

Appreciate your response on this

2

It seems you are using a rather outdated version. Why don’t you use the latest? The statement in the documentation is much clearer:

The first questions to answer:

  • What do you mean when you say “graph density”? Can you explain the concept?
  • Why are you trying to compute it?

While this may not sound like a response, in fact it is. I am trying to lead you onto the right path.

3

Hello szhorvat,

I would like to know the density of my network. I am working to compute the density of pig shipments. From my research in several articles, I saw that the formula for a directed network is

total number of edges/(total number of nodes*(total number of nodes - 1))

In my 1st network, my data seems to have a value of below 1:
37128/(685*684) = 0.079

However, in my second network where there are only few nodes (66 provinces), there seems to be a very big value:

31622/(66*65) = 7.37

My data involves animal shipments (edges) in different provinces (nodes). It is very possible that there are multiple shipments in one province. There was a suggestion to me to use the following formula:

D= total number of edges / (total number of nodes*(total number of nodes -1) * multiplicity factor

The multiplicity factor represents the number of shipments between the same pair of nodes.

Does this seem to be a logical way of computing for density given the nature of my network?

Appreciate your help on this

4

It seems to me that you are approaching this a bit backwards: “I want to calculate graph density, what is the formula/algorithm for it?”

Why do you want to calculate the graph density? Graph density is simply the fraction of connections that are present between the given vertices, relative to how many there could be at most. In multigraphs, there is no upper bound on the number of connections, so the concept of graph density does not make sense.