Модели фазового поля на графах

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

Граф функционала Гинзбурга–Ландау

Для графа с вершинами V и весами ребер $\omega _{i,j}$, график функционала Гинзбурга–Ландау отображения $u:V\to \mathbb {R}$ дается

$F_{\varepsilon }(u)={\frac {\varepsilon }{2}}\sum _{i,j\in V}\omega _{ij}(u_{i}-u_{j})^{2}+{\frac {1}{\varepsilon }}\sum _{i\in V}W(u_{i}),$

где W - потенциал двойной ямы, например потенциал четвертой степени W ( x ) = x ² (1 − х ² ). Граф функционала Гинзбурга–Ландау был введен Бертоцци и Фленнером. По аналогии с моделями фазового поля континуума, где области с u, близкими к 0 или 1, являются моделями двух фаз материала, вершины можно разделить на вершины с u _j, близкими к 0 или близким к 1, и для малых $\varepsilon$, минимизаторы $F_{\varepsilon }$ будет удовлетворять тому, что u _j близко к 0 или 1 для большинства узлов, разделяя узлы на два класса.

График уравнения Аллена – Кана

Чтобы эффективно минимизировать $F_{\varepsilon }$, естественным подходом является градиентный поток ( самый крутой спуск ). Это означает ввести искусственный временной параметр и решить графическую версию уравнения Аллена-Кана :

${\frac {d}{dt}}u_{j}=-\varepsilon (\Delta u)_{j}-{\frac {1}{\varepsilon }}W'(u_{j}),$

где $\Delta$ является графом Лапласа . Обычное уравнение Аллена-Кана для континуума и уравнение Аллена-Кана в графе являются естественными аналогами, просто заменяющими обычное исчисление исчислением на графах . Результат сходимости для схемы Аллена – Кана с числовым графом был установлен Луо и Бертоцци.

Также возможно адаптировать другие вычислительные схемы для потока средней кривизны , например схемы, включающие определение порога, такие как схема Мерримана-Бенса-Ошера, к настройке графика с аналогичными результатами.

См. также

• Разрезы графов в компьютерном зрении