igraph-help
[Top][All Lists]

## Re: [igraph] Non-Backtracking Matrix

 From: Tamás Nepusz Subject: Re: [igraph] Non-Backtracking Matrix Date: Thu, 30 Jan 2014 16:43:21 +0100

```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.

```