Как создать взвешенный список / матрицу смежности из списка краев?

Моя проблема очень проста: мне нужно создать список / матрицу смежности из списка ребер.

У меня есть список краев, хранящийся в документе csv, с column1 = node1 и column2 = node2, и я хотел бы преобразовать его в взвешенный список смежности или взвешенную матрицу смежности.

Чтобы быть более точным, вот как выглядят данные - где числа - это просто идентификаторы узлов:

node1,node2
551,548
510,512
548,553
505,504
510,512
552,543
512,510
512,510
551,548
548,543
543,547
543,548
548,543
548,542

Любые советы о том, как добиться преобразования из этого в список / матрицу взвешенной смежности? Вот как я решил сделать это раньше, но безуспешно (любезно предоставлено Дай Шизука) :

dat=read.csv(file.choose(),header=TRUE) # choose an edgelist in .csv file format
el=as.matrix(dat) # coerces the data into a two-column matrix format that igraph likes
el[,1]=as.character(el[,1])
el[,2]=as.character(el[,2])
g=graph.edgelist(el,directed=FALSE) # turns the edgelist into a 'graph object'

Спасибо!


r igraph adjacency-list adjacency-matrix sna
person Milo    schedule 16.05.2013    source источник
comment
Не могли бы вы предоставить нам небольшой воспроизводимый пример и ваши возможные попытки его кодирования?   -  person Roman Luštrik    schedule 16.05.2013
comment
Этот пост может быть полезным.   -  person Arun    schedule 16.05.2013
comment
Спасибо @Arun за то, что указал мне на этот пост. Это действительно полезно, но, если я не ошибаюсь, их данные уже организованы в виде матрицы, тогда как, как вы можете видеть из отредактированной версии моего вопроса, у меня другой ввод. Отредактировав пост, надеюсь, я ответил и Роману.   -  person Milo    schedule 16.05.2013

Ответы (4)


arrow_upward
18
arrow_downward

В этом ответе используется только основание R. Результатом является стандартная матрица, используемая для представления матрицы смежности.

 el  <- cbind(a=1:5, b=5:1) #edgelist (a=origin, b=destination)
 mat <- matrix(0, 5, 5)
 mat[el] <- 1
 mat
 #    [,1] [,2] [,3] [,4] [,5]
 #[1,]    0    0    0    0    1
 #[2,]    0    0    0    1    0
 #[3,]    0    0    1    0    0
 #[4,]    0    1    0    0    0
 #[5,]    1    0    0    0    0

Здесь mat - ваша матрица смежности, определенная из списка редакторов el, который представляет собой простой cbind векторов 1:5 и 5:1.

Если ваш список редакторов включает веса, вам нужно немного другое решение.

el <- cbind(a=1:5, b=5:1, c=c(3,1,2,1,1)) # edgelist (a=origin, b=destination, c=weight)
mat<-matrix(0, 5, 5)
for(i in 1:NROW(el)) mat[ el[i,1], el[i,2] ] <- el[i,3]  # SEE UPDATE
mat
#     [,1] [,2] [,3] [,4] [,5]
#[1,]    0    0    0    0    3
#[2,]    0    0    0    1    0
#[3,]    0    0    2    0    0
#[4,]    0    1    0    0    0
#[5,]    1    0    0    0    0

ОБНОВЛЕНИЕ

Некоторое время спустя я понял, что цикл for (3-я строка) в предыдущем примере взвешенного списка редакторов не нужен. Вы можете заменить его следующей векторизованной операцией:

mat[el[,1:2]] <- el[,3]
person ndoogan    schedule 16.05.2013
comment
Я попробовал ваш ответ, и он работает! вы знаете, как построить результаты? Вот мой вопрос, не могли бы вы взглянуть? Спасибо! stackoverflow.com/questions/64841361 / - person stats555; 15.11.2020

arrow_upward
16
arrow_downward

Сообщение на моем веб-сайте, которое вы упомянули в вопросе (https://sites.google.com/site/daishizuka/toolkits/sna/sna_data) использует пакет igraph, поэтому убедитесь, что он загружен.

Более того, недавно я понял, что igraph предоставляет гораздо более простой способ создать взвешенную матрицу смежности из списков edgelists, используя graph.data.frame (). Я обновил это на своем сайте, но вот простой пример:

library(igraph)
el=matrix(c('a','b','c','d','a','d','a','b','c','d'),ncol=2,byrow=TRUE) #a sample edgelist
g=graph.data.frame(el)
get.adjacency(g,sparse=FALSE)

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

el=matrix(c('a','b','c','d','a','d','a','b','c','d'),ncol=2,byrow=TRUE) #a sample edgelist
lab=names(table(el)) #extract the existing node IDs
mat=matrix(0,nrow=length(lab),ncol=length(lab),dimnames=list(lab,lab)) #create a matrix of 0s with the node IDs as rows and columns
for (i in 1:nrow(el)) mat[el[i,1],el[i,2]]=mat[el[i,1],el[i,2]]+1 #for each row in the edgelist, find the appropriate cell in the empty matrix and add 1.
person Dai Shizuka    schedule 29.06.2013
comment
Обратите внимание, что для взвешенной сети вы захотите добавить attr='weight' к вызову get.adjacency(), чтобы он возвращал взвешенную матрицу смежности вместо невзвешенной версии. - person Keith Hughitt; 18.07.2016
comment
отличная ссылка, в ней также показано использование рамки для импорта списка краев. Я не вижу эквивалентного API в Python: / - person user305883; 12.10.2016

arrow_upward
9
arrow_downward

Начните с краев фрейма данных и используйте igraph для получения матрицы смежности:

голова (края)

  node1 node2
1   551   548
2   510   512
3   548   553
4   505   504
5   510   512
6   552   543

library(igraph)
as.matrix(get.adjacency(graph.data.frame(edges)))

    551 510 548 505 552 512 543 553 504 547 542
551   0   0   2   0   0   0   0   0   0   0   0
510   0   0   0   0   0   2   0   0   0   0   0
548   0   0   0   0   0   0   2   1   0   0   1
505   0   0   0   0   0   0   0   0   1   0   0
552   0   0   0   0   0   0   1   0   0   0   0
512   0   2   0   0   0   0   0   0   0   0   0
543   0   0   1   0   0   0   0   0   0   1   0
553   0   0   0   0   0   0   0   0   0   0   0
504   0   0   0   0   0   0   0   0   0   0   0
547   0   0   0   0   0   0   0   0   0   0   0
542   0   0   0   0   0   0   0   0   0   0   0
person Sandipan Dey    schedule 04.10.2016

arrow_upward
0
arrow_downward

Другая возможность с пакетом qdapTools:

library(qdapTools)

el[rep(seq_len(nrow(el)), el[,'c']), c('a', 'b')] %>%
    {split(.[,'b'], .[,'a'])} %>%
    mtabulate()

##   1 2 3 4 5
## 1 0 0 0 0 3
## 2 0 0 0 1 0
## 3 0 0 2 0 0
## 4 0 1 0 0 0
## 5 1 0 0 0 0
person Tyler Rinker    schedule 04.10.2016