Почему узлы последнего индекса не перепредставлены в случайных сетях, сгенерированных с помощью igraph? - PullRequest
Новая
       15

Почему узлы последнего индекса не перепредставлены в случайных сетях, сгенерированных с помощью igraph?

4 голосов
/ 28 июня 2019

Я использую интерфейс 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?

1 Ответ

2 голосов
/ 28 июня 2019

Причина в том, что nodeB в вашем псевдокоде никогда не может быть n (или, в коде C, оно никогда не может быть no_of_nodes - 1. (Однако nodeA может быть n!)

Фактически, максимальное значение для nodeB задается как maxEdges (мод n -1), а значения в моде n -1 равны в диапазоне [0, n -1 [; обратите внимание, что верхняя граница является исключительной.

...