我有一个问题，看起来跟连接的子图问题很像，但实际上不属于严格的定义。
我面对的是一张拥有数百万个节点和链接的图（无法进行手动分析），其中有已知的2或3个“集合”。
每个“集合”由数十万个节点和成千上万个子图组成，这些子图不强连通。理论上，这些“集合”不应该相互连接...但是（估计）有几十个错误链接最终将它们连接起来。
问题在于找到这些集合和错误链接，或者至少得到一个人类可管理的错误链接候选列表，可以通过手动验证进行确认。
我的目前的“最佳想法”是随机选择两个节点，找到它们之间的最短路径，然后标记该最短路径上的链接。重复执行数百万次，错误链接最终会成为最多被标记的链接，因为它们是集合之间的“瓶颈”。
然而，这种方法相当缓慢，并且当一个集合比其他集合大得多并且具有内部瓶颈时，它会主导“最多被标记”的列表，使其毫无意义。
是否有更好的算法/方法来解决这个问题？
编辑：路径标记的改进是按路径长度成比例地标记，这有助于解决“大集合的内部瓶颈”问题，但并不完全消除它，因为某些集合可能具有远离的“异常值”，而其他集合具有许多紧密连接的节点（短内部距离）。
我面对的是一张拥有数百万个节点和链接的图（无法进行手动分析），其中有已知的2或3个“集合”。
每个“集合”由数十万个节点和成千上万个子图组成，这些子图不强连通。理论上，这些“集合”不应该相互连接...但是（估计）有几十个错误链接最终将它们连接起来。
问题在于找到这些集合和错误链接，或者至少得到一个人类可管理的错误链接候选列表，可以通过手动验证进行确认。
我的目前的“最佳想法”是随机选择两个节点，找到它们之间的最短路径，然后标记该最短路径上的链接。重复执行数百万次，错误链接最终会成为最多被标记的链接，因为它们是集合之间的“瓶颈”。
然而，这种方法相当缓慢，并且当一个集合比其他集合大得多并且具有内部瓶颈时，它会主导“最多被标记”的列表，使其毫无意义。
是否有更好的算法/方法来解决这个问题？
编辑：路径标记的改进是按路径长度成比例地标记，这有助于解决“大集合的内部瓶颈”问题，但并不完全消除它，因为某些集合可能具有远离的“异常值”，而其他集合具有许多紧密连接的节点（短内部距离）。
