1

I am rather new to Python and NetworkX. I need to create a list similar to Edgelist=[(0,1),(0,3),(1,0),(1,2),(1,4),(2,1),(2,5)], which elements represent the starting and ending node of an edge (link) that is in turn part of a network.

Rather than setting them manually, I want Python to create the couples you see in the list by randomly selecting the integer values of (start,end) from an assigned range of values (namely, 0, 999), which represent the node IDs. Then, I want to make sure that every node ID is included at least once in the series of (start,end) values (this means that all my nodes will be connected to at least one other node).

I know I could use random.randint(0, 999) but I don't know how to "nest" it into the creation of a list (perhaps a for loop?). I wish I had some code to show you but this is my first attempt at working with NetworkX!

EDIT

To give you a visual idea of what I mean, here are two images. The first is a regular network (aka lattice), and the second is a random one. The edge list of the first was created manually in order to reproduce a chess table, while the second displays an edge list which is a (manually) shuffled counterpart of the first one. As you see, the nodes are kept in exactly the same locations. Hope this helps a bit more. Thanks! enter image description here enter image description here

Improve this question
8
  • 2
    Networkx has many algorithms for generating random networks. Using one of them is likely to be better than the approach you are describing, especially because there are many very different varieties of random graph that would have the property you've described.. Can you tell us a bit more about the properties you want for your network? Commented Oct 14, 2015 at 20:08
  • Thanks for asking Joel. I have already built a lattice (e.g., a regular network which length distribution is a constant value - all nodes are equidistant from each other). Now I want to build a random network out of the same set of nodes, by simply keeping the coordinates of each node and randomly selecting the pairs of nodes to be connected. I knew of the many algorithms but none of them seemed to suit my needs, up to my knowledge. Commented Oct 14, 2015 at 21:24
  • what degree distribution? Configuration Model seems the most likely option. nx.configuration_model([1]*1000) will get you what you've stated you need, but it may not have all the properties you want. Commented Oct 15, 2015 at 2:33
  • 1
    I think the challenge I'm having understanding your question is that it's not clear what output you would want. Let's say start = 0 end = 2. Can you give a sample full output for this? I'm interested in: How many "edges"? Is repetition of an edge allowed? Commented Oct 15, 2015 at 2:37
  • By the way, a common algorithm for interpolating between a lattice and a random graph is to start with a lattice and then select random pairs of edges (u,v) and (w,x). Then delete them and create new edges (u,x) and (w,v) (after checking that those edges don't exist already and u!=x, w!=v). Commented Oct 15, 2015 at 6:48

6 Answers 6

Reset to default
1

There is a similar answer but for a complete graph on - How to generate a fully connected subgraph from node list using python's networkx module

In your case, using zubinmehta's answer:

import networkx import itertools def complete_graph_from_list(L, create_using=None): G = networkx.empty_graph(len(L),create_using) if len(L)>1: if G.is_directed(): edges = itertools.permutations(L,2) else: edges = itertools.combinations(L,2) G.add_edges_from(edges) return G

You could build the graph as:

S = complete_graph_from_list(map(lambda x: str(x), range(0,1000))) print S.edges()
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

If you copy content from an other question/answer you must (by the license) properly attribute it by stating who is the author (with a link to his profile) and what's the original question/answer.
@Bakuriu - I will keep in mind to also write the author's name if i'm going into referrals. Thanks for pointing out
1

Here is a networkx command that will create a graph such that each node has exactly one edge:

import networkx as nx G = nx.configuration_model([1]*1000)

If you look into the guts of it, it does the following which answers your question - each node will appear in exactly one edge.

import random mylist = random.suffle(range(start,end)) edgelist = [] while mylist: edgelist.append((mylist.pop(),mylist.pop()))

You should guarantee that mylist has even length before going through the popping.

Improve this answer

11 Comments

Well, I should have made this clear too. What I am after is a network in which every node appears at least once in the edgelist. In my conceptual models, no disconnected nodes are allowed. So, saying that each node will appear in exactly one edge means, for me, that all my nodes have just one link (e.g., their degree is always 1, no matter where they are located). Building a network like this will produce no disconnected nodes, but will also constrain the number of links, and could somehow be seen as the output of a constrained randomness. Makes sense?
So my main question is - how many links do you want? Any algorithm that someone provides will enforce that the number of links comes from some distribution. You should put some thought into how many links you actually want, and then it's much easier to create an algorithm to provide that. Right now it's not clear if you want the bare minimum (what I've provided) or the maximum ( nx.complete_graph(1000) ) or somewhere in between.
Good point Joel. I refrained from adding all these details in the original question to avoid publishing a "bible". The random network features random connections, hence the number of links each node has must be random (from 0 to x), and so are the nodes to which it is connected. The answer is therefore somewhere in between, but according to a random process.
So an obvious network to think about is the small-worlds network. From your lattice, use nx.double_edge_swap link to swap edges randomly. As you do this more and more, you'll get towards a completely random network with the same degrees. This lets you interpolate between a lattice and the random network. Alternately, go straight to the random network with nx.configuration_model (but read the documentation carefully since it can have self-edges or repeated edges).
If you want to be sure your final network is connected (rather than just every node has an edge), then look at nx.connected_double_edge_swap.
|
1

Python has inbuilt library called itertools. Sample as below as how you achieve what you mentioned:

import itertools list = [3, 4, 6, 7] sublist_length = 2 comb = itertools.combinations(list, sublist_length)

This will return comb as an iterator.

You can do comb.next() to get next element in the iterator or iterate over a for loop to get all results as you wanted as below.

for item in comb: print item

which should output:

(3, 4), (3, 6), (3, 7), (4, 6), (4, 7), (6, 7),

I hope this will solve your problem.

Improve this answer

Comments

0

For the list creation you can do something like:

import random max = 999 min = 0 original_values = range(min, max) # could be arbitrary list n_edges = # some number.. my_edge_list = [(random.choice(original_values), random.choice(original_values)) for _ in range(n_edges)]

To assert you have all values in there you can do the following

vals = set([v for tup in my_edge_list for v in tup]) assert all([v in vals for v in original_values])

The assert will make sure you have the proper representation in your edges. As far as doing your best to make sure you don't hit that assert you can do a couple of things.

  1. Sample without replacement from your list of integers until they are all gone to create a "base network" and then randomly add on more to your hearts desire
  2. Make n_edges sufficiently high that it's very likely your condition will be met. If it's not try again...

Really depends on what you're going to use the network for and what kind of structure you want it to have

EDIT: I have updated my response to be more robust to an arbitrary list of values rather than requiring a sequential list

Improve this answer

3 Comments

Because there is no need for an assert. It basically means the algorithm is broken.
I disagree with that...especially because option 1 ensures that that won't happen. The OP did not specify how they wanted the network generation to occur, if they wanted it one attempt, if it needed to be a complete graph, etc. The only stipulation was that every possible number was part of at least one edge. Both proposed algorithms provide that
@haavee If I generate a random sequence of numbers, but do some steps to guarantee they have some property a priori, it's likely I'll be biasing my outcomes. To have an unbiased sample in these cases, I should generate the sequence and then test.
0 
random.seed(datetime.datetime.now()) from random import randint # ot generate 100 tuples with randints in range 0-99 li = [(randint(0,99),randint(0,99)) for i in range(100)] print(li) [(80, 55), (3, 10), (66, 65), (26, 23), (8, 72), (83, 25), (24, 99), (72, 9), (52, 76), (72, 68), (67, 25), (72, 18), (94, 62), (7, 62), (49, 94), (29, 89), (11, 38), (52, 51), (19, 32), (20, 85), (56, 61), (4, 40), (97, 58), (82, 2), (50, 82), (77, 5), (2, 9), (2, 46), (39, 4), (74, 40), (69, 15), (1, 77), (45, 58), (80, 59), (85, 80), (27, 80), (81, 4), (22, 33), (77, 60), (75, 87), (43, 36), (60, 34), (90, 54), (75, 3), (89, 84), (51, 93), (62, 64), (81, 50), (15, 60), (33, 97), (42, 62), (83, 26), (13, 33), (41, 87), (29, 63), (4, 32), (6, 14), (79, 73), (95, 4), (41, 16), (96, 64), (15, 28), (35, 13), (35, 82), (77, 16), (63, 27), (75, 37), (11, 52), (21, 35), (37, 96), (9, 86), (83, 11), (5, 42), (34, 32), (17, 8), (65, 55), (58, 19), (90, 40), (18, 75), (29, 14), (0, 11), (25, 68), (34, 52), (22, 8), (12, 53), (16, 49), (73, 54), (78, 80), (74, 60), (40, 68), (69, 20), (37, 38), (74, 60), (53, 90), (25, 48), (44, 52), (49, 27), (28, 35), (29, 94), (35, 60)]
Improve this answer

2 Comments

It's a start, but this doesn't guarantee that every ID is present.
Yes John, and this is a crucial point. My ultimate aim is to build a network which has 10000 nodes, and for my goal it would be pointless having even a few disconnected nodes. So I must find a way to check for complete connectedness. And, of course, no self-linking is allowed (the starting and ending point of each parenthesis in the list must NOT coincide). Thanks for highlighting this!
-1

Here is a solution that first generates a random population of nodes (pop1), then shuffles it (pop2) and combines those into a list of pairs.

Note: this method only yields vertices where each node is exactly once start and exactly once end, so maybe not what you're after. See below for another method

import random, copy random.seed() # defaults to time.time() ... # extract a number of samples - the number of nodes you want pop1 = random.sample(xrange(1000), 10) pop2 = copy.deepcopy( pop1 ) random.shuffle( pop2 ) # generate pairs from the same population - this guarantees your constraint pairs = zip( pop1, pop2 ) print pairs

Output:

[(17, 347), (812, 688), (347, 266), (731, 342), (342, 49), (904, 17), (49, 731), (50, 904), (688, 50), (266, 812)]

Here is another method

This allows for duplicate occurrences of the nodes. The idea is to draw start and end nodes from the same population:

import random random.seed() population = range(10) # any population would do # choose randomly from the population for both ends # so you can have duplicates pairs = [(random.choice(population), random.choice(population) for _ in xrange(100)] print pairs[:10]

Output:

[(1, 9), (7, 1), (8, 6), (4, 7), (6, 2), (7, 3), (0, 2), (1, 0), (8, 3), (8, 3)]
Improve this answer

7 Comments

There is a bug in your first approach. Try it with start=0, end = 1. You'll get (0,0) (1,1) half the time, which violates the constraint requested. More generally, a fraction for large values, you'll run into a node connected to itself in 1/e of the samples you generate.
Your second approach also as a bug. As you can see in your output, 5 did not appear, which violates the constraint the OP gave.
Well, my the first method does satisfy those constraints. OP did not mention if nodes should appear more than once - i.e. in different edges.
The OP mentioned that they should be connected to other nodes. I'd be shocked if a (1,1) edge meets the OP's requirements.
Well, one other thing missing in your problem description is how many edges you'd like. The nodes is one thing but if you look at the diagrams (thanks for those) there's 12 edges in the first and 17 (if I counted correctly ...) in the 2nd.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.