GraphX 带有一种用于查找图的连通分量的算法。
我没有找到有关其实现复杂性的声明。
通常，可以在线性时间内找到连接的组件，例如通过广度优先搜索或深度优先搜索（参见Wikipedia 文章）。但是，这假设您可以将图形保存在内存中。GraphX 实现了一种分布式的核外算法，所以我认为它没有可比性。
你知道他们的算法是如何工作的，复杂度是多少吗？
问问题
2392 次
2 回答
5
我认为图与非图解决方案的主要目标是减少解决问题所需的连续步骤的数量。这与复杂性不同——事实上，图形解决方案可能需要更多的 CPU 指令来执行，但如果它减少了连续步骤的数量，它仍然是正确的解决方案。
在寻找连通分量方面，广度优先和深度优先方法都具有相同数量的连续步骤——即图中顶点数量的一些倍数。必须将相同的逻辑顺序应用于每个顶点。这就是整个解决方案。
即使您的图表有两个或多或少相等大小的集群，您也不能将工作分成两个工作人员并从一端开始并在中间相遇。你不知道终点在哪里。你不知道中间在哪里。
如果你知道你所知道的结果，你的连续步骤总数可以减少到一半。如果它有帮助，您可以将其视为您在顺序步骤方面可以做到的理论上最好的。它完全取决于图表的形状。
如果你有很多独立的、未连接的集群，并且没有一个集群超过 10 人，那么理论上你可以做的最好的事情是 10 个连续的步骤。不管你有多少并行处理能力，你能做的最好的就是 10 个连续的步骤。
图算法不仅能让你更接近理论最小值——取决于你的集群的形状，它实际上会超过它。
那么 Spark 算法是如何工作的呢？这相当简单——每个节点只是将其广播VertexId给它的邻居，它的邻居也这样做。任何接收到VertexId比自己低的节点广播下一轮；如果不是，顶点会保持沉默。
如果你有一个集群，其中每个顶点都连接到其他每个顶点，那么在一轮消息之后，每个人都知道谁是最低的 VertexID，并且它们都在下一轮保持沉默。一个连续的步骤，整个集群。
另一方面，如果集群中的每个顶点只连接到最多 2 个其他顶点，那么在所有顶点知道最小值VertexID是多少之前，它可能需要 N 个连续的步骤。
显然，图算法中的顺序步骤具有不同的性质，甚至因图而异。连接良好的图将生成大量消息并花费更多时间合并它们等。但它不会像连接不佳的图那样需要那么多的顺序步骤。
长话短说，图解决方案的性能完全取决于图的形状，但它应该比广度优先或深度优先解决方案更好地并行化。
于 2016-04-29T18:59:02.123 回答
0
这可能不是您问题的直接答案，但 GraphX 连接的组件不适合我。我在 Spark 上使用 map/reduce 实现了连接组件。您可以在此处找到更多详细信息 - https://www.linkedin.com/pulse/connected-component-using-map-reduce-apache-spark-shirish-kumar和 MIT 许可下的源代码 - https://github .com/kwartile/connected-component。
于 2019-07-03T05:03:57.723 回答