0
$\begingroup$

I need a way of taking some graph G and obtaining a spanning subset of G where each edge $e_i$ has some probability $P_i$ of being in the subgraph. So the size of the edge sets of each random subgraph would also be random, up to the given probabilities. I've looked at existing Mathematica commands, and most random sampling functions would seem to require that I specify the number of edges that will be in my subgraph. And this is not what I'm after.

I'm aware of the Subgraph function, but this doesn't seem to get me the desired results either, since it asks the user to input the edges/vertices so that it can construct the explicit subgraph.

What do y'all recommend?

$\endgroup$
1
  • 2
    $\begingroup$ Could you add an example? $\endgroup$
    – MarcoB
    Mar 21, 2022 at 20:16

1 Answer 1

1
$\begingroup$

If you want to retain each edge in a graph g with probability p, you can use:

sample[list_, p_] := 
 Pick[list, UnitStep[p - RandomReal[1, Length[list]]], 1]

Graph[VertexList[g], sample[EdgeList[g], p]]

If you also want to retain the various edge/vertex properties the graph may have, you can use IGTakeSubgraph from the IGraph/M package.

Of course this may not produce a connected graph, but you did not ask for that. The IGRandomSpanningTree functions from IGraph/M may be of interest: it samples the spanning trees of a graph uniformly. Note that just adding more graph edges to a spanning tree randomly will not achieve the uniform sampling of connected spanning subgraphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.