Как судить о силе ориентированного ациклического графа?

Question

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

(если график не отображается, нажмите здесь или перейдите по этой ссылке: http://www.flickr.com/photos/86396568@N00/2893003041/

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

Вот подходы, которые я рассмотрел до сих пор для оценки силы узла:

1) Подсчет количества узлов ниже, вычитая количество узлов выше.

• A = 7, a = 7, B = 5, b = 1

2) Подсчет количества полных путей (до завершения) для каждого узла, суммирование их длин.

• A = 17 (1 + 5 + 5 + 5 + 1), B = 12 (4 + 4 + 4), a = 9 (3 + 3 + 3), b = 2
• Это делает ходуля сильнее, чем стебель.

3) Подсчет каждого возможного пути, обработка каждого узла в качестве пункта назначения.

• A = 9 (A-> B, A-> C, A-> D, A-> E, A-> G, 2xA-> F, 2xA-> H), B = 6, a = 9 , б = 2

3 пока кажется лучшим вариантом, но есть ли лучший, обобщенный для DAG? Это то, что имеет лучший известный подход? Принципы состоят в том, чтобы использовать как можно больше информации на графике, а решение должно быть интуитивно понятным.

Answer 1

Это действительно зависит от того, что вы подразумеваете под силой. Из-за универсальности группы обеспечения доступности баз данных при представлении информации вы можете обсуждать что угодно - от потока управления с несколькими результатами до предложений аргументов неадверциальных дискурсивных связок или даже полного набора зависимостей между разными словами в предложении.

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

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

Answer 2

Я думаю, вам нужно более четко определить «силу». Это связано с проблемой максимального расхода ?

Answer 3

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

Answer 4

Хорошо, практическое применение - спортивные команды. Каждый узел - это команда, каждая ссылка - это победа над другой командой. Предположим, что нет круговых путей победы, таких как A-> B-> C-> A. Цель состоит в том, чтобы получить рейтинг силы, который не противоречит графику и ранжирует команды в порядке их силы. Этот сайт - мой футбольный сайт (100% ** 1002), где вы можете видеть полные графики всего сезона НФЛ каждую неделю. (И другие виды спорта.) Я в основном ищу алгоритмы ранжирования, отличные от тех, которые я перечислил выше, которые могут иметь еще больший смысл и могут быть защищены как использование всей информации на графике. Цель не обязательно должна быть более точной с точки зрения будущих выборов (хотя, вероятно, будет более сильный алгоритм), но вместо этого быть настолько описательной, насколько это возможно, сезона.

Вы можете увидеть 3-ю неделю сезона НФЛ на сайте. Я удалил два «бита» (длинная история), которые были неоднозначными, полагаясь на остальную часть графика, чтобы определить порядок клевания.