时间戳

首页 > 解决方案 > 在保留度数的同时重新连接图中的边

r - 在保留度数的同时重新连接图中的边

问题描述

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

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

对于 5 个节点，这可以正常工作，但对于 1000+ 个节点和一些度数（超过 100）的节点，需要大量重复，直到满足条件 1。

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

显式计算所有可能的向量（节点标签），删除无效的向量，然后随机选择一个向量对于大型图来说不是一个好主意。这将占用太多内存，并且仅计算所有这些可能也需要大量时间。

我在寻找什么

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

编码示例

一个使用 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 库很好，如果他们设法加快速度，他们会受到特别欢迎。

附加信息

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

标签： rvectorpermutationgraph-theory

解决方案

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

你说，“我想创建一组新的边，这样每个节点的度数都和以前一样。” 如果我是你，我会修改 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
}

推荐阅读