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

[Phil Cui]

Hi Tamas,

Thank you very much for your suggestion.

I tried make_line_graph according to your suggestion. And it works very well for small scale graph.

However, when the graph include millions of nodes, it becomes hard to create a complete line graph.

I tried very hard based on current functions in igraph package, considering sampling the motifs is slightly different than the usual random walk since it requires checking the motif type during the random walk, so it takes long to finish the whole process, mostly because the transition from edge to node or node to edge, as I listed in the former email. The random walk actually doesn't take long, however, those functions called to converting edge to node before checking the motif type really slows down the motif sampling process.

So I am thinking if I can delve into the C code (https://github.com/igraph/igraph/blob/master/src/random_walk.c) and work based on the current random_walk function and create a revised version of that to sample the motifs with size 2.The proposed function will return two vectors with the type igraph_vector_t. Each vector stores one of the ends of the sampled edge. In that way, I can first finish the sampling procedure with the sampled edges acquired and without creating a complete motif graph. Then I can check the motif type with the help of isomorphism_class by accessing the neighboring two pair of nodes returned by the random_motif_sampling function.

I already come out a draft version of that, but I don't know how to test it. My plan is to fork the igraph package to my local computer through Github and then test it on my side so that it won't affect the original package in case I make some mistake. The problem I encounter now is: how to embed my code to the igraph package so that I can test the code.

Thanks a lot for your always kind help.

Best regards,

Phil

___________________________________________________________

Phil Hengjun Cui

Drexel University | Electrical and Computer Engineering

Philadelphia, USA

___________________________________________________________

On Mon, Aug 10, 2015 at 5:18 AM, Tamas Nepusz <address@hidden> wrote:

> The oncoming questions are: what is the most efficient way to find the
> incident edges of the current edge?
If your graph is relatively small and you are going to perform this type of
query many times, the easiest it to create the line graph of the graph and then
use neighbors() on the line graph. This works because every vertex of the line
graph corresponds to the edge with the same index in the original graph, and
two vertices in the line graph are connected if the corresponding edges share
a vertex in the original graph. So, something like:

g_LineGraph <- line.graph(g_OriginGraph)
IncidentEdgeIds <- neighbors(g_LineGraph, CurrentEdgeId)

You can basically consider the line graph as an efficient data structure that
pre-computes and lists all edges incident on a specific edge in the original
graph.

T.

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