Question

Describe, in detail, the procedure for generating a degree preserving network. Provide an example of a small network ( n = 5) and generate a new network that preserves the degree (this can be done by hand, in matlab, in excel, etc.). Show that you have preserved the original network’s degree distribution.

Answer 1

There are different manners of generating an ensemble of networks with preserved degree distribution. Here, we will discuss about configuration model which is widely used in many domains.

Configuration model consist of constructing a network with a previously specified degree distribution. st of constructing a network with a previously specified degree distribution.

Starting from an empty set of N vertices, each vertex is assigned a degree k(v) that can be visually regarded as free stubs.

Subsequently, pairs of stubs are randomly chosen and connected. The configuration model has several limitations and it is often difficult (if not impossible) to generate networks without introducing self-loops or multiple links.

Alternatively, random networks with given degree sequence can be obtained by iteratively swapping randomly selected edges.

This is usually the method of choice for significance testing of graph measures, basically, because it works without the problems of the configuration model.

Above figure shows the generation of random networks with preserved degree distribution.

In fig (a), each vertex is assigned a fixed number of stubs which are then joined at random.

In fig (b), link switching method takes place. Here, two edges are selected at random and switched, provided that the new edges do not already exist neither become self loops.

Let me know if you have any doubts or if you need anything to change. 

If you are satisfied with the solution, please leave a +ve feedback : ) Let me know for any help with any other questions.

Thank You!
===========================================================================