How to computer new edge weight when converting vertices to edges using line.graph (igraph) in R?

Question

I am trying to convert edges to nodes using line.graph. My first graph has weights for each edge, I am trying to get weights on the egdes for the new graph in the following way -

First Graph -

1-------(0.7)-----2-----(0.5)-----3

New Graph -

1,2-------(0.35)--------2,3

So, the vertices of first graph is 1,2 and 3. Edge weight for 1-2 is 0.7 and for 2-3 is 0.5. In the new graph I have vertices (1,2) and (2,3) and the edge connecting them has weight 0.35 i.e the multiplication of the edge weights (0.7 * 0.5).

How can I do this in igraph?

Can you clarify your algorithm? Suppose you had 1-------(0.7)-----2-----(0.5)-----3-----(0.2)-----4 how many times would you aggregate your edges and what would this graph end up looking like? — Tim Biegeleisen
So for this case my graph would look like - 1,2------(0.35)------2,3-----(0.1)-----3,4 Basically, it is just converting the edges to nodes, where the edges are ending. — topsyl
This is called a Line graph: en.wikipedia.org/wiki/Line_graph — Gabor Csardi

josliber josliber · Accepted Answer · 2015-03-06T06:31:30

Basically, I would summarize your algorithm for computing a new graph as:

Create a node in the new graph for every edge in the original graph
If a pair of nodes in the new graph shared a node in the original graph (aka they are mapped to adjacent edges in the original graph), add an edge between them of weight equal to the product of the mapped edge weights.

The approach I would take to this would be to loop through the nodes in the original graph, adding an edge to the new graph for each pair edges adjacent to that node:

# Sample graph (from comments on original question)
library(igraph)
g <- graph.data.frame(data.frame(x=1:3, y=2:4, weight=c(0.7, 0.5, 0.2)))

# Build new graph from edge list
g.edges <- get.edges(g, E(g))
enames <- paste(g.edges[,1], g.edges[,2], sep=",")
ewts <- E(g)$weight
(new.edges <- do.call(rbind, sapply(1:vcount(g), function(x) {
  incident <- which(g.edges[,1] == x | g.edges[,2] == x)
  if (length(incident) <= 1) {
    return(NULL)
  } else {
    all.comb <- combn(incident, 2)
    return(data.frame(x=enames[all.comb[1,]], y=enames[all.comb[2,]], weight=apply(all.comb, 2, function(x) prod(ewts[x]))))
  }
})))
#     x   y weight
# 1 1,2 2,3   0.35
# 2 2,3 3,4   0.10

You can build the new graph with graph.data.frame(new.edges).

How to computer new edge weight when converting vertices to edges using line.graph (igraph) in R?

1 Answers