Получить цепочку заражений из матрицы смежности, r, igraph

Question

У меня есть диаграмма erdos.reyni. Я заражу вершину и хочу посмотреть, какая последовательность вершин будет следовать за болезнью? igraph имеет такие функции, как get.adjacency(), neighbors().

Подробнее. Это матрица смежности с именами вершин вместо 0,1 флагов, и я пытаюсь получить из нее цепочку заражений. Как поток/последовательность эпидемии через граф, если определенная вершина заражена. Давайте не будем беспокоиться о вероятности заражения здесь (предположим, что все удары вершин заражены с вероятностью 1).

Итак, предположим, что я ударил вершину 1 (здесь находится строка 1). Мы видим, что он имеет исходящие ссылки на вершину 4,5,18,22,23,24,25. Таким образом, следующими вершинами будут те, которые связаны с 4,5,18 ... 25, то есть эти значения в строках4, row5, row18, ... row25. Затем, согласно модели, болезнь будет проходить через эти и так далее.

Я понимаю, что могу передать строку для упорядочивания строк матрицы. Моя проблема в том, что я не могу понять, как сгенерировать эту последовательность.

Матрица выглядит следующим образом.

> channel 
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] 
[1,] 4 5 18 22 23 24 25 NA 
[2,] 6 10 11 18 25 NA NA NA 
[3,] 7 11 18 20 NA NA NA NA 
[4,] 24 NA NA NA NA NA NA NA 
[5,] 1 3 9 13 14 NA NA NA 
[6,] 3 8 9 14 19 23 NA NA 
[7,] 3 4 8 15 20 22 NA NA 
[8,] 2 3 25 NA NA NA NA NA 
[9,] 3 4 11 13 20 NA NA NA 
[10,] 4 5 8 15 19 20 21 22 
[11,] 3 13 15 18 19 23 NA NA 
[12,] 11 13 16 NA NA NA NA NA 
[13,] 4 6 14 15 16 17 19 21 
[14,] 2 6 13 NA NA NA NA NA 
[15,] 3 17 20 NA NA NA NA NA 
[16,] 6 15 18 23 NA NA NA NA 
[17,] 2 25 NA NA NA NA NA NA 
[18,] 2 5 NA NA NA NA NA NA 
[19,] 3 11 NA NA NA NA NA NA 
[20,] 1 4 7 10 12 21 22 25 
[21,] 2 4 6 13 14 16 18 NA 
[22,] 1 3 4 15 23 NA NA NA 
[23,] 1 16 24 NA NA NA NA NA 
[24,] 7 8 19 20 22 NA NA NA 
[25,] 7 12 13 17 NA NA NA NA 

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

R будет наиболее полезным (но я заинтересован в алгоритме так что любой Python, Ruby, etc.will быть большим). Результирующий вектор будет иметь длину 115 (8x25 = 200 - 85 NAs = 115). и будет выглядеть так. Это в основном то, как болезнь распространится, если вершина 1 станет зараженной.

4,5,18,22,23,24,25,24,1,3,9,13,14,2,5,1,3,4,15,23,1,16,24,7,8,19,20,22,7,12,13,17,7,8,19,20,22, 4,5,18,22,23,24,25,7,11,18,20... 

То, что я знаю, до сих пор: 1. R имеет пакет **igraph**, который позволяет мне вычислить соседей (graph, vertex, "out") 2. То же пакет также может генерировать get.adjlist(graph...), get.adjacency

Answer 1

Поиск «цепи заражения», подобной этому, эквивалентен поиску по ширине в первом порядке, например.:

library(igraph) 
set.seed(50) 
g = erdos.renyi.game(20, 0.1) 
plot(g) 
order = graph.bfs(g, root=14, order=TRUE, unreachable=FALSE)$order 

Выход:

> order 
[1] 14 1 2 11 16 18 4 19 12 17 20 7 8 15 5 13 9 NaN NaN NaN 

Answer 2

Это не ясно, как вы определяете порядок ряды, так ... только несколько советов:

Вы можете выбрать перестановку/комбинацию строк пропускания вектора индекса:

> (m <- matrix(data=1:9, nrow=3)) 
    [,1] [,2] [,3] 
[1,] 1 4 7 
[2,] 2 5 8 
[3,] 3 6 9 
> m[c(2,3,1),] 
    [,1] [,2] [,3] 
[1,] 2 5 8 
[2,] 3 6 9 
[3,] 1 4 7 

Функция t() переносит матрицу.

Матрица хранится в столбцах первой (или column-major) порядка:

> as.vector(m) 
[1] 1 2 3 4 5 6 7 8 9 

NA значения могут быть удалены с помощью подмножества:

> qq <- c(1,2,NA,5,7,NA,3,NA,NA) 
> qq[!is.na(qq)] 
[1] 1 2 5 7 3 

Кроме того, алгоритмы графа представленной Bioconductor-х graph или CRAN's igraph.