0
$\begingroup$

Random graphs are popular topic in math and statistics.

Most of the existing models generate random graphs based on probability distribution on edges, e.g. each edge is sample from a Bernoulli distribution with parameter $p$ (and number of the vertices is fixed, hence the expected degree for each would be $p(|V|-1)$).

I was wondering if there is a way to generate a random graph which would yield in a given expected degree.

$\endgroup$
1
  • $\begingroup$ Are you looking for the Configuration Model? Configuration model is a RG model where the degree sequence are fixed before hand $\endgroup$
    – Sayan
    Oct 13, 2016 at 5:53

2 Answers 2

1
$\begingroup$

Configuration Model: Suppose we wish to construct a graph with $n$ vertices $\{1,2,\ldots,n\}$ having degree sequence $\{d_1,d_2,\ldots,d_n\}$. It can be done in the following manner:

Let $\ell_n=\sum\limits_{i=1}^n d_i$ (must be even). Then consider a graph with $\ell_n$ vertices with $\ell_n$ many half edges hanging from each vertex (one half edge for each vertex). Number vertices as $\{1,2,\ldots,\ell_n\}$. Take the half edge corresponding to 1st vertex and choose another vertex uniformly from the remaining vertices. Join the first vertex half edge with the chosen vertex half edge to get an edge and mark both the vertex. Then consider the next unmarked vertex in the list of vertices. Again choose the another vertex from the remaining list of unmarked vertices. Join the half edges of the two vertices and mark them. Continuing in this fashion we would obtain a graph with $\ell_n$ vertices.

Note that the appearance of each graph as a realization in this case is uniform with probability $$\frac1{(\ell_n-1)(\ell_n-3)\cdots 3\cdot 1}=\frac1{(\ell_n-1)!!}$$ Now coalesce the first $d_1$ vertices into 1 vertex. Coalesce the next $d_2$ vertices into another vertex and so on. Thus we would obtain our required graph. Note that this graph may have multiedges and self loops.

This model is known as the configuration model.

A good reference would be Remco's book on Random Graphs and Complex Networks Volume 1

$\endgroup$
0
$\begingroup$

Well, if you want to have vertices with expected degree $q$, since the expected number of edges adjacent to a vertex in the "usual" way to randomize graph is $p(|V|-1)$, you can fix that quantity equal to $q$ and solve for $p$ i.e. get: $$ p=\frac{q}{|V|-1}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.