Re: [igraph] Non-Backtracking Matrix

[Tamás Nepusz]

Hello,  

> 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.
Yes, that’s true, it works this way at the moment, but it is not guaranteed in 
general. We might change it in a later version of igraph and then your code 
would break, but it’s unlikely that we’ll do this. Anyway, probably a better 
way would be to find the mutual edge pairs in the directed graph (using 
is.mutual) and for every mutual edge pair (i, j), you should remove (i, j) and 
(j, i) from the line graph. I’m not sure how to do that efficiently in R. 
get.edgelist(graph)[is.mutual(graph), ] gives you the edges that exist in both 
directions, so that could be a good starting point, but I don’t see immediately 
what would be the most efficient way to proceed; maybe Gabor can comment on 
that.

An alternative way is to do the same thing what line.graph does while also 
filtering the backtracking paths at the same time. Essentially, line.graph 
iterates over the vertices, and for each vertex, it takes the incoming edges 
and the outgoing edges and creates every possible pair between an incoming edge 
and an outgoing edge. Constructing these edge pairs manually and excluding 
backtracking pairs before they are added to the line graph (or its edge list) 
is also an option. You could use get.adjedgelist(mode=“in”) to get a list of 
incoming edge indices for each vertex, and get.adjedgelist(mode=“out”) to get a 
list of outgoing edge indices for each vertex, and then it’s only a matter of 
looping and constructing the edge list of the line graph.

All the best,
T.