# Random non-induced subgraph

Given a graph G then G.random_subgraph(.5) returns a random subgraph of G (each vertex is selected independently with probability .5).

However, this will return an induced subgraph.

Is there a command that returns a not necessarily induced subgraph?

edit retag close merge delete

Not sure what you mean. Do you mean that also edges in G should be included or not with some probability?

( 2022-09-28 18:51:30 +0100 )edit

The algorithm random_subgraph(p) will select each vertex of G independently with probability p but then include ALL the edges between those vertices provided they are edges in G. The idea is that instead of including all possible edges it subsequently selects each with probability q.

( 2022-09-29 01:52:10 +0100 )edit

Do you want to achieve equiprobability of each subgraph ? If yes, first selecting the vertices and then the eges might not work.

( 2022-09-29 11:47:53 +0100 )edit

Sort by ยป oldest newest most voted

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.

more