[jira] [Commented] (SPARK-17383) improvement LabelPropagation of graphx lib

["ASF GitHub Bot (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/SPARK-17383?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16724154#comment-16724154 ] 

ASF GitHub Bot commented on SPARK-17383:
----------------------------------------

srowen closed pull request #14940: [SPARK-17383][GRAPHX] Improvement LabelPropagaton, and reduce label shake and disconnection of communities
URL: https://github.com/apache/spark/pull/14940
 
 
   

This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:

As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):

diff --git a/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala b/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
index fc7547a2c7c27..31a9414ae47ca 100644
--- a/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
+++ b/graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala
@@ -58,7 +58,7 @@ object LabelPropagation {
       }.toMap
     }
     def vertexProgram(vid: VertexId, attr: Long, message: Map[VertexId, Long]): VertexId = {
-      if (message.isEmpty) attr else message.maxBy(_._2)._1
+      (Map(attr -> 1L) ++ message).maxBy(m => (m._2, m._1))._1
     }
     val initialMessage = Map[VertexId, Long]()
     Pregel(lpaGraph, initialMessage, maxIterations = maxSteps)(


 

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


> improvement LabelPropagation of graphx lib
> ------------------------------------------
>
>                 Key: SPARK-17383
>                 URL: https://issues.apache.org/jira/browse/SPARK-17383
>             Project: Spark
>          Issue Type: Improvement
>          Components: GraphX
>    Affects Versions: 2.1.0
>            Reporter: XiaoSen Lee
>            Priority: Major
>
> In the labelPropagation of graphx lib, node is initialized with a unique
> label and at every step each node adopts the label that most of its neighbors currently have, but ignore the label it currently have. I think it is unreasonable, because the labe a node had is also useful. When a node trend to has a stable label, this means there is an association between two iterations, so a node not only affected by its neighbors, but also its current label.
> so I change the code, and use both the label of its neighbors and itself.
> This iterative process densely connected groups of nodes form a consensus on a unique label to form
> communities. But the communities of the LabelPropagation often discontinuous.
> Because when the label that most of its neighbors currents have are many,e.g, node "0" has 6 neigbors labed {"1","1","2","2","3","3"},it maybe randomly select a label. in order to get a stable label of communities, and prevent the randomness, so I chose the max lable of node.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

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