Перепишите ребра на графике, сохранив градусы - PullRequest
Новая
       15

Перепишите ребра на графике, сохранив градусы

0 голосов
/ 18 мая 2018

Предположим, у меня есть граф с 5 узлами. Каждый узел имеет определенное количество ребер (без ребер от узла к себе), которые называются степенью этого узла. Я хочу создать новый набор ребер, чтобы каждый узел имел ту же степень, что и раньше.

Моя первая попытка - создать вектор, в котором каждый узел v имеет записи степени (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 - это хорошо, они особенно приветствуются, если им удается ускорить процесс.

Дополнительная информация

Вместо того, чтобы просто иметь вектор узлов (с повторениями столько раз, сколько они появляются в ребрах), можно предположить, что фактические ребра в исходном графе также предоставляются.

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Я думаю, что альтернативным способом решения этой проблемы является использование модели роста, такой как модель Эрдоша-Рени , которая полезна для генерации случайных графиков.

Вы сказали: «Я хочусоздать новый набор ребер, чтобы каждый узел имел ту же степень, что и раньше. "На вашем месте я бы изменил модель 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))
}

Как вы видите, я использовал хэш-карту для хранения степени каждого узла и получения ее быстро при необходимости (см. Переменную степеньMapи функции увеличенияDegree и 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
}
0 голосов
/ 18 мая 2018

Очевидно, эта проблема называется рандомизация с сохранением степени .Это можно сделать путем многократной переподключения, которая работает следующим образом:

Пример двух ребер, назовем их AB и CD.Если A отличается от C, а D отличается от b, выбранные ребра будут удалены и заменены AC и BD.Повторяя это достаточно много раз, ребра рандомизируются.

Конечно, это также может быть применено к векторному примеру путем составления списка ребер и случайной выборки их.

...