Обнаружение необычных шаблонов траекторий в гигантском ориентированном графе

Question

У меня есть гигантский ориентированный граф (100 М + узлов) узлов, с несколькими экземплярами экземпляров пути между наборами узлов. путь между любыми двумя узлами может меняться, но то, что я хотел бы найти, - это пути, которые разделяют несколько промежуточных узлов , за исключением для значительного отклонения.

Например, у меня есть 10 экземпляров пути между узлом A и узлом H. Девять из этих десяти экземпляров пути перемещаются через узлы c, d, e, f - но один из экземпляров проходит через c, d, z , e, f - Я хочу найти этот «нечетный» экземпляр.

Любые идеи, как я даже начну подходить к такой проблеме? Существующие аналитические рамки, которые могут подойти к задаче?

Детали на основе комментариев:

• Пир (путь экземпляр запись) представляет собой список узлов путешествовали через с ассоциированным временем прохождения границы на край.
• В настоящее время необработанные записи PIR находятся в формате простой строки - очевидно, я хотел бы сохранить его по-другому в зависимости от того, как я в конечном итоге решит его проанализировать.
• Это не маршрут решение проблема - мне больше не нужно будет найти paths; Мне нужно только проанализировать принятых путей (каждый из которых является PIR).
• Список подпапок должен быть сгенерирован из PIR.

Примером PIR будет что-то вроде: ; 300 узла А; NodeB; 600; 100; nodeC; кивал; 100; nodeF

Это приводит к пути А-> BC-> D-> F; стоимость/время каждой вершины - это число - например, стоить 300, чтобы перейти от A-> B, 600, чтобы перейти от B-> C и 100, чтобы перейти от D-> F. Стоимость/время каждого обхода будет отличаться при каждом обходе. Так, например, в одном ПИРе может стоить 100, чтобы перейти от A-> B, но в следующем он может стоить 150, чтобы перейти от A-> B.

Answer 1

Перейдите по списку путей и разбейте их на группы, основанные на начальном и конечном узлах. Так, например, все пути, начинающиеся с узла A и заканчивающиеся узлом B, находятся в одном наборе. Затем вы можете сделать то же самое с подпоследовательностями этих путей. Так, например, каждый путь с подпоследовательностью a, b, c, d и начальным узлом y и конечным узлом k находятся в одном наборе. Также обратные пути по мере необходимости, чтобы, например, у вас не было набора для путей k к y и набора для путей y к k. Затем вы можете проверить, достаточно ли подпоследовательности, за которым следует проверка того, есть ли путь (ы), который не имеет этой подпоследовательности, если есть подпоследовательность внутри этого пути, которая достаточно близка к исходной последовательности на основе edit distance. Если вас интересует только путь, вы можете просто вычислить расстояние редактирования пути и подпоследовательности, вычесть разницу в длине и проверить, является ли результат достаточно низким. Вероятно, лучше всего использовать подпоследовательность пути, чтобы он начинался и заканчивался тем же узлом, что и искомая подпоследовательность.

Для вашего примера алгоритм в конечном итоге достигнет набора путей, содержащих подпоследовательность c, d, e, f, и найдет, что их 9. Это превышает количество, необходимое для того, чтобы подпоследовательность была достаточно распространенной (и достаточно долго, возможно, нуждалась в последовательностях по меньшей мере длины k), тогда она проверила бы пути, которые не включены. В этом случае есть только один. Затем было бы прямо или косвенно отмечено, что только удаление z будет делать последовательность c, d, z, e, f в c, d, e, f.Это передает (в настоящее время неопределенные) требования для «нечетных», и поэтому путь, содержащий c, d, z, e, f, добавляется в список возвращаемых путей.