具有给定稀疏性的随机简单连通图生成

Question

我正在尝试找到一种有效的算法来生成具有给定稀疏性的简单连通图.就像是:

Input:
    N - size of generated graph
    S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
    simple connected graph G(v,e) with N vertices and S edges

Answer 1

高层次的想法

1. 生成具有N个节点和N-1个边缘的(统一选择的)随机生成树.
2. 在达到所请求的边数之前,在任意两个随机节点之间添加边.

创建生成树

该基于分区的答案由ypnos是一个良好的开端,但偏压由总是选择一个访问节点的新边缘的一端引入.通过在每次迭代中随机选择一个访问节点,开始访问的节点具有更多迭代,从中可以选择它们.因此,较早的节点更可能具有高度(边数)而不是稍后选取的节点.

偏见的例子

例如,对于4节点连通图而不是生成线性路径图(这是75%的可能生成树),这种偏差将导致生成的星图大于25%的概率它应该是.

偏见并不总是坏事.事实证明,这种偏差有利于生成类似于现实世界计算机网络的生成树.但是,为了创建真正随机连接的图形,必须从可能的生成树集合中统一选取初始生成树(请参阅Wikipedia的统一生成树文章).

随机游走方法

生成统一生成树的一种方法是通过随机游走.以下是威尔逊描述简单随机游走算法的文章比封面时间更快地生成随机生成树的文章.

从任何顶点开始,在图上做一个简单的随机游走.每次遇到顶点时,都要标记发现顶点的边.当发现所有顶点时,标记的边形成随机生成树.该算法易于编码,运行时间常数较小,并且可以很好地证明它可以生成具有正确概率的树.

这适用于简单的连通图,但是如果你需要一个有向图的算法,那么在描述Wilson的算法时,请进一步阅读本文.这是随机生成树和Wilson算法的另一种资源.

履行

由于我也对这个问题感兴趣,我编写了各种方法的Python实现,包括随机游走方法.请随意查看GitHub上代码的要点.

以下是随机游走方法代码的摘录:

# Create two partitions, S and T. Initially store all nodes in S.
S, T = set(nodes), set()

# Pick a random node, and mark it as visited and the current node.
current_node = random.sample(S, 1).pop()
S.remove(current_node)
T.add(current_node)

graph = Graph(nodes)

# Create a random connected graph.
while S:
    # Randomly pick the next node from the neighbors of the current node.
    # As we are generating a connected graph, we assume a complete graph.
    neighbor_node = random.sample(nodes, 1).pop()
    # If the new node hasn't been visited, add the edge from current to new.
    if neighbor_node not in T:
        edge = (current_node, neighbor_node)
        graph.add_edge(edge)
        S.remove(neighbor_node)
        T.add(neighbor_node)
    # Set the new node as the current node.
    current_node = neighbor_node

# Add random edges until the number of desired edges is reached.
graph.add_random_edges(num_edges)

Answer 2

对于每个节点,您至少需要一个边缘.

从一个节点开始.在每次迭代中,创建一个新节点和一个新边.边缘是将新节点与前一节点集中的随机节点连接起来.

创建所有节点后,创建随机边缘,直到满足S.确保不要创建双边(为此可以使用邻接矩阵).

随机图在O(S)中完成.