ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 29 Sep 2022 11:47:53 +0200Random non-induced subgraphhttps://ask.sagemath.org/question/64210/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?Tue, 27 Sep 2022 22:25:43 +0200https://ask.sagemath.org/question/64210/random-non-induced-subgraph/Comment by tmonteil for <p>Given a graph G then G.random_subgraph(.5) returns a random subgraph of G (each vertex is selected independently with probability .5).</p>
<p>However, this will return an induced subgraph.</p>
<p>Is there a command that returns a not necessarily induced subgraph?</p>
https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64245#post-id-64245Do you want to achieve equiprobability of each subgraph ? If yes, first selecting the vertices and then the eges might not work.Thu, 29 Sep 2022 11:47:53 +0200https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64245#post-id-64245Comment by Magus for <p>Given a graph G then G.random_subgraph(.5) returns a random subgraph of G (each vertex is selected independently with probability .5).</p>
<p>However, this will return an induced subgraph.</p>
<p>Is there a command that returns a not necessarily induced subgraph?</p>
https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64236#post-id-64236The 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.Thu, 29 Sep 2022 01:52:10 +0200https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64236#post-id-64236Comment by John Palmieri for <p>Given a graph G then G.random_subgraph(.5) returns a random subgraph of G (each vertex is selected independently with probability .5).</p>
<p>However, this will return an induced subgraph.</p>
<p>Is there a command that returns a not necessarily induced subgraph?</p>
https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64229#post-id-64229Not sure what you mean. Do you mean that also edges in G should be included or not with some probability?Wed, 28 Sep 2022 18:51:30 +0200https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?comment=64229#post-id-64229Answer by John Palmieri for <p>Given a graph G then G.random_subgraph(.5) returns a random subgraph of G (each vertex is selected independently with probability .5).</p>
<p>However, this will return an induced subgraph.</p>
<p>Is there a command that returns a not necessarily induced subgraph?</p>
https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?answer=64241#post-id-64241I 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.Thu, 29 Sep 2022 05:02:48 +0200https://ask.sagemath.org/question/64210/random-non-induced-subgraph/?answer=64241#post-id-64241