[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] dyads and triads census
From: |
Gabor Csardi |
Subject: |
Re: [igraph] dyads and triads census |
Date: |
Wed, 26 Sep 2007 15:47:21 +0200 |
User-agent: |
Mutt/1.5.13 (2006-08-11) |
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