Использование igraph subgraph_isomorphisms для поиска заданных сетевых мотивов - PullRequest
Новая
       47

Использование igraph subgraph_isomorphisms для поиска заданных сетевых мотивов

0 голосов
/ 07 июня 2019

Я ищу мотивы размера 5 на графиках с менее чем 5000 узлов и менее чем 10000 ребер.(все неокрашено)

Для этого я использую функцию, предоставленную в библиотеке igraph для R subgraph_isomorphisms с использованием метода vf2 (см. пример ниже).Я использую матрицу смежности для генерации подграфа и список ребер для генерации самого графа.

У многих изоморфных подграфов, которые я нахожу, есть дополнительные ребра.Есть ли способ найти только подграфы с точно заданной структурой?Поиск ответов с использованием igraph или любой другой библиотеки в R

См. Воспроизводимый пример ниже (смотреть на этот пример намного проще, если просто нарисовать график, заданный этой матрицей смежности, на листе бумаги) 

library(igraph)

subgraph <- matrix(
  data = c(0, 1,
           1, 0), ncol = 2)

graph <- matrix(
  data = c(0, 1, 0, 0,
           1, 1, 0, 1,
           1, 0, 0, 1,
           0, 0, 1, 0), ncol = 4)

subgraph <- graph_from_adjacency_matrix(subgraph, mode = "directed", weighted = T, diag = T)
graph    <- graph_from_adjacency_matrix(graph,    mode = "directed", weighted = T, diag = T)
subgraph_isomorphisms(subgraph, graph, method = "vf2")

Выходные данные дают две пары (1,2) и (3,4), когда на самом деле матрица смежности (1,2) выглядит как

(0 1) (1 1)

Который отличается от того, который мы искали

1 Ответ

1 голос
/ 16 июля 2019

Ответ на этот вопрос в определениях того, что я ищу и что я нахожу.

Я искал сетевые мотивы размера 5. Когда я ищу сетьмотивы с точки зрения теории графов это означает, что я ищу индуцированные подграфы с заданной матрицей смежности.

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

Это именно та проблема, с которой я столкнулся.Чтобы справиться с этим, я просто сравнил найденную мной матрицу смежности с подграфами.Надеюсь, это кому-нибудь пригодится.

...