使用图subgraph_isomorphisms查找给定的网络主题

Question

我在寻找小于5,000个节点和小于10000条边的图中大小为5的主题。(所有内容都未着色)

为了做到这一点，我使用方法vf2 (参见下面的示例)，使用R subgraph_isomorphisms的图形库中提供的函数。我使用邻接矩阵生成子图，边列表生成图本身。

我发现很多同构子图都有额外的边。有没有办法只找到具有确切给定结构的子图？使用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)

和我们要找的那个不一样

Answer 1

这个问题的答案在于定义我正在寻找什么和我正在寻找什么。

我正在寻找的是大小为5的网络主题。当我从图论的角度寻找网络主题时，这意味着我正在寻找具有给定邻接矩阵的导出子图。

此函数的作用是找到与给定图同构的图的子图。不同的是，我在寻找导出子图，而函数只给出子图，所以允许额外的边。

这正是我所经历的问题。为了解决这个问题，我最终只比较了我找到的子图的邻接矩阵和motif的邻接矩阵。希望能对某些人有所帮助。

Answer 2

除了前面的注释，我还注意到，当我试图在一个由四个顶点组成的完整图中查找类型为210的同构三元组(2个相互边和1个不对称边)时，该函数返回"True“。解决方案是添加：

subgraph_isomorphisms(subgraph, graph, method = "vf2", **induced = TRUE**)