Алгоритм для определения «нечетко связанных» подграфов

Question

У меня проблема, которая выглядит как проблема подграфов connectet с высоты мили, но совершенно отличается тем, что она не подпадает под строгие определения.

Я столкнулся с графиком с несколькими миллионами узлов и ссылок (ручной анализ невозможен), среди этих миллионов узлов, как известно, есть 2 или 3 «набора».

Каждый из «наборов» состоит из сотен тысяч единиц узлов и десятков тысяч этапов, не сильно связанных между собой. Каждый из этих наборов теоретически не должен быть связан с другими наборами ... но есть (gesstimation) десяток ошибочных ссылок, которые в конечном итоге соединяют эти множества.

Проблема заключается в том, чтобы найти эти наборы и ошибочные ссылки или, по крайней мере, получить список возможных кандидатов, которые могут быть проверены человеком, которые могут быть проверены вручную.

Моя текущая «лучшая идея» состоит в том, чтобы случайно выбрать два узла, найти кратчайший путь между ними, а затем пометить ссылки на этом кратчайшем пути. Rinse & повторяют миллионы раз, а ошибочные ссылки в конечном итоге оказываются как наиболее яркие, так как они «chokepoints» между наборами.

Однако это довольно медленно, и когда один набор намного больше других и имеет внутренние chokepoints, он становится доминирующим над «самым заметным» списком, что делает его бессмысленным.

Есть ли для этого лучшие алгоритмы/подходы?

редактировать: уточнением пути разметки является пометка пропорционально длиной пути, который помогает с «внутренними узкими местами большого набора» вопросом, но не полностью устраняет ее как некоторые наборы могут иметь удаленные «выбросы», в то время как другие наборы имеют множество тесно связанных узлов (короткие внутренние расстояния)

Answer 1

Моя идея ant colony algorithm. Я вдохновляюсь вашим подходом к выбору двух случайных узлов, но думал, что будет полезно сделать что-то большее, а не просто вычислить кратчайший путь.

Начать n муравьев в n случайных узлах. Вам нужно будет настроить n методом проб и ошибок. Муравьи оставляют феромон на пройденных краях. Феромон испаряется во времени. Муравьи выбирают один из различных ребер для перемещения в соответствии с вероятностью. Чем больше феромонов имеет край, тем вероятнее, что муравь будет выбирать этот край.

В начале муравьи перемещаются полностью случайным образом, поскольку феромоны и ребра не имеют такой же вероятности. Однако со временем самые популярные ребра, мосты между двумя «нечетко связанными» компонентами будут иметь на себе все больше и больше феромонов.

Итак, вы бросаете муравьев, имитируете для m поворотов и возвращаете края с наибольшим количеством феромонов на них. Вы можете визуализировать этот процесс, чтобы четко видеть, что происходит.

Update: я понял, что фраза «Однако, с течением времени, самые популярные края, мосты между двумя„нечетко связями“компоненты будут иметь все больше и больше феромона на них» неправильно. Я implemented это, и это выглядит как большая часть времени мостов не обязательно привлекают муравей:

Были п = 1000 муравьев и т = 1000 шагов.Первоначально у каждого края было 1 единица феромона, и он увеличивался на 1, если муравей пронесся над ним. Никакого испарения, однако я думаю, что это не улучшит ситуацию. Мост имел 49845 единиц феромонов, но было еще три края, которые имели более 100 тыс.

---

Как было предложено Peter de Rivaz в комментарии, я попытался (source code) повторение min-cut между 2 случайных узлов, и это намного лучше:

_{Графы генерироваться с python-igraph библиотекой.}