时间戳

首页 > 解决方案 > 为什么最后一个索引的节点在使用 igraph 生成的随机网络中没有过度代表？

c - 为什么最后一个索引的节点在使用 igraph 生成的随机网络中没有过度代表？

问题描述

我正在使用 R 接口igraph生成一个随机有向网络 (Erdös-Rényi)，其节点数n和边数 为常数m，使用函数sample_gnm。

为了确保我理解所使用的算法，我检查了 C 源代码，尽管我没有 C 经验。据我了解 C 代码，有一个if语句应该导致索引节点的过度表示n接收有向边。

这是真正的代码： https ://github.com/igraph/igraph/blob/7d4be976481356fa673772e6e7c30b637ea8dd52/src/games.c#L734-L736 ，这就是我理解伪代码中的C代码的方式：

# What is the maximum number of edges a network with n nodes could have
maxEdges := n*(n-1)

s := uniformly sample m integers from [1, maxEdges] without replacement

for (i = 1; i = m; i++) {

  # Get IDs for nodes A and B with equal probability over n
  nodeA := floor(s[i] / (n)) + 1
  nodeB := s - ((nodeA - 1) * n)

  # Since we do not allow loops, if nodeA = nodeB, assign n to nodeB
  if (nodeA = nodeB) {
    nodeB := n
  }

}

但是，我还在 R 中运行了一个模拟，以确保情况确实如此：

testFun = function(n,m) {

  # Generate the network
  g = sample_gnm(n, m, directed = TRUE, loops = FALSE)

  # Find the "to" node IDs
  toEdgename = ends(g, E(g))[, 2]

  return(toEdgename)

}

# Create 1000 random networks and get the "to" node name for each edge
spam = replicate(1000, testFun(100, 9000))
# Plot the histogram
hist(sapply(1:ncol(spam), 
            # Count the percent of times the index 100 appeared per simulation
            function(ii) sum(spam[, ii] == 100) / 9000), 
     100)

令我惊讶的是，它不会导致可观察到的偏差。这一定意味着我不理解 C 代码在做什么。谁能帮我理解为什么这段 C 代码不会导致n索引的过度表示？

标签： crigraph

解决方案

原因是nodeB在您的伪代码中永远不可能是n（或者，在 C 代码中，它永远不可能是no_of_nodes - 1. （但是，nodeA 可以是n！）

实际上，maxEdges (mod n -1)nodeB给出了最大值，mod n -1 中的值在 [0, n -1[; 请注意，上限是独占的。

推荐阅读