I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the subgraph has only nodes with degree $k \leq k_{max}$.

In other words, I want to create a new random graph with the same number of vertices, but with a random set of the original edges from $G$ removed such that the maximum degree of the new graph is less than some threshold.

I have already developed a working algorithm (MATLAB) which randomly prunes edges from nodes with degree $k > k_{max}$ until this condition is met - however I feel it is far from optimal. It is important that the new random subgraph has the same number of vertices and remains undirected (symmetric). Disconnected vertices (with no in/out edges are allowed).

Ideally both original graph $G$ and new random subgraph $G_s$ should result in sparse matrices (i.e. an edge list), however a full adjacency matrix will suffice.

Thanks!!

  • Are you looking for any special kind of randomness properties? – Raziman T V Jan 13 '17 at 17:40
  • Somehow my question was added when I wasn't logged in properly! Raiziman T.V. - I'm not necesarily looking for special randomness properties. – Adam Zienkiewicz Jan 13 '17 at 18:29

Okay, here is an efficient but partial solution: Randomly select a vertex, and from that create the minimum spanning tree. This will make sure that you select each vertex and an associated edge, with minimal degree. Of course this graph is unlikely to include any disconnected vertices. So just include them if they exist in the original graph. If you would like to impose a degree constraint on the MST, you could check here.

At this stage, a minimal graph is established. You could then select some random edges from the original graph and add them until your degree criteria is satisfied. I call this a partial solution because the graph will be pseudo-random, i.e. the only randomness source stem from the selection of initial vertex, and the random edges added afterwards. But that might still work for you.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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