2

I have a list of graphs (igraph format) and I would like to obtain a merge graph, which would be the intersection of those nodes and vertices that are shared a certain percentage trough all the graphs.

I know that igraph library has the function graph.intersection() but this function intersect all the vertices and nodes present in all the graphs.

Any help would be much appreciated

Here is a brief example

g1 <- graph.data.frame(df1, directed=F)
df2 <- data.frame(V1=c(1,2,2,3,4), V2=c(3,3,5,5,5))
g2 <- graph.data.frame(df2, directed=F)
df3 <- data.frame(V1=c(1,2,3,4), V2=c(3,3,5,5))
g3 <- graph.data.frame(df3, directed=F)
df4 <- data.frame(V1=c(1,1,2,3), V2=c(2,3,4,5))
g4 <- graph.data.frame(df4, directed=F)

get.edgelist(g1)
     [,1] [,2]
[1,] "1"  "3" 
[2,] "2"  "3" 
[3,] "2"  "4" 
[4,] "3"  "5" 
[5,] "4"  "5" 

get.edgelist(g2)
     [,1] [,2]
[1,] "1"  "3" 
[2,] "2"  "3" 
[3,] "2"  "5" 
[4,] "3"  "5" 
[5,] "4"  "5" 

get.edgelist(g3)
     [,1] [,2]
[1,] "1"  "3" 
[2,] "2"  "3" 
[3,] "3"  "5" 
[4,] "4"  "5" 

get.edgelist(g4)
     [,1] [,2]
[1,] "1"  "2" 
[2,] "1"  "3" 
[3,] "2"  "4" 
[4,] "3"  "5"

If I put all the graphs in a list:

mylist <- list(g1,g2,g3,g4)

And then apply the graph.intersection() function:

g.int <- graph.intersection(mylist, keep.all.vertices=FALSE)

The result is a graph with the following nodes and edges:

V(g.int)
[1] "1" "2" "3" "4" "5"

get.edgelist(g.int)
     [,1] [,2]
[1,] "3"  "5" 
[2,] "1"  "3"

What I want is to include those vertices and edges that appears in a certain percentage, in this example I would like to include edges present in 75% of the graphs. Thus, the optimal result would be:

V(g.int)
[1] "1" "2" "3" "4" "5"

get.edgelist(g.int)
     [,1] [,2]
[1,] "3"  "5" 
[2,] "1"  "3" 
[3,] "4"  "5"

Hope now it is more clear

user2380782
  • 1,542
  • 4
  • 22
  • 60
  • As written, this question is really broad and difficult to answer in the general case. Please provide a [reproducible example](http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example). Include some sample data as well as desired output. This would make your question much easier to answer. – MrFlick Sep 03 '14 at 14:15
  • Have you tried adding the adjacency matrices? – Will Beason Sep 03 '14 at 16:12
  • Not @WillBeason, maybe I should give it a try – user2380782 Sep 03 '14 at 16:31
  • Typed up as an answer. Should work on any list of graphs. – Will Beason Sep 03 '14 at 16:32

1 Answers1

1

You can create a graph of all of the edges in the graphs, then eliminate edges which do not appear often enough.

library(igraph)

# generate graphs
edgeset <- combn(1:20, 2)

graphs <- list()
for (i in 1:10) {
  graphs[[i]] <- graph(i + edgeset[, sample(ncol(edgeset), 150)])
}

# Get a list of all edges in all graphs
myedges <- lapply(graphs, get.edgelist)

# Make a graph of all of the edges including overlap
uniongraph <- graph(do.call(rbind, myedges))

# Eliminate edges not overlapped enough
resultgraph <- graph.adjacency(get.adjacency(uniongraph) >= 0.75 * length(graphs))
Will Beason
  • 3,417
  • 2
  • 28
  • 46