Re: [igraph] Turn a directed network into a weighted undirected network

[Tamas Nepusz]

> for(i in 1:n){
> sbg.freq[i] <- graph.count.subisomorphisms.vf2(G, sbgCycle.graph[[i]])
> # graph.get.subisomorphisms.vf2(G, sbgCycle.graph[[i]])
> }
>
> I hope that 'i' in the brackets 'sbgCycle.graph[[i]])' corresponds to
> the the number of reciprocal edges.
No, it doesn't - it corresponds to the number of possible mappings
from the nodes of the subgraph to the nodes of the entire graph. For
instance, if you have a full graph with three nodes such that each
edge is present in both directions, it will contain the ordinary
directed cycle with three edges with six different possible mappings
(since you can start the cycle at any vertex and proceed in one of two
possible directions, so you get 3*2 = 6).

> My questions is: How to save a list of all directed cycles in the
> network G in order to to denote edge is involved in i-th type of  the
> 3-cycles?

> I have tried to type:
>> graph.get.subisomorphisms.vf2(G, sbgCycle.graph[[1]])[1]
> [[1]]
> + 3/5 vertices:
> [1] 1 2 3
> But I'm confused in the nodes labels (A, B, C) and IDs nodes (1,2,3).
get.subisomorphisms.vf2() will return a list of mappings from the
vertices of the template graph (the smaller one) to the vertices of
the full graph. For instance, in your case, the mapping "1 2 3" means
that vertex 1 of the template graph is mapped to vertex 1 of the full
graph, vertex 2 is mapped to vertex 2 and vertex 3 is mapped to vertex
3. If you have "2 1 3", this means that the first vertex of the
template graph is mapped to vertex 2 of the full graph, the second
vertex of the template graph is mapped to vertex 1 of the full graph,
and the third vertex is mapped to vertex 3. You don't have a mapping
for the edges, only for the vertices, because isomorphism maps the
vertices and the edge mapping just "follows" from this.

I would probably approach the problem from a different direction:

1. Convert the graph to undirected by dropping the arrowheads and
collapsing multiple edges into a single one first. (This is done with
to.undirected() and simplify()). Note that this operation keeps the
vertex IDs, i.e. vertex i in the converted graph will be the same as
the vertex IDs in the original graph.

2. Search for triangles in the undirected graph using, for instance,
get_subisomorphisms_vf2(). This still gives you vertex IDs only, but
then it is easier to map the vertex IDs to edge IDs using
get.edge.ids() because there could be at most one edge between any
pair of vertices (and not two, as in the directed case).

3. Search for subisomorphisms in the directed graph to all of the four
templates mentioned in the paper, but use
subgraph_isomorphisms(method="lad", induced=TRUE). The induced=TRUE
parameter ensures that the subisomorphism search looks for _induced_
subgraphs only, so a cycle of length 3 as a template will not be found
six times in a 3-recip subgraph (see the terminology on Fig 1 of the
paper). You also need method="lad" because VF2 does not support
induced=TRUE at the moment.

4. For each triangle in the undirected graph that you have found in
step 2 (and for which you now know the edge IDs in the undirected
graph since you used get.edge.ids() in step 2), check which template
graph it was isomorphic to according to the results of step 3 - this
will give you the weighting.

T.