I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper.
We are talking about generating an undirected graph in a slightly different way than what the Watts-Strogatz model does.
One of the very first steps of the algorithm is
instead of selecting links to connect most immediate $\langle k \rangle / 2$ neighbors to form a regular lattice, our model selects a number $k$ of links at random from a local neighborhood $N_{d_0}$ with the distance threshold of $d_0$, where $k$ comes from a geometric distribution. The local neighborhood is defined as the group of close-by nodes with mutual node number difference less than the threshold $d_0$, that is $N^{(i)}_{d_0} = \{j; |j-i| < d_0\}$, for node $i$. It is worth noting that our model adopts a geometric distribution with the expectation $\langle k \rangle$ of for the initial node degree settings (i.e, for the link selection).
In other words, each node with index $i$ should have a (possibly different) random degree $k$, obtained by linking it with nodes with an index-distance $d_0$.
First of all, I need to choose the parameter $p$ to generate the geometric distribution. If the average is $\langle k \rangle$, I choose $p = 1/\langle k \rangle$.
However, picking $n$ node degrees from a geometric distribution may not result in a feasible graph of $n$ nodes.
Moreover, Since this is an undirected graph we are talking about, going through each node and creating a random number $k$ of links will most likely not produce the desire average degree. E.g. during the ith iteration, the node i may already have more than $k$ links, created by the previous iterations of nodes randomly linking to it.
I tried to implement my own algorithm to distribute the node degrees as close as possible to the distribution outcome. Pseudocode
k_values = n values from the geometric distribution with p = 1/<k>
for each node in [0, n)
if degree(node) < k_values[node]
for each neighbor closer than d_0
if degree(neighbor) < k_values[neighbor]
if not link_exist(node, neighbor)
create_link(node, neighbor)
The problem is, this approach tends to consistently result in nodes having lower degrees than the output of the geometric distribution.
I know there are ways to generate an undirected graph with a given degree distribution. The biggest problem here seems to be the additional constraint on the potential neighborhood of each node (i.e. nodes within index-distance $d_0$). Any ideas on how to solve that?
I would be happy getting a graph that is within a certain threshold from the outcome of the geometric distribution, and still quite close to the intended average degree $\langle k \rangle$.