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 -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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@skewed.de>
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.ht... Would there be any way to call that inside graph-tool as a faster alternative? Cheers! Mehdi On Thu, Aug 4, 2011 at 10:07 AM, Tiago de Paula Peixoto <tiago@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@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
Hi Mendhi, On 08/06/2011 04:17 AM, Mehdi Khoury wrote:
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.ht... 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 -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
mehdi -
Mehdi Khoury
-
Tiago de Paula Peixoto