0

I'm looking for motifs of size 5 in graphs with less than 5000 nodes and less than 10000 edges. (everything uncolored)

To do this I use function provided in igraph library for R subgraph_isomorphisms using method vf2 (see example below). I use adjacency matrix to generate subgraph and edgelist to generate the graph itself.

A lot of isomorphic subgraphs that I find have extra edges. Is there any way to only find subgraphs with exact given structure? Looking for answers using igraph or any other library in R

See reproducible example below (looking at this example is way easier if you just draw graph given by this adjacency matrix on a piece of paper)

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")

Output gives you two pairs of (1,2) and (3,4), when in fact adjacency matrix of (1,2) looks like

(0 1) (1 1)

Which is different from the one we were looking for

4

2 回答 2

1

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

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

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

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

于 2019-07-16T16:02:00.087 回答
0

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

subgraph_isomorphisms(subgraph, graph, method = "vf2", **induced = TRUE**)
于 2021-06-01T09:48:43.757 回答