erdos.renyi.game edge density lower than specified

Usage
1

I am trying to generate random graphs of social network data using the erdos.renyi.game function. I have specified the requirements using:

random.graph ← erdos.renyi.game(25, 15, type=“gnm”)

If I understand the function correctly, 25 is the number of nodes, and 15 should be the density of edges. However, the density of my randomized graphs are approximately 0.05.
If I’m not mistaken the function should choose edges approximately close to 15?
Does anyone know how I can force the erdos.renyi function to use the given edge density?

2

For gnm, the second parameter, m, is the number of edges. For a graph with 25 vertices, there are 300 possible edges, not counting loops and multi-edges. 15 edges out of 300 gives a density of 0.05, so that seems to be correct. Are you sure you want a density of 15? Because that means 15 edges per possible edge, so quite a multi-edged multigraph. It seems like the function only goes up to a density of 1.

3

Thank you for the response. That makes a lot of sense.
Unfortunately, I believe I must use a density of 15 as that is my observed networks edge density. (I study a highly social Crow species with many association per node).
In order to accurately simulate my random graphs, I believe the densities must be approximately the same.

When I calculate

edge_density(my_network)
I get 15

Whereas, when I calculate the simulated graph densities

edge_density(Random_network)
I get 0.05

I’m unsure as to why the “Random_network” density is given as a proportion while the actual network isn’t. I will try to investigate the function further.

4

In the documentation (igraph R manual pages), it says
“The density of a graph is the ratio of the number of edges and the number of possible edges.”
and also
“Note that this function may return strange results for graph with multiple edges, density is ill-defined for graphs with multiple edges.”

So I think it should never get above 1. From your description it also seems like your graph shouldn’t have multiple edges between two vertices. Does it?

If it isn’t a proportion then it isn’t a density, and it would be just the number of edges.

1 Like
5

My graph only has 1 edge between any 2 vertices.

However, the network is very densely connected (some nodes have up to 22 edges) so it sounds like the multiple edges are affecting its ability to calculate the density correctly.

6

That really shouldn’t be a problem. When I test the function it also works fine for a full graph of 1000 nodes (so 999 edges per node):

> test_graph <- make_full_graph(1000)
> edge_density(test_graph)
[1] 1

And for some random example:

> test_graph <-   graph_from_literal( A--B, C--D, E--F, G--H, I, J, K )
> edge_density(test_graph)
[1] 0.07272727

I also get exactly what I would expect.

One way I can get the density above 1 is to have loops in the graph, but still call the function with loops=false. ( I tried this in C only)

Is it possible to post your data so I can try to reproduce it?

7

These two sentences together indicate that the graph is simple, in which case its density should never be above 1.Maybe you meant that the average degree of your network is 15 (instead of the density)?

8

I realized after looking through my data files that there were 2 nodes with multiple edges between them. This is definitely the driver of the strange density results.
I have begun working on converting these parallel edges to weights and then plan to run the erdos.renyi.game.
Thank you for your help @GroteGnoom !