Access data in nodes at distance of 2 or ancestors

User 52 | 12/31/2014, 12:26:49 PM

Using graphlab can i access the degree of the nodes at distance of 2 . One way is to run for two iterations and write GAS as required. Is there any example algo for this ?

Comments

User 940 | 12/31/2014, 7:51:54 PM

Hi kapilkumar,

You can compute the degree of nodes with <a href="http://graphlab.com/products/create/docs/generated/graphlab.SGraph.tripleapply.html#graphlab.SGraph.tripleapply">.triple_apply()</a>. There is an example of this here in the API docs.

After that you can get the neighborhood of your desired vertex with radius 2 with .<a href="http://graphlab.com/products/create/docs/generated/graphlab.SGraph.getneighborhood.html#graphlab.SGraph.getneighborhood">get_neighborhood()</a>.

This should return the sub-graph that you want, with each vertex containing a 'degree' attribute.

Does that help?

Cheers! -Piotr


User 52 | 1/4/2015, 10:22:06 PM

Thanks, Yes it was of great help. Can you please also tell me is there any way to count the number of paths of length 2 from a node to another .


User 954 | 1/5/2015, 10:55:15 PM

Hi kapilkumar,

If you want to compute all the paths of length 2 in a graph then join operation of graph edges SFrame by itself should solve your problem:

<pre class="CodeBlock"><code>g = gl.SGraph() edges = gl.SFrame({'source': range(9), 'dest': range(1,10)}) g = g.addedges(edges, srcfield='source', dstfield='dest') edgesframe = g.edges joinres = edges.join(edges,on={'dest':'source'}) joinres.num_rows()</code></pre>

Note that not only count, but it gives you all the paths with length two. if you only care about the number of paths with length 2, not the paths itself, then you can use <a href="http://graphlab.com/products/create/docs/generated/graphlab.SGraph.tripleapply.html#graphlab.SGraph.tripleapply">.triple_apply()</a> to compute degree of the vertices.

<pre class="CodeBlock"><code>def degreecountfn (src, edge, dst): src['degree'] += 1 dst['degree'] += 1 return (src, edge, dst) g = g.tripleapply(degreecountfn, mutatedfields=['degree'])</code></pre>

Then using degree information and SFrame <b class="Bold">Apply</b> and <b class="Bold">GroupBy</b> operators to compute paths length 2.

Note that if you have directed graph, then you need to calculate both 'in-degree' and 'out-degree' attributes of the vertices (in your triple_apply() function) instead of only 'degree' attribute.

I hope it helps.


User 52 | 1/6/2015, 10:02:10 AM

Hi Soroush,

Thanks for detailed reply. I am actually working on a problem for my research work.

I have a Bipartite graph which is very well connected . I have in this graph two types of vertices major and minor. There is no edge between major vertices and there is no edge between minor vertices. What i want to do is the following:

  1. I want to find the number of paths of length 2 between every pair of Major vertices.
  2. Degree of all the major vertices.

Remember i have a large number of vertices and edges.

Please suggest the most optimal way to do it.

Thanks, Kapil