Graph Topology Profiling

Question

Может ли кто-нибудь предложить мне некоторые алгоритмы, которые можно использовать для анализа классификации топологии графа? Ввод: список смежности с необработанной информацией о графике. Выход: Какой граф это? В настоящее время я хочу сосредоточиться только на Pure Types - Daisy chain, Mesh, Ring, Star, Tree.

В какой области исследования алгоритма отвечает за такой алгоритм? Это вычислительная геометрия?

Редактировать - Размер графика не должен превышать 32 узла. Однако между узлами будут избыточные связи.

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

Answer 1

Начните с проверки того, что ваш график полностью подключен

Затем проверьте распределение узлов degree:.

• кольцо: Все узлы были бы имеют степень 2
• Цепь Дейзи: все узлы имеют степень 2, за исключением двух узлов со степенью 1 (существуют альтернативные определения того, что представляет собой цепочка ромашки).
• Звезда: каждый узел имеет степень 1, за исключением одного узел с d egree n-1
• Дерево: сумма степеней 2 * (количество узлов-1). Кроме того, если высокая степень к, то есть, по крайней мере, K узлов со степенью 1.
• Mesh: Все, что идет ...

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

Answer 2

Чтобы классифицировать новый экземпляр, вам нужна система классификации в первую очередь!

Другими словами, ваш график (элемент для классификации) подходит где-то в какой-то структуре данных топологий графов (система классификации). Система может быть такой же простой, как и список; в этом случае вы выполняете простой алгоритм, описанный в this other post, где список топологий определяется распределением степени.

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

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