Создание графика из заводских данных журнала

Question

Я хочу обобщить график, который я создал из данных заводского журнала.

В необработанном виде график содержит 234 узла (действие, которое может выполнить робот) и около 4 миллионов ребер (поток данных журнала: робот 1 выполняет действие 1 в 23:45:32 -> Робот 23 выполняет действие 334 в 23:45:33).

Я создал график в Networkx как Weighted DiGraph (вес - это число раз, когда произошел переход, например, из действия 1 -> действие 334) и визуализировал его в Gephi, чтобы вы могли видетькак это выглядит (см. изображение).

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

Я хочу найти пути, которые ведут к этим узлам:

Однако, когдая проверяю nx.is_tree (G), is_directed_acyclic_graph (G) или что-то еще, все они возвращают false.Поэтому мой первый вопрос: какой график я здесь смотрю?Это какой-то особый случай?Потому что я не могу найти правильный термин для этого.

Мой второй вопрос: каковы некоторые стратегии автоматического поиска путей к этим важным узлам.Например, некоторые из конечных узлов являются ошибками.Было бы здорово узнать, какая цепочка / путь / трасса узлов / ребер чаще всего приводит к этим ошибкам.

Заранее спасибо за ваши предложения!

Answer 1

Это ориентированный граф.Пока в вашем графе есть путь от одного узла к себе, у него есть циклы.Так что это не ациклично.

В вашем случае один и тот же робот может выполнять одно и то же действие более одного раза, поэтому ясно, что цикл существует.Даже если один робот выполнил действие 1 и затем 2, другой выполнил действие 2, а затем 3, а еще один выполнил действие 3, а затем 2, у вас все равно будет цикл.Кроме того, если бы не было цикла, то в конечном итоге у каждого робота заканчивались возможные задачи (потому что они не могли повторяться).На самом деле, в вашем графе были бы определенные действия, такие, что когда робот их выполняет, он больше ничего не делает.

Этот график - просто взвешенный ориентированный граф.

ПростейшийМера важных узлов является их частота.В вашем случае это будет сумма их весовых коэффициентов или сумма их весовых коэффициентов (которые должны быть равны, вплоть до поправки, для узлов которой выполняются первые / последние действия, выполняемые роботом в вашем наборе данных).

Существуют и другие "центральные" меры.Вы можете найти многие из них в документации .Тот факт, что ваш график направлен и взвешен, может повлиять на то, была ли реализована мера централизованности для сети (проверьте детали документации и учтите, что если вы явно не скажете ему использовать веса ребер, он будет обрабатыватьграфик как невзвешенный).

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