Spark：GraphX 中使用的连通分量算法的时间复杂度是多少？
Spark: What is the time complexity of the connected components algorithm used in GraphX?
GraphX 带有一个 algorithm for finding connected components 的图表。
我没有找到关于其实施复杂性的声明。
通常，查找连通分量可以在线性时间内完成，例如通过广度优先搜索或深度优先搜索（参见 Wikipedia article）。但是，这假设您可以将图形保存在内存中。 GraphX 实现了一个分布式的、核外的算法，所以我假设它没有可比性。
你知道他们的算法是怎么工作的，有什么复杂度吗？
我认为图与非图解决方案的主要目标是减少解决问题所需的连续步骤数。这与复杂性不同——事实上，Graph 解决方案可能需要执行更多 CPU 指令，但如果它减少顺序步骤的数量，仍然是正确的解决方案。
就查找连通分量而言，广度优先和深度优先方法都具有相同数量的顺序步骤——即图中顶点数量的一些倍数。相同的逻辑必须按顺序应用于每个顶点。这就是整个解决方案。
即使您的图表有两个或多或少大小相等的集群，您也不能将工作分成两个工作人员并从一端开始并在中间相遇。你不知道尽头在哪里。你不知道中间在哪里。
如果你知进知出，你的顺序步骤总数可以减少一半。如果有帮助，您可以将其视为您在连续步骤方面可以做到的理论上最好的。它完全取决于你的图表的形状。
如果你有很多独立的集群，没有连接，并且没有集群超过 10 人，那么理论上你可以做的最好的是 10 个连续的步骤。无论您拥有多少并行处理能力，您最多只能执行 10 个连续步骤。
图形算法不仅能让您更接近理论最小值 -- 根据集群的形状，它实际上可以击败它。
那么Spark算法是如何工作的呢？这相当简单——每个节点只是将其 VertexId 广播给它的邻居，它的邻居也这样做。任何节点收到比自己低的 VertexId 就广播下一轮；否则 Vertex 会静音。
如果你有一个集群，其中每个顶点都连接到每个其他顶点，那么在一轮消息之后，每个人都知道谁是最低的 VertexID，并且他们在下一轮都保持沉默。一个连续的步骤，整个集群。
另一方面，如果集群中的每个顶点最多只连接到其他 2 个顶点，那么在所有顶点知道最小 VertexID 是多少之前，它可能需要 N 个连续步骤。
显然，图算法中的顺序步骤具有不同的性质，甚至在图与图之间也不同。连接良好的图会生成大量消息并花费更多时间合并它们等。但它不会像连接不太好的图那样需要那么多顺序步骤。
长话短说，图形解决方案的性能完全取决于图形的形状，但它应该比广度优先或深度优先的解决方案并行化好得多。
这可能不是您问题的直接答案，但 GraphX 连接组件不适合我。我在 Spark 上使用 map/reduce 实现了连接组件。您可以在此处找到更多详细信息 - https://www.linkedin.com/pulse/connected-component-using-map-reduce-apache-spark-shirish-kumar and the source code under MIT license here - https://github.com/kwartile/connected-component.
GraphX 带有一个 algorithm for finding connected components 的图表。
我没有找到关于其实施复杂性的声明。
通常，查找连通分量可以在线性时间内完成，例如通过广度优先搜索或深度优先搜索（参见 Wikipedia article）。但是，这假设您可以将图形保存在内存中。 GraphX 实现了一个分布式的、核外的算法，所以我假设它没有可比性。
你知道他们的算法是怎么工作的，有什么复杂度吗？
我认为图与非图解决方案的主要目标是减少解决问题所需的连续步骤数。这与复杂性不同——事实上，Graph 解决方案可能需要执行更多 CPU 指令，但如果它减少顺序步骤的数量，仍然是正确的解决方案。
就查找连通分量而言，广度优先和深度优先方法都具有相同数量的顺序步骤——即图中顶点数量的一些倍数。相同的逻辑必须按顺序应用于每个顶点。这就是整个解决方案。
即使您的图表有两个或多或少大小相等的集群，您也不能将工作分成两个工作人员并从一端开始并在中间相遇。你不知道尽头在哪里。你不知道中间在哪里。
如果你知进知出，你的顺序步骤总数可以减少一半。如果有帮助，您可以将其视为您在连续步骤方面可以做到的理论上最好的。它完全取决于你的图表的形状。
如果你有很多独立的集群，没有连接，并且没有集群超过 10 人，那么理论上你可以做的最好的是 10 个连续的步骤。无论您拥有多少并行处理能力，您最多只能执行 10 个连续步骤。
图形算法不仅能让您更接近理论最小值 -- 根据集群的形状，它实际上可以击败它。
那么Spark算法是如何工作的呢？这相当简单——每个节点只是将其 VertexId 广播给它的邻居，它的邻居也这样做。任何节点收到比自己低的 VertexId 就广播下一轮；否则 Vertex 会静音。
如果你有一个集群，其中每个顶点都连接到每个其他顶点，那么在一轮消息之后，每个人都知道谁是最低的 VertexID，并且他们在下一轮都保持沉默。一个连续的步骤，整个集群。
另一方面，如果集群中的每个顶点最多只连接到其他 2 个顶点，那么在所有顶点知道最小 VertexID 是多少之前，它可能需要 N 个连续步骤。
显然，图算法中的顺序步骤具有不同的性质，甚至在图与图之间也不同。连接良好的图会生成大量消息并花费更多时间合并它们等。但它不会像连接不太好的图那样需要那么多顺序步骤。
长话短说，图形解决方案的性能完全取决于图形的形状，但它应该比广度优先或深度优先的解决方案并行化好得多。
这可能不是您问题的直接答案，但 GraphX 连接组件不适合我。我在 Spark 上使用 map/reduce 实现了连接组件。您可以在此处找到更多详细信息 - https://www.linkedin.com/pulse/connected-component-using-map-reduce-apache-spark-shirish-kumar and the source code under MIT license here - https://github.com/kwartile/connected-component.