Phase-field models on graphs

Phase-field models on graphs are a discrete analogue to phase-field models, defined on a graph. They are used in image analysis (for feature identification) and for the segmentation of social networks.

For a graph with vertices V and edge weights ${\displaystyle \omega _{i,j}}${\displaystyle \omega _{i,j}}, the graph Ginzburg–Landau functional of a map ${\displaystyle u:V\to \mathbb {R} }${\displaystyle u:V\to \mathbb {R} } is given by

${\displaystyle 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}),}${\displaystyle 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}),}

where W is a double well potential, for example the quartic potential W(x) = x²(1 − x²). The graph Ginzburg–Landau functional was introduced by Bertozzi and Flenner.^[1] In analogy to continuum phase-field models, where regions with u close to 0 or 1 are models for two phases of the material, vertices can be classified into those with u_j close to 0 or close to 1, and for small ${\displaystyle \varepsilon }${\displaystyle \varepsilon }, minimisers of ${\displaystyle F_{\varepsilon }}${\displaystyle F_{\varepsilon }} will satisfy that u_j is close to 0 or 1 for most nodes, splitting the nodes into two classes.

To effectively minimise ${\displaystyle F_{\varepsilon }}${\displaystyle F_{\varepsilon }}, a natural approach is by gradient flow (steepest descent). This means to introduce an artificial time parameter and to solve the graph version of the Allen–Cahn equation,

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

where ${\displaystyle \Delta }${\displaystyle \Delta } is the graph Laplacian. The ordinary continuum Allen–Cahn equation and the graph Allen–Cahn equation are natural counterparts, just replacing ordinary calculus by calculus on graphs. A convergence result for a numerical graph Allen–Cahn scheme has been established by Luo and Bertozzi.^[2]

It is also possible to adapt other computational schemes for mean curvature flow, for example schemes involving thresholding like the Merriman–Bence–Osher scheme, to a graph setting, with analogous results.^[3]

• Graph cuts in computer vision

• Graph theory
• Mathematical modeling

• Articles with short description
• Short description matches Wikidata