Spark GraphX question.

[Tae-Hyuk Ahn <ah...@gmail.com>]

Hi All,

I am wondering what is the best way to remove transitive edges with maximum
spanning tree. For example,

Edges:
1 -> 2 (30)
2 -> 3 (30)
1 -> 3 (25)

where parenthesis is a weight for each edge.

Then, I'd like to get the reduced edges graph after "Transitive Reduction"
with considering the weight as a maximum spanning tree.

Edges:
1 -> 2 (30)
2 -> 3 (30)

Do you have a good idea for this?

Thanks,

Ted




--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Spark-GraphX-question-tp20768.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org

Re: Spark GraphX question.

[Tae-Hyuk Ahn <ah...@gmail.com>]

Thanks, Harihar. 

But this is slightly more complicate than just using subgraph(filter()). 

See the transitive reduction. 
http://en.wikipedia.org/wiki/Transitive_reduction

My case has one more additional requirement to think about weight (like a
maximum spanning tree).

Using a linear transitive reduction algorithm (and get some hints from
"TriangleCount.scale" in GraphX), it might have some steps as

1. Compute the set of neighbors for each vertex.
2. For each edge, compute the intersection of the sets and send the weight
to both vertices.
3. For each vertex, mark an edge as "False" if it has the intersection, but
lower weight.
4. Remove all "False" edges using subgraph.

But I am sure GraphX developer might have a better scalable and succinct
idea for this problem.

Thanks,

Ted



--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Spark-GraphX-question-tp20768p20777.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@spark.apache.org
For additional commands, e-mail: user-help@spark.apache.org

Re: Spark GraphX question.

[Harihar Nahak <hn...@wynyardgroup.com>]

Hi Ted,

I've no idea what is Transitive Reduction but the expected result you can
achieve by graph.subgraph(graph.edges.filter()) syntax and which filter
edges by its weight and give you new graph as per your condition.

On 19 December 2014 at 11:11, Tae-Hyuk Ahn [via Apache Spark User List] <
ml-node+s1001560n20768h72@n3.nabble.com> wrote:
>
> Hi All,
>
> I am wondering what is the best way to remove transitive edges with
> maximum spanning tree. For example,
>
> Edges:
> 1 -> 2 (30)
> 2 -> 3 (30)
> 1 -> 3 (25)
>
> where parenthesis is a weight for each edge.
>
> Then, I'd like to get the reduced edges graph after "Transitive Reduction"
> with considering the weight as a maximum spanning tree.
>
> Edges:
> 1 -> 2 (30)
> 2 -> 3 (30)
>
> Do you have a good idea for this?
>
> Thanks,
>
> Ted
>
>
> ------------------------------
>  If you reply to this email, your message will be added to the discussion
> below:
>
> http://apache-spark-user-list.1001560.n3.nabble.com/Spark-GraphX-question-tp20768.html
>  To start a new topic under Apache Spark User List, email
> ml-node+s1001560n1h95@n3.nabble.com
> To unsubscribe from Apache Spark User List, click here
> <http://apache-spark-user-list.1001560.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=1&code=aG5haGFrQHd5bnlhcmRncm91cC5jb218MXwtMTgxOTE5MTkyOQ==>
> .
> NAML
> <http://apache-spark-user-list.1001560.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>


-- 
Regards,
Harihar Nahak
BigData Developer
Wynyard
Email:hnahak@wynyardgroup.com | Extn: 8019




-----
--Harihar
--
View this message in context: http://apache-spark-user-list.1001560.n3.nabble.com/Spark-GraphX-question-tp20768p20771.html
Sent from the Apache Spark User List mailing list archive at Nabble.com.