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 > > [email protected] (mailto:[email protected]) > > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > > _______________________________________________ > igraph-help mailing list > [email protected] (mailto:[email protected]) > https://lists.nongnu.org/mailman/listinfo/igraph-help _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
