使用 igraph subgraph_isomorphisms 查找给定的网络图案

Question

我正在寻找少于 5000 个节点和少于 10000 条边的图形中大小为 5 的图案。（一切未着色）

为此，我使用 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)

这与我们要找的那个不同

Answer 1

这个问题的答案是我正在寻找的东西和我正在寻找的东西的定义。

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

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

这正是我遇到的问题。为了处理它，我最终只是将我发现的子图的邻接矩阵与主题的邻接矩阵进行比较。希望对大家有所帮助。

Answer 2

添加到之前的评论中，我还注意到函数 returns“True”，当我试图在一个完整的四个图内找到类型为 210 的同构三元组（2 个互边和 1 个不对称）时顶点。解决方法是添加：

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

使用 igraph subgraph_isomorphisms 查找给定的网络图案

Using igraph subgraph_isomorphisms to find given network motifs

r

graph-theory

isomorphism

subgraph

igraph