CODEWITHSUNDEEP
igraph
alberto
alberto

Reputation: 2645

Count only a subset of motifs of size k

I want to count the motifs of size 4 in a tree graph:

library(igraph)
g <- barabasi.game(100)
census.motifs <- motifs(g, size=4)[c(4,8,13,30)]

There are 217 possible graphs with 4 vertices, but only 4 of them can appear in a directed rooted tree.

Is there a way to tell igraph that it only has to look for those 4? Or a faster/clever way to do this?

Upvotes: 0

Views: 84

Answers (1)

Ryan Haunfelder
Ryan Haunfelder

Reputation: 786

The four motifs in a directed rooted tree could be counted as k-instars using the ergm package http://svitsrv25.epfl.ch/R-doc/library/ergm/html/ergm-terms.html

A k-instar is a set of k nodes all sharing one common root. If n is the number of nodes in your tree, the counts for your 4 motifs will be the number of 3-instars (fully connected), (n-3) times the number of 2-instars (two edges connecting to root and one other node), (n-2) choose 2 times the number of 1-instars (one edge connecting to the the root and two other nodes), and n choose 4 minus the sum of the previous three counts. In R you could use,

library(intergraph)
library(ergm)
library(igraph)
n <- 100
g <- barabasi.game(n)
kistars <- summary(asNetwork(g)~istar(1:3))
kistars[3]
(n-3)*kistars[2]
choose(n-2,2)*kistars[1]
choose(n,4)*sum(kistars)

Upvotes: 1

Related Questions