Re: [igraph] Non-Backtracking Matrix

[Pierre-Andre Maugis]

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 <address@hidden> 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