Hello,
Thanks you for the advices, they proved really helpful. The line.graph
function does the trick. It is most likely not the best solution, but it
works sufficiently well for me.
Here is how I do it in R.
get.backtrack <- function(g){
n <- ecount(g)
g <- as.directed(g)
h <- line.graph(g)
P <- rbind(1:n,(n+1):(2*n))
P <- cbind(P,P[c(2,1),])
h <- h - edges(E(h,P))
get.adjacency(h)
}
I assume I have a simple undirected graph g and take the line-graph of its
directed counterpart. Then I remove the "backtracking paths". To do so, I
store them in a matrix P. The way I do it is not really clean, but it
works, most likely because of the way the directed graph is created from
the undirected one, and because of the way the line graph is created from
the original one. As I understood it, the node labels in the line-graph are
the edge numbers in the edgelist of the original graph. And when making a
directed graph of an originally undirected one, the new edges are stacked
in the same order as the original ones at the end of the edgelist.
Thanks agains,
Pierre-André
On 28 January 2014 14:20, Pierre-Andre Maugis <[email protected]> wrote:
> Hello,
>
> I am trying to build the non-backtracking matrix of a network. It is the
> matrix whose entries are indexed by the edges of the graph. Entries are 0
> if the said edges do not form a path of length two, and 1 if they do. More
> details can be found in arXiv:1306.5550, p3.
>
> All the algorithms I could produce are very slow. Computing the entries is
> not a problem, however storing them properly in the matrix is, and takes a
> lot of time.
>
> I would welcome any suggestion on the topic.
> Best,
> Pierre-André Maugis
>
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
