choosing a random edge?
Joel
already. I'd like to choose a random edge from a network, uniformly
from all edges.
The obvious ways to do that would be to make a list of all edges and
choose one, or to choose each node proportional to its degree and then
choose a random edge of that node. But it seems there may be more
efficient ways that someone smarter than me has already implemented.
Does this exist yet?
thanks,
Joel
alex
> Before I start recreating the wheel, I thought I'd see if this exists
> already. I'd like to choose a random edge from a network, uniformly
> from all edges.
> or to choose each node proportional to its degree and then
> choose a random edge of that node.
double_edge_swap looks like it samples nodes proportional to degree:
http://networkx.lanl.gov/svn/networkx/trunk/networkx/generators/degree_seq.py
Joel
Thanks,
Joel
Aric Hagberg
A while back I sent this to someone asking about choosing k random
edges uniformly from a large graph. It might be more useful depending on
exactly what you are doing and the number of edges in the graph.
Aric
import networkx
from random import random, shuffle
def random_items(iterable, k=1):
# Raymond Hettinger's recipe
# http://code.activestate.com/recipes/426332/
result = [None] * k
for i, item in enumerate(iterable):
if i < k:
result[i] = item
else:
j = int(random() * (i+1))
if j < k:
result[j] = item
shuffle(result)
return result
def all_edges_iter(G,k=1,data=False):
if data:
for n,nbrs in G.adj.iteritems():
for nbr,data in nbrs.iteritems():
yield (n,nbr,data)
else:
for n,nbrs in G.adj.iteritems():
for nbr in nbrs:
yield (n,nbr)
def random_edges(G,k=1,data=False):
"""Choose k random edges uniformly from G.
For undirected graphs this might produce duplicates
since each edge is considered twice, once for each
representation u-v and v-u. Duplicates can be removed by
using set(random_edges()).
"""
return random_items(all_edges_iter(G,data=data),k=k)
if __name__ == "__main__":
import networkx
G=networkx.star_graph(100)
print random_edges(G,6,data=True)
Joel
Anyways, if anyone else is doing this and tries Aric's code, I think there is a small issue with the all_edges_iter (at least when I'm using it on a multigraph). When networkx lists its edges, it has a particular order to it. The snippet of code Aric gave will not necessarily give the order that networkx produces. So if you ask it whether an edge is part of G.edges(), about half the time it says no. If the nodes are named by numbers, the snippet below works. I'm not sure how things behave if the nodes have different names.
def all_edges_iter(G,k=1,data=False):
if data:
for n,nbrs in G.adj.iteritems():
for nbr,data in nbrs.iteritems():
yield (n,nbr,data)
else:
yield (nbr,n,data)
else:
for n,nbrs in G.adj.iteritems():
for nbr in nbrs:
yield (n,nbr)
else:
yield (nbr,n)