6
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

You can use the configuration model for this. Create a "stub" array where each of the $n$ vertices appears in the array $k_i \sim \text{Geom}(p)$ times. Shuffle the array and then treat each adjacent pair in the array as an edge in the graph. Here's some python code to illustrate.

from numpy.random.mtrand import geometric
from random import shuffle
from _collections import defaultdict

if __name__ == '__main__':
    # Number of vertices
    n = 1000

    # Geometric distribution probability parameter
    p = 0.5

    stubs = []
    for i in xrange(0, n):
        # Sample the degree from the geometric distribution
        degree = geometric(p) 
        # Insert into the stubs array the current vertex label degree times
        stubs += [i] * degree

    # Shuffle the values
    shuffle(stubs)

    # Build the graph
    G = {}
    for i in xrange(0, n):
        G[i] = []

    for i in xrange(1, len(stubs), 2):
        G[stubs[i]].append(stubs[i-1])
        G[stubs[i-1]].append(stubs[i])

    # Recover the degree distribution
    degrees = { i : len(neighbors) for i, neighbors in G.items() }

    dist = defaultdict(int)
    for (vertex, degree) in degrees.items():
        dist[degree] += 1

    print("Degree, empirical, theoretical")
    for (degree, freq) in dist.items():
        print("%d %f %f" % (degree, freq / float(n),  pow((1 - p), degree - 1) * p ))

Sample output:

Degree, empirical, theoretical
1 0.496000 0.500000
2 0.254000 0.250000
3 0.128000 0.125000
4 0.071000 0.062500
5 0.023000 0.031250
6 0.018000 0.015625
7 0.005000 0.007812
8 0.003000 0.003906
9 0.002000 0.001953

For more detailed description of the the configuration model, see Section 13.2 p. 435 of Networks by Newman.

$\endgroup$
  • 1
    $\begingroup$ Answers that consist mostly of programming code is rarely suited for this site. We value ideas, concepts, proofs of correctness and (if needed) pseudocode more. $\endgroup$ – Raphael Jan 1 '16 at 19:13
  • $\begingroup$ What if it is not geometric distribution, some distribution which is not in python libraries. How to get the degree sequence? Is it a new question for a new post? @GEL $\endgroup$ – Nick Dong Jun 25 '16 at 8:55
  • $\begingroup$ @NickDong The configuration model is valid for an arbitrary distribution on the natural numbers. If you can sample the degree from the distribution (using a library, your own algorithm, or from data, etc), the above code can be used by substituting "geometric(p)" with a call to your sampling function. $\endgroup$ – GEL Jun 27 '16 at 0:57

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.