1

所以我写了一个函数来查找图中度数最小的 k 个节点。它看起来像这样：

def smallestKNodes(G, k):
    leastK = []
    for i in range(G.GetMxNId()):
        # Produces an iterator to the node
        node = G.GetNI(i)
        for j in range(k):
            if j >= len(leastK):
                leastK.append(node)
                break
            elif node.GetDeg() < leastK[j].GetDeg():
                leastK.insert(j, node)
                leastK = leastK[0:k]
                break
    return leastK[0:k]

我的问题是当所有节点的度数相同时，它每次都选择相同的节点。我怎样才能做到这一点，它需要所有零度或其他节点，然后随机选择 k 个节点？

规定：

（1）假设k = 7，那么如果有3个度数为0的节点和10个度数为1的节点，我想选择所有度数为0的节点，但随机选择4个度数为1的节点。

(2) 如果可能，我不想访问任何节点两次，因为可能有太多节点无法放入内存。也可能有非常多的具有最小度数的节点。在某些情况下，也可能存在非常少量的节点。

4

2 回答 2

2

存储所有满足您条件的节点并从中随机选择k节点。您可以通过改组数组（例如Fisher-Yates、std::shuffle、randperm等）并选择第一个k节点（例如）来进行随机选择。

于 2013-09-19T17:37:38.283 回答
1

您可能需要进行两次遍历，第一次遍历以发现您必须随机化的相关度数，选择多少个该度数的节点，以及具有该度数的节点总数。然后，在您的节点上进行第二次传递，仅随机选择具有所需程度的节点。

要选择总k节点，n使每个节点具有公平的概率 ( k/n)，遍历相关节点，并以概率 1、1、...、1、k/(k+1)、k/(k+2) 选择每个节点), ..., k/n。选择节点时，如果k已经选择了节点，则随机丢弃其中一个。

def randomNodesWithSpecificDegree(G, d, k, n):
    result = []
    examined = 0
    for i in range(G.GetMxNId()):
        # Produces an iterator to the node
        node = G.GetNI(i)
        if node.GetDeg() = d:
            examined = examined + 1
            if len(result) < k:
                result.append(node)
            elif random(0...1) < k / examined
                index = random(0...k-1)
                result[index] = node
    assert(examined = n)
    return result

这个伪代码在k很小和n很大的时候都很好（似乎是你的情况）。

于 2013-09-22T13:22:40.440 回答