1 | initial version |

I don't think anything like this exists in Sage now, but the code for `random_subgraph`

is pretty simple:

```
def random_subgraph(self, p, inplace=False):
"""
Return a random subgraph containing each vertex with probability ``p``.
INPUT:
- ``p`` -- the probability of choosing a vertex
- ``inplace`` -- boolean (default: ``False``); using ``inplace=True``
will simply delete the extra vertices and edges from the current
graph. This will modify the graph.
EXAMPLES::
sage: P = graphs.PetersenGraph()
sage: P.random_subgraph(.25)
Subgraph of (Petersen graph): Graph on ... vert...
"""
p = float(p)
if p < 0 or p > 1:
raise ValueError("a probability must be in range [0..1]")
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)
```

The heart of it is:

```
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)
```

Something that doesn't quite work:

```
sage: g = graphs.PetersenGraph()
sage: p = 0.3
sage: V = [v for v in g if random()<p]
sage: E =
sage: h = g.subgraph(vertices=V, edges=E)
```

The problem is that the definition of `E`

ignores which vertices are in `V`

. You could instead construct your subgraph in stages:

```
sage: h1 = g.random_subgraph(p)
sage: E = [e for e in h1.edge_iterator() if random()<p] # choose edges randomly from h1
sage: h2 = h1.subgraph(edges=E)
```

Now `h2`

will have the randomly chosen vertices that make up `h1`

, and it will have edges chosen from `h1`

randomly.

2 | No.2 Revision |

I don't think anything like this exists in Sage now, but the code for `random_subgraph`

is pretty simple:

```
def random_subgraph(self, p, inplace=False):
"""
Return a random subgraph containing each vertex with probability ``p``.
INPUT:
- ``p`` -- the probability of choosing a vertex
- ``inplace`` -- boolean (default: ``False``); using ``inplace=True``
will simply delete the extra vertices and edges from the current
graph. This will modify the graph.
EXAMPLES::
sage: P = graphs.PetersenGraph()
sage: P.random_subgraph(.25)
Subgraph of (Petersen graph): Graph on ... vert...
"""
p = float(p)
if p < 0 or p > 1:
raise ValueError("a probability must be in range [0..1]")
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)
```

The heart of it is:

```
vertices = [v for v in self if random() < p]
return self.subgraph(vertices=vertices, inplace=inplace)
```

Something that doesn't quite work:

```
sage: g = graphs.PetersenGraph()
sage: p = 0.3
sage: V = [v for v in g if random()<p]
sage: E =
```~~ ~~[e for e in g.edge_iterator() if random()<p]
sage: h = g.subgraph(vertices=V, edges=E)

The problem is that the definition of `E`

ignores which vertices are in `V`

. You could instead construct your subgraph in stages:

```
sage: h1 = g.random_subgraph(p)
sage: E = [e for e in h1.edge_iterator() if random()<p] # choose edges randomly from h1
sage: h2 = h1.subgraph(edges=E)
```

Now `h2`

will have the randomly chosen vertices that make up `h1`

, and it will have edges chosen from `h1`

randomly.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.