Графовое расстояние

Топологическая мера расстояния, при которой исходное метрическое пространство объектов заменяется графом. **Процесс вычисления:** 1. Каждый объект становится вершиной графа $V$. 2. Ребра $E$ проводятся только между $k$ ближайшими соседями (или точками в пределах радиуса $\epsilon$). 3. Расстояние между точками $A$ и $B$ определяется как длина кратчайшего пути по ребрам графа (алгоритм Дейкстры), либо через оценку связности случайного блуждания. **Применение:** Используется в методах *Спектральной кластеризации* и *Affinity Propagation*. Эта метрика блестяще решает задачу "скрученного рулона" (Swiss Roll), когда точки геометрически лежат близко друг к другу в Евклидовом пространстве, но топологически находятся на разных витках спирали и должны быть разнесены по графу.