Functions producing small-world / scale free / ER networks

Hi all,

I would like to know if somebody has already coded functions for creating
some small-world / scale free / ER networks with the following parameters
(similar to networkx):

small-world -> n : The number of nodes , k : Each node is connected to k
nearest neighbors in ring topology , p: The probability of rewiring each
edge

scale-free -> n : Number of nodes, m : Number of edges to attach from a new
node to existing nodes

ER -> n : The number of nodes , p : Probability for edge creation.

Cheers!

Mehdi

small-world -> n : The number of nodes , k : Each node is connected to
k nearest neighbors in ring topology , p: The probability of rewiring
each edge

There no function for this yet. It is in my TODO list. But you can
create this easily by creating a 1D lattice (a ring) with the lattice()
function, and than randomly rewire a portion of the edges.

scale-free -> n : Number of nodes, m : Number of edges to attach from

a new

node to existing nodes

This is implemented in the price_network() function.

ER -> n : The number of nodes , p : Probability for edge creation.

This is also in my TODO list, although it is very easy to
implement. Note that, for most purposes, this is equivalent to
generating a random graph with random_graph() and using a poisson degree
distribution with the appropriate average.

Cheers,
Tiago

Hi Tiago,

thanks for the feedback.

I have followed your advice for the scale-free and er network and there are
no pb for these.
The watts-strogatz network version I have implemented works, but is very
very slow.
See code:

def watts_strogatz_network(n,k,p):
    g=lattice([n])
    # make a ring
    g.add_edge(g.vertex(0), g.vertex(n-1))
    # add edges to k neighbours of each vertex in the ring
    # k-1 neighbours if k is odd
    if ((k%2!=0) and k>1):
        k-=1
    if k>2:
        for v in range(n):
            l_n=get_n_levels_neighbours(n,v,k)
            for v_n in l_n:
                if not g.edge(v_n,v):
                    g.add_edge(g.vertex(v), g.vertex(v_n))
    # replace each edge u-v by an edge u-w with probability p
    for u in range(n):
        for v in g.vertex(u).all_neighbours():
            if (random()<=p):
                l1=range(n)
                l2=get_n_levels_neighbours(n,u,k)
                l=[i for i in l1 if i not in l2]
                l.remove(u)
                #print l
                w=rd.choice(l)
                while w==u or g.edge(u,w):
                    w=rd.choice(l)
                g.remove_edge(g.edge(u, v))
                g.add_edge(g.vertex(u), g.vertex(w))
    return g

def get_n_levels_neighbours(maxn,n,k):
    l=range(n-(k/2),n)
    l+=range(n+1,n+(k/2)+1)
    for i in range(len(l)):
        if (l[i]<0):
            l[i]=((l[i])%(maxn-1))+1
        if(l[i]>(maxn-1)):
            l[i]=l[i]%maxn
    return l

I have noticed that the boost library has a small-world graph generator
see:
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/small_world_generator.html
Would there be any way to call that inside graph-tool as a faster
alternative?

Cheers!

Mehdi

attachment.html (4.15 KB)

Hi Mendhi,

Hi Tiago,

thanks for the feedback.

I have followed your advice for the scale-free and er network and
there are no pb for these. The watts-strogatz network version I have
implemented works, but is very very slow.
[...]

Yes, indeed. Doing it in C++ would be much faster.

But there are ways to improve your code:

    - Do not call the range() function, since it is O(N). In loops, you
      should call xrange() instead.
    - To sample a random vertex, you can do something like:
      g.vertex(numpy.random.randint(g.num_vertices()))
      This is much faster than using choice().

I have noticed that the boost library has a small-world graph
generator see:
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/small_world_generator.html
Would there be any way to call that inside graph-tool as a faster
alternative?

Yes, I will implement this as soon as I have some time.

Cheers,
Tiago