CODEWITHSUNDEEP
rigraph
topsyl
topsyl

Reputation: 53

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

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?

Upvotes: 1

Views: 579

Answers (1)

josliber
josliber

Reputation: 44309

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

  1. Create a node in the new graph for every edge in the original graph
  2. 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).

Upvotes: 2

Related Questions