1

I have an undirected graph with the following attributes and I need to do some analysis on a fully random graph and a regular graph with the same attributes.

Attributes:

Number of Nodes = 37764
Number of Edges = 518151
Average Degree = 27.44153161741341

To study the properties of random graphs, I create them using networkx.gnm_random_graph(37764,518151) and performed my analysis. But I am very much confused about how to generate regular graphs using the same attributes.

I found two methods to generate regular graphs here using networkx.random_regular_graph(k, n) (documentation) and igraph.Graph().K_Regular(n, k) (documentation), but noticed that they need the degree k to be an integer value.

But in my original graph, the value is a float value 27.44153161741341. Now I cannot understand how to create a regular graph (or many graphs to give the same above-mentioned attributes when averaged) for my analysis.

In rephrasing my question: How to deal with the decimal part of the average degree in my case?

Language/library no bound for the solution.

willcrack
  • 1,794
  • 11
  • 20
thepunitsingh
  • 713
  • 1
  • 12
  • 30

1 Answers1

0

A regular graph is a graph where each vertex has the same degree.

It's not possible to have a regular graph with an average decimal degree because all nodes in the graph would need to have a decimal degree.

The best you can do is:

>>> G = nx.random_regular_graph(27, 37764)
>>> len(G.edges())
509814

# OR

>>> G = nx.random_regular_graph(28, 37764)
>>> len(G.edges())
528696

I guess you could try something like:

def perfect_avg(v_27, v_28):
    return v_27 * (1-0.44153161741341) + v_28 * (0.44153161741341)

where v_27 is the value for the graph with degree = 27
(and v_28 the value for the graph with degree = 28)

For example:

>>> nr_edges27 = len(G27.edges())
>>> nr_edges28 = len(G28.edges())
>>> perfect_avg(nr_edges27, nr_edges28)
518151.0
willcrack
  • 1,794
  • 11
  • 20
  • Yes, I've thought of having either 27 or 28 degrees, but wouldn't be the properties of these graphs differ by a large margin from the expected graph with original average degree? – thepunitsingh Dec 16 '20 at 11:34
  • the number of edges changes quite significantly at least. I don't know about shortest path lenght, cluster coeff, degree dist... – willcrack Dec 16 '20 at 11:41
  • All other properties depend on the graph structure. I'm majorly worried about the number of edges as it will affect all properties. Please advise on this solution - I approximate the decimal part to 4 places. That becomes `0.4415 = 883/2000`, so I make 2000 graphs in which I make 883 graphs with 28 degrees and 2000-883=1117 graphs with 27 degrees? So, our average degree will be approximately the same over 2000 graphs. – thepunitsingh Dec 16 '20 at 11:51
  • Yess in that case the average degree of the 2000 graphs would be 27.4415 – willcrack Dec 16 '20 at 11:55
  • Thanks, I'll try and check the results, and if required add the improvements to the answer. – thepunitsingh Dec 16 '20 at 11:56
  • Np, the thing is.. Will the rest of the values simply average to the "correct" value? Won´t It take a ridiculous amount of time to calculate some of the properties to 2000 graphs? – willcrack Dec 16 '20 at 11:59
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/226047/discussion-between-thepunitsingh-and-willcrack). – thepunitsingh Dec 16 '20 at 13:44
  • I´ve edited the answer, see if it makes sense ;) – willcrack Dec 16 '20 at 17:03
  • What did you think of my final answer? Anything missing? – willcrack Dec 24 '20 at 00:26
  • 1
    I have discussed with few people in the field and they have told me that since we have to study the properties of the graph, the difference of 1 degree won't matter. So, we can take the round-off degree, which in this case is 27. – thepunitsingh Dec 24 '20 at 05:56
  • I guess that makes sense, I mean you want to study the regular graph, not the average of two graphs.. – willcrack Dec 24 '20 at 10:35
  • It seems like you have found the solution! Consider marking the question as answered by posting your own answer or by accepting mine. – willcrack Dec 24 '20 at 10:39