Re: [igraph] How to make read.graph and maximal.clique faster in R?

[Tamás Nepusz]

Hi,  

There is nothing you can do to make read.graph() and maximal.cliques() faster; 
this is as good as it gets. However, note that you don’t need maximal.cliques() 
to achieve your goal. Essentially, you are looking for the set of edges that 
participate in triangles. A far easier (and faster) way of doing this is to 
iterate over the edges one by one and check whether the two endpoints of the 
edge have at least one common neighbor.

I would probably do the following:

1) Construct the adjacency list represetation of the graph using get.adjlist(); 
this gives you a list of sorted lists where each entry contains the neighbors 
of a node.

2) For each edge that goes from vertex i to j, check the i-th and j-th entries 
of the adjacency list using R’s intersect() function. If the intersection is 
non-empty, then the edge i-j participates in a triangle.

I have no serious coding experience in R so I won’t attempt to give you code 
for this, but I did the same in Python and I managed to process your graph in 
35 seconds plus the time it took to read the graph.

For what it’s worth, the above works only if there are no loop edges in your 
graph. If there are, use simplify() to get rid of them before you start 
searching for the triangles.  

--  
T.


On Monday, 17 February 2014 at 05:22, Mona Jalal wrote:

> My code didn't come here properly. Here's the code:
>  
> http://stackoverflow.com/questions/21818697/dealing-with-large-matrix-graphs-in-r-how-to-make-the-operations-in-igraph-fast
>  
>  
> Sorry about that,
> Mona.
>  
> On 02/16/14, Mona Jalal wrote:
> > Hi,
> >  
> > Is there anyway to make the following code work faster? It really takes 
> > till forever and it gets stuck in finding the edges that belong to a 
> > triangle in a large graph.
> >  
> >  
> > I am reading "cit-Patents.txt" from the following link: 
> > https://snap.stanford.edu/data/cit-Patents.txt.gz
> >  
> > library(igraph) #xlist<-read.table("cit-Patents.txt") 
> > read.graph_xlist<-read.graph("cit-Patents.txt", 
> > format="edgelist",directed=TRUE) #xlist <- graph.data.frame(xlist) ij <- 
> > get.edgelist(read.graph_xlist) library(Matrix) m <- sparseMatrix( i = 
> > rep(seq(nrow(ij)), each=2), j = as.vector(t(ij)), x = 1 ) cl <- 
> > maximal.cliques(read.graph_xlist) cl <- cl[ sapply(cl, length) > 2 ] 
> > print(cl) # Function to test if an edge is part of a triangle triangle <- 
> > function(e) { any( sapply( cl, function(u) all( e %in% u ) ) ) } 
> > print(triangle) # Only keep those edges kl <- ij[ apply(ij, 1, triangle), ] 
> > print(kl) # Same code as before m <- sparseMatrix( i = rep(seq(nrow(kl)), 
> > each=2), j = as.vector(t(kl)), x = 1 )
> >  
> >  
> >  
> >  
> > Thanks,
> >  
> > Mona.
> >  
> > _______________________________________________
> > igraph-help mailing list
> > address@hidden (mailto:address@hidden)
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>  
>  
>  
> _______________________________________________
> igraph-help mailing list
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help