- Кластеризация ориентированных графов с использованием параметризованных ядер диффузии случайных блужданий(arXiv)
Автор:Гарри Севи, Матье Джонкере, Аргирис Калогератос
Аннотация:Кластеризация на основе оператора случайного блуждания доказала свою эффективность для неориентированных графов, но ее обобщение на ориентированные графы (орграфы) гораздо сложнее. Хотя оператор случайного блуждания хорошо определен для орграфов, в большинстве случаев такие графы не являются сильно связанными, и, следовательно, связанные случайные блуждания не являются неприводимыми, что является важным свойством для кластеризации, которое естественным образом существует в неориентированной среде. Чтобы исправить это, обычным обходным путем является либо наивная симметризация матрицы смежности, либо замена оператора естественного случайного блуждания оператором случайного блуждания телепортации, но это может привести к потере ценной информации, переносимой граничной направленностью. В этой статье мы представляем новую структуру кластеризации, параметризованную кластеризацию диффузионного ядра со случайным блужданием (P-RWDKC), которая подходит для обработки как ориентированных, так и неориентированных графов. Наша структура основана на диффузионной геометрии и обобщенной структуре спектральной кластеризации. Соответственно, мы предлагаем алгоритм, который автоматически выявляет структуру кластера в заданном масштабе, рассматривая динамику случайных блужданий, связанную с параметризованным оператором ядра, и оценивая его критическое время диффузии. Эксперименты с графами K-NN, построенными из реальных наборов данных и реальных графиков, показывают, что наш подход к кластеризации хорошо работает во всех протестированных случаях и превосходит существующие подходы в большинстве из них.
2. Ограниченный многоагентный поиск пути на ориентированных графах(arXiv)
Автор:Стефано Ардиццони, Лука Консолини, Марко Локателли, Ирэн Саккани
Аннотация: мы обсуждаем C-MP и C-MAPF, обобщения классических задач планирования движения (MP) и многоагентного поиска пути (MAPF) на ориентированном графе G. А именно, мы применяем верхний ограничивается числом агентов, занимающих каждого члена семейства вершинных подмножеств. Например, это ограничение позволяет поддерживать безопасную дистанцию между агентами. Мы доказываем, что поиск допустимого решения C-MP и C-MAPF является NP-сложным, и мы предлагаем метод сокращения для преобразования их в стандартные MP и MAPF. Этот метод редукции состоит в нахождении подмножества узлов W и редуцированного графа G/W, таких, что решение MAPF на G/W обеспечивает решение C-MAPF на G. Кроме того, мы изучаем задачу нахождения W максимального мощность, которая сильно NP-трудна.
3.Подсчет путей в ориентированных графах(arXiv)
Автор: Пётр М. Хайяц, Оскар Стаховяк
Аннотация: мы рассматриваем класс ориентированных графов с N ребрами и без петель короче k. Используя понятие помеченного графа, мы определяем графы из этого класса, которые максимизируют число всех путей длины k. Затем мы показываем R-размеченную версию этого результата для полуколец R, содержащихся в полукольце неотрицательных действительных чисел и содержащее полукольцо неотрицательных рациональных чисел.
