Re: [igraph] Retrieve nodes forming a motif with subgraph_isomorphisms

[Phil Cui]

Hi Tamas,

I tried the ways as you suggested. It works. However, the speed is a bottleneck. So I come out a method to avoid checking motifs for my case. 

The oncoming questions are: what is the most efficient way to find the incident edges of the current edge? 

Here is my solution:

CurrentEdgeId <- get.edge.ids( g_OriginGraph, motif_current )   # motif_current is just an edge

IncidentEdges <- incident_edges( g_OriginGraph, motif_current )

IncidentEdgeIds <- unlist( IncidentEdges )

IncidentEdgeIds = IncidentEdgeIds[ IncidentEdgeIds != CurrentEdgeId ]

The above code can give the neighboring edges of the current edge. However, it is much slower than directly indexing the edge list of the graph:

        Edges <- as_edgelist( g_OriginGraph, FALSE )

        Motifs_left  <- rbind( Edges[Edges[,1] == motif_current[1],], Edges[Edges[,2] == motif_current[1],] )

        Motifs_right <- rbind( Edges[Edges[,1] == motif_current[2],], Edges[Edges[,2] == motif_current[2],] ) 

        NeighborMotifs <- rbind(Motifs_left, Motifs_right)

        idx <- which( NeighborMotifs[,1] == motif_current[1] & NeighborMotifs[,2] == motif_current[2] )

        NeighborMotifs <- NeighborMotifs[-idx,]

So I am wondering if there is some other functions from igraph to get the edges very fast.

Thanks a lot. 

Cheers,

Phil

___________________________________________________________

Phil Hengjun Cui

Drexel University | Electrical and Computer Engineering

Philadelphia, USA

___________________________________________________________

On Thu, Aug 6, 2015 at 5:24 PM, Tamas Nepusz <address@hidden> wrote:

On 08/04, Phil Cui wrote:
> (1) it gives motifs including those are the same type as g1 and also those are
> different types from g1 according to the result from
> isomorphism_class;
It could be the case that the issue is that you *expected* igraph to do
an induced subgraph isomorphism search. For instance, consider the following
pattern graph:

A --> B --> C

and the following target graph in which the pattern is being searched:

a --> b --> c --> a

igraph will happily return the mapping A=a, B=b, C=c as well as A=b, B=c, C=a
and A=c, B=a, C=b because the edges A --> B and B --> C can be mapped to some
edges of the target graph and the subgraph isomorphism algorithm does not aim
to map _nonexistent_ connections of the pattern graph to _nonexistent_
connections of the target graph. If you want to ensure that missing connections
between a pair of vertices in the pattern graph are mapped to missing
connections in the target graph, you need to use *induced* subgraph
isomorphism search.

subgraph_isomorphisms() in the R interface of igraph actually uses one of two
algorithms behind the scenes: VF2 or LAD. The LAD algorithm supports induced
subgraph isomorphisms, while VF2 does not, so if you want to search for
induced subgraph isomorphisms, you need to call subgraph_isomorphisms with
method="lad" and induced=T.

> (2) there are many duplicated combinations of nodes which relates to
> the same motif;
It can probably happen if the motif is isomorphic to itself -- in such cases,
multiple mappings may exist between the pattern and the target graph such that
the same nodes of the target graph are mappend to the pattern but in different
order.

> (3) the result provided is based on the vertex name, but I prefer vertex id.
> I tried unlist to get the ids, however, that will combine all
> everything together.
Just erase the vertex names temporarily before performing the search and add
them back later. (There could be a better solution for the problem in the
R interface but I'm not too familiar with R).

All the best,
T.

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help