Random non-induced subgraph

edit

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.