在保留度数的同时重新连接图形中的边缘

Question

假设我有一个包含5个节点的图表。每个节点都有一定数量的边（没有从节点到自身的边），这些边称为该节点的度。我想创建一组新的边，以便每个节点具有与以前相同的程度。

我的第一个尝试是创建一个向量，其中每个节点v具有度（v）条目，对该向量进行采样（以获得该向量的置换），将该向量分成两个相等长度的向量并检查是否在第n个条目中两个向量是不同的（称为条件1）。如果是这种情况，则两个向量将形成边缘列表，从节点到其自身没有边缘。

对于5个节点，这可以正常工作，但是对于1000多个节点和一些具有度数（超过100）的节点，在满足条件1之前需要大量重复。

我的第二次尝试是sample()，创建两个向量并再次从那些不满足条件1的节点对中进行采样，然后添加分割结果并将它们添加到剩余的两个向量中并重复几次直到任一条件1满足或违反条件1的节点集合不能正确匹配以形成适当的边缘（即那些不违反条件1的边缘）。

显式计算所有可能的向量（节点标签），删除无效的向量然后随机选择一个对于大图不是一个好主意。它需要太多的内存，只是计算它们所有这些也可能需要花费很多时间。

What I'm looking for

给定一个节点向量（只是整数标签，偶数长度），返回一个随机选择的（因此它需要使用像sample()或其他一些基于伪随机数的函数）的节点对（最好是两个向量形式）边缘列表），以便每个边连接两个不同的节点，节点的度数保持不变。

Coding example

一个使用5个节点的小编码示例：E<-c(1,1,1,1,2,2,2,3,3,4,4,4,5,5)

有效的解决方案：

V1<-c(1,1,1,1,2,2,4) V2<-c(2,3,4,5,3,4,5)

另一个有效的解决方案（这有一个重复的边缘，这是允许的）：

V1<-c(1,1,1,1,2,2,3) V2<-c(2,3,4,5,4,4,5)

不是有效的解决方案（这有一个自我边缘，这是不允许的）：

V1<-c(1,2,1,1,2,2,4) V2<-c(1,3,4,5,3,4,5)

使用（异国情调的）R库是好的，如果他们设法加快速度，他们会特别受欢迎。

Additional information

可以假设还提供了原始图中的实际边缘，而不是仅具有节点的矢量（重复次数与它们在边缘中出现的次数）。

Answer 1

显然这个问题叫做degree-preserving randomization。它可以通过反复重新布线来完成，其工作方式如下：

采样两条边，我们称之为AB和CD。如果A与C不同且D与b不同，则采样边缘将被移除并由AC和BD替换。通过多次重复这一过程，边缘是随机的。

当然，这也可以通过制作边列表并随机采样来应用于矢量示例。

Answer 2

我认为解决这个问题的另一种方法是使用增长模型，如Erdos-Renyi model，这有助于生成随机图。

你说，“我想创建一组新的边缘，以便每个节点具有与以前相同的度数。”如果我是你，我会修改Erdos-Renyi模型以生成新图。

首先，您需要创建一个图表。以下代码（正是函数randomGraph）可以为您完成。

#install.packages("network")
library(network)

increaseDegree <- function(key, degreeMap) {
  keyChar = as.character(key)
  if(is.null(degreeMap[[keyChar]])) {
    degreeMap[[keyChar]] = 0
  }
  degreeMap[[keyChar]] = degreeMap[[keyChar]]  + 1
  return(degreeMap)
}

getDegree <- function(key, degreeMap) {
  keyChar = as.character(key)
  if(is.null(degreeMap[[keyChar]])) {
    return (0)
  } else {
    return (degreeMap[[keyChar]])
  }
}

randomGraph <- function(numNodes) {
  degreeMap <- new.env(hash=T, parent=emptyenv())
  initialNumNodes = 2;
  g <- network.initialize(numNodes, directed = FALSE);
  add.edge(g,1,2);
  increaseDegree(1, degreeMap)
  increaseDegree(2, degreeMap)
  i = 3;
  while(i <= numNodes) {
    sourceNode <- i;
    destNode <- sample(i-1, 1);
    add.edge(g,sourceNode,destNode);
    increaseDegree(sourceNode, degreeMap)
    increaseDegree(destNode, degreeMap)
    i = i + 1;
  }
  return (list(graph = g, degreeMap = degreeMap))
}

如您所见，我使用哈希映射来存储每个节点的程度，并在需要时快速获取它（请参阅degreeMap变量和函数increaseDegree和getDegree）。

之后，您将获得第一张图表。但是，您需要第二个图形，其中每个节点具有与以前相同的程度。为此，您可以修改randomGraph函数并使用第一个图创建新图。因此，修改后的函数将类似于：

newGraphPresevingDegree <- function(oldGraphObject) {
  oldGraph = oldGraphObject$graph
  oldDegreeMap = oldGraphObject$degreeMap

  numNodes = network.size(oldGraph)
  newGraph <- network.initialize(numNodes, directed = FALSE);
  newDegreeMap <- new.env(hash=T, parent=emptyenv())
  i = 1;
  while(i <= numNodes) {
    sourceNode <- i;
    sourceDesiredDegree = getDegree(sourceNode, oldDegreeMap);
    sourceCurrentDegree =  getDegree(sourceNode, newDegreeMap);
    while(sourceCurrentDegree < sourceDesiredDegree) {
      destNode <- sample(i:numNodes, 1);
      destDesiredDegree = getDegree(destNode, oldDegreeMap);
      destCurrentDegree =  getDegree(destNode, newDegreeMap);
      if(sourceNode != destNode && sourceCurrentDegree < sourceDesiredDegree
         && destCurrentDegree < destDesiredDegree && is.adjacent(newGraph,sourceNode,destNode) == FALSE) {
        add.edge(newGraph, sourceNode, destNode);
        increaseDegree(sourceNode, newDegreeMap)
        increaseDegree(destNode, newDegreeMap)
        sourceCurrentDegree =  getDegree(sourceNode, newDegreeMap);
      }
    }
    i = i + 1;
  }
  return (list(graph = newGraph, degreeMap = newDegreeMap))
}

最后，您执行以下操作：

# creating a random graph
numNodes = 3000;
oldGraphObject = randomGraph(numNodes)
oldGraph = oldGraphObject$graph
oldDegreeMap = oldGraphObject$degreeMap

#creating the new graph
newGraphObject = newGraphPresevingDegree(oldGraphObject)
newGraph = newGraphObject$graph
newDegreeMap = newGraphObject$degreeMap

并检查学位是否保持不变：

i = 1
while(i <= numNodes) {
  oldDegree = length(get.neighborhood(oldGraph, i))
  currentDegree = length(get.neighborhood(newGraph, i))
  if(oldDegree != currentDegree) {
    print(paste("old neighborhood of node", i))
    print(get.neighborhood(oldGraph, i))

    print(paste("new neighborhood of node", i))
    print(get.neighborhood(newGraph, i))
    print("------------")
  }
  i = i + 1
}