我正在寻找一种有效生成随机无向子图的方法$G_s$和$N$顶点，使用来自现有无向图的边的子集$G$, 大小也一样$N$, 其中子图只有度数的节点$k \leq k_{max}$.

换句话说，我想创建一个具有相同顶点数的新随机图，但具有一组随机的原始边$G$删除，使得新图的最大度数小于某个阈值。

我已经开发了一种工作算法（MATLAB），它从具有度数的节点中随机修剪边缘$k > k_{max}$直到满足这个条件 - 但是我觉得它远非最佳。重要的是新的随机子图具有相同数量的顶点并保持无向（对称）。断开的顶点（不允许输入/输出边）。

理想情况下都是原始图$G$和新的随机子图$G_s$应该导致稀疏矩阵（即边缘列表），但是完整的邻接矩阵就足够了。

谢谢！！