Re: [igraph] dyads and triads census

[Gabor Csardi]

Simone,

Finding the dyads is easy based on reciprocity:

dyad.census <- function(graph) {
  vc <- vcount(graph)
  ec <- ecount(graph)
  mut <- reciprocity(graph)
  d <- mut*ec/(mut+1)
  s <- ec-2*d
  m <- vc*(vc-1)/2-d-s
  c(Mut=d, Asym=s, Null=m)
}

As Tamas mentioned, motif finding kinda works for triads, but it does 
not find the unconnected triads, so some extra work is needed.

motif24 <- function(graph) {
  res <- c(0,0)
  vc <- vcount(graph)
  for (e in seq(ecount(graph))-1) {
    ed <- get.edge(graph,e)
    mut <- are.connected(graph,ed[2],ed[1])
    if (mut && ed[1]>=ed[2]) { next }
    reachable <- unique(c(neighbors(graph, ed[1], mode="all"),
                          neighbors(graph, ed[2], mode="all"),
                          ed))
    if (!mut) {
      res[1] <- res[1] + vc-length(reachable)
    } else {
      res[2] <- res[2] + vc-length(reachable)
    }
  }
  res
}   

triad.census <- function(graph) {
  motifs <- graph.motifs(graph)
  vc <- vcount(graph)  
  ec <- ecount(graph)
  iso <- sum(degree(graph)==0)
  motifs[c(2,4)] <- motif24(graph)
  motifs[1] <- vc*(vc-1)*(vc-2)/6 - sum(motifs)
  names(motifs) <- c("003", "012", "021U", "102", "021C", "111D", "021D", 
"030T",
                     "120D", "111U", "201", "030C", "120C", "120U", "210", 
"300")
  motifs[ c("003","012","102","021D","021U","021C","111D","111U",
            "030T","030C","201","120D","120U","120C","210","300")]
}

motif24 is quite slow with the current implementation, but perhaps
it will do for your graphs.

Thanks for the suggestion, i'll include these (a better implementation
though) in igraph, maybe in the next release. I haven't checked these 
functions extensively, please check them.

Gabor

On Wed, Sep 26, 2007 at 10:04:40AM +0200, Tamas Nepusz wrote:
> Dear Simone,
> 
> > I couldn't find them in igraph, so I was wondering, are you planning
> > to include them in future release?
> I think what you call dyad and triad census is what igraph calls
> "counting the motifs in a graph". The corresponding C function is:
> 
> http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph-Motifs.html
> 
> If you are using the R interface, you should check the graph.motifs,
> graph.motifs.no and graph.isoclass functions.
> 
> -- 
> Tamas
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK