Nano Hash - криптовалюты, майнинг, программирование

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

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

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

Итак, предположим, я попал в вершину 1 (которая здесь первая строка). Мы видим, что он имеет исходящие ссылки на вершину 4,5,18,22,23,24,25. Итак, следующие вершины будут связаны с 4,5,18 ... 25, то есть значениями в row4, 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 будет наиболее полезным (но меня интересует алгоритм, поэтому любой питон, рубин и т. Д. Будет отличным). Результирующий вектор будет иметь длину 115 (8x25 = 200 - 85 NA = 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

r matrix igraph adjacency-list
27.03.2013

  • интересные комментарии. Теперь, когда вы, ребята, настаиваете. Эта матрица представляет собой матрицу смежности с именами векторов вместо двоичных флагов. Результатом будет модель потока эпидемии ... за исключением того, что она моделирует не болезнь, а скорее дефолт банка !! :) Что касается подсказки ... ну, из последних 2 недель кодирования я понял, что с языками высокого уровня, такими как R / java, манипулировать векторами было намного лучше, чем с типами символов старой школы в C ++. 28.03.2013
  • Подождите, разве это не поиск в ширину по графику? 28.03.2013
  • Взгляните на graph.bfs(), особенно на аргумент order. 28.03.2013
  • @Marius да ... это именно то, чего я пытаюсь достичь! За исключением того, что это не прямолинейный граф erdos.reyni, использование первого в ширину приведет к бесконечной последовательности ... Я просто хочу знать, как получить первые несколько. будет смотреть на graph.bfs () 28.03.2013
  • Поиск в ширину работает на неориентированных графах, потому что вы ведете список узлов, которые посетили, он не заканчивается бесконечностью, он просто достигает всех достижимых узлов. 28.03.2013
  • @Marius Ты мужчина! Это именно то, что я искал! Спасибо 28.03.2013
  • @jordan, конечно, та же проблема. Но не обязательно один и тот же вопрос. Этот (до редактирования) был о матрице упорядочения независимо от контекста или языка. Речь идет о теории графов и поиске в ширину. Я попытался удалить обман, но мне нужно было больше голосов. Поразмыслив, мы можем оставить это педантикам, стремящимся отсортировать матрицы нерегулярным образом. Решением будет сортировка матриц без использования функции предварительного определения. Я нигде не нашел алгоритма сортировки для такой проблемы. Спасибо за помощь, ребята. 28.03.2013

Ответы:


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

введите описание изображения здесь

27.03.2013

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() транспонирует матрицу.

Матрица хранится в порядке «сначала столбцы» (или столбец-майор). :

> 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 или igraph пакетов.

27.03.2013
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..