[graph-tool] Functions producing small-world / scale free / ER networks

Mehdi Khoury mehdi.khoury at gmail.com
Sat Aug 6 04:17:47 CEST 2011

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):
    # 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):
    if k>2:
        for v in range(n):
            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):
                l=[i for i in l1 if i not in l2]
                #print l
                while w==u or g.edge(u,w):
                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):
    for i in range(len(l)):
        if (l[i]<0):
    return l

I have noticed that the boost library has a small-world graph generator
Would there be any way to call that inside graph-tool as a faster



On Thu, Aug 4, 2011 at 10:07 AM, Tiago de Paula Peixoto <tiago at skewed.de>wrote:

> On 08/02/2011 03:03 PM, mehdi wrote:
> > 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
> --
> Tiago de Paula Peixoto <tiago at skewed.de>
> _______________________________________________
> graph-tool mailing list
> graph-tool at skewed.de
> http://lists.skewed.de/mailman/listinfo/graph-tool
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20110806/62244b94/attachment.htm>

More information about the graph-tool mailing list