识别"模糊连接"子图的算法
我有一个问题,看起来像一英里高的connectet子图问题,但是非常明显,因为它不属于严格的定义.
我面对的是一个包含数百万个节点和链接的图表(手动分析是不可能的),在这些数百万个节点中,已知有2或3个"集合".
每个"集合"由数万分之一的节点和数万分之一的子图组成,没有强连接.这些集合中的每一个理论上都不应该与其他集合相关联......但是(猜测)有十几个错误的链接最终连接这些集合.
问题是要找到那些集合和错误的链接,或者至少得到一个人工可管理的错误链接候选列表,可以手动验证.
我目前的"最好的想法"是随机选择两个节点,找到它们之间的最短路径,然后在最短路径上标记链接.冲洗和重复数百万次,错误的链接最终成为最明显的链接,因为它们是集合之间的"阻塞点".
然而,这是非常缓慢的,并且当一组比其他组大得多且具有内部阻塞点时,它最终占据"最显着"的列表,使其变得毫无意义.
那有更好的算法/方法吗？
编辑:路径标记的细化是与路径的长度成比例地标记,这有助于"大集合的内部阻塞点"问题,但并不完全消除它,因为一些集合可能具有远距离的"异常值",而其他组有很多紧密连接的节点(内部距离短)
我的想法是蚁群算法。我从你选择两个随机节点的方法中得到启发，但认为做更多的事情而不是仅仅计算最短路径会很有用。
在n个随机节点中启动n只蚂蚁。您需要通过试错法来调整 n。蚂蚁在走过的边缘留下信息素。信息素及时蒸发。蚂蚁根据概率选择不同的边之一进行旅行。边缘的信息素越多，蚂蚁选择该边缘的可能性就越大。
一开始，蚂蚁的移动完全是随机的，因为没有信息素，而且边缘具有相同的概率。然而，随着时间的推移，两个“模糊连接”组件之间最流行的边缘、桥梁上将有越来越多的信息素。
因此，您扔了 n 只蚂蚁，模拟 m 圈，然后返回信息素含量最高的边缘。您可以将这个过程可视化，清楚地看到发生了什么。
更新：我意识到这句话“然而，随着时间的推移，两个“模糊连接”组件之间最流行的边缘、桥梁将有越来越多的信息素”是错误的。我实现了它，看起来大多数时候桥梁不一定会吸引蚂蚁：
有 n = 1000 只蚂蚁，m = 1000 步。最初，每条边都有 1 个单位的信息素，如果蚂蚁走过它，信息素就会增加 1。没有蒸发，但我认为这不会改善情况。Bridge 有 49845 个信息素单位，但其他三个边的信息素数量超过 100k。
正如Peter de Rivaz在评论中所建议的，我尝试（源代码）在 2 个随机节点之间重复min-cut，效果要好得多：
使用python-igraph库生成的图。