{"id":525,"date":"2015-11-10T10:12:50","date_gmt":"2015-11-10T09:12:50","guid":{"rendered":"https:\/\/iww.inria.fr\/sed-sophia\/?p=525"},"modified":"2015-11-10T11:10:04","modified_gmt":"2015-11-10T10:10:04","slug":"graph-connected-component-analysis-with-bulk-synchronous-parallel-processing","status":"publish","type":"post","link":"https:\/\/iww.inria.fr\/sed-sophia\/graph-connected-component-analysis-with-bulk-synchronous-parallel-processing\/","title":{"rendered":"Graph Connected Component Analysis with Bulk-Synchronous-Parallel Processing"},"content":{"rendered":"<p>In an undirected graph, a connected component is a subgraph in which any two vertices are connected to each other by paths. Usual algorithms build a graph where each vertex is labeled with its component number. They use a search from an unclassified vertex to build the connected component containing this vertex. The process repeats until all vertices are labeled with a component. Vertices that are not connected form a component with only one vertex.<br \/>\n<!--more--><br \/>\nIn an <a href=\"https:\/\/iww.inria.fr\/sed-sophia\/the-bulk-synchronous-parallel-model-for-graph-processing\/\" target=\"_blank\">edge-centric BSP<\/a> implementation, like <a href=\"https:\/\/spark.apache.org\/graphx\/\" target=\"_blank\">GraphX<\/a>, finding all the connected components is done in parallel using Pregel iterations:<\/p>\n<pre>\/\/<em> working copy of the input graph, set label of vertices to their vertex Id<\/em>\r\nval cGraph : Graph[ Int, ED ] = graph.mapVertices(\r\n        (vid, attr) =&gt; vid )\r\n\r\ncGraph.pregel[ Long ](initialMsg = Long.MaxValue) (\r\n    \/\/ <em>vertex program<\/em>\r\n    (vid : VertexId, attr : Long, msg : Long) =&gt; Math.min(msg, attr),\r\n    \/\/ <em>sendMsg: send to vertex the min of component label along the edges<\/em>\r\n    (edgeT : EdgeTriplet[Long, ED]) =&gt;\r\n        if (edgeT.srcAttr &lt; edgeT.dstAttr)\r\n            Iterator( (edgeT.dstId, edgeT.srcAttr) )\r\n        else if (edgeT.dstAttr &lt; edgeT.srcAttr)\r\n            Iterator( (edgeT.srcId, edgeT.dstAttr) )\r\n        else\r\n            Iterator.empty,\r\n    \/\/ <em>mergeMsg<\/em>\r\n    Math.min(_, _) )\r\n<\/pre>\n<p>This algorithm will build a graph where each vertex is labeled with the lowest vertex Id of the connected component that contains this vertex. The vertex program is a function called each time a vertex receives a message, in this case a Long number which is the component Id of one of its neighbor. The <code>sendMsg<\/code> function processes an edge and propagate the minimum of the vertex attribute of one vertex to the other vertex, and finally messages are merged with the <code>min()<\/code> binary function.<\/p>","protected":false},"excerpt":{"rendered":"<p>In an undirected graph, a connected component is a subgraph in which any two vertices are connected to each other by paths. Usual algorithms build a graph where each vertex is labeled with its component number. They use a search from an unclassified vertex to build the connected component containing\u2026<\/p>\n<p> <a class=\"continue-reading-link\" href=\"https:\/\/iww.inria.fr\/sed-sophia\/graph-connected-component-analysis-with-bulk-synchronous-parallel-processing\/\"><span>Continue reading<\/span><i class=\"crycon-right-dir\"><\/i><\/a> <\/p>\n","protected":false},"author":824,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","_members_access_role":[],"_members_access_error":""},"categories":[29],"tags":[],"class_list":["post-525","post","type-post","status-publish","format-standard","hentry","category-development-in-the-inria-teams"],"_links":{"self":[{"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/posts\/525","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/users\/824"}],"replies":[{"embeddable":true,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/comments?post=525"}],"version-history":[{"count":9,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/posts\/525\/revisions"}],"predecessor-version":[{"id":559,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/posts\/525\/revisions\/559"}],"wp:attachment":[{"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/media?parent=525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/categories?post=525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iww.inria.fr\/sed-sophia\/wp-json\/wp\/v2\/tags?post=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}