[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Loop detection in a directed network

From: Gábor Csárdi
Subject: Re: [igraph] Loop detection in a directed network
Date: Sat, 13 Jul 2013 10:31:12 -0400


some ideas. 

is.dag() (in R) tells you whether there are loops at all. But probably you know that there are some.

Start graph.dfs() from a vertex with in-degree 0, and then look at the DFS order of vertices, and look for edges that are pointing backwards according to the DFS order. I believe that these must signal loops.

Alternatively, calculate the strongly connected components of the graphs. All vertices of a loop belong to the same strongly connected component. Also, each non-trivial strongly connected component must contain at least one directed loop. This is also a way to parallelize the problem, because you can just work with the individual strongly connected components.

I cannot say for sure that these methods work for your graph, so try on a smaller (snowball) sample first, and see how your solution scales with the number of edges and vertices.


On Sat, Jul 13, 2013 at 10:02 AM, FARKAS, Illes <address@hidden> wrote:

What tool would you recommend to detect the loops in a directed network with 5M nodes and 110M directed links? I think that the number of loops of length n decays at least exponentially with n.


igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]