Misplaced Pages

Phase-field models on graphs

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Phase field models on graphs) Graph-based mathematical model

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.

Graph Ginzburg–Landau functional

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

F ε ( u ) = ε 2 ∑ i , j ∈ V ω i j ( u i − u j ) 2 + 1 ε ∑ i ∈ 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. 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 uj close to 0 or close to 1, and for small ε {\displaystyle \varepsilon } , minimisers of F ε {\displaystyle F_{\varepsilon }} will satisfy that uj is close to 0 or 1 for most nodes, splitting the nodes into two classes.

Graph Allen–Cahn equation

To effectively minimise F ε {\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,

d d t u j = − ε ( Δ u ) j − 1 ε W ′ ( u j ) , {\displaystyle {\frac {d}{dt}}u_{j}=-\varepsilon (\Delta u)_{j}-{\frac {1}{\varepsilon }}W'(u_{j}),}

where Δ {\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.

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.

See also

References

  1. Bertozzi, A.; Flenner, A. (2012-01-01). "Diffuse Interface Models on Graphs for Classification of High Dimensional Data". Multiscale Modeling & Simulation. 10 (3): 1090–1118. CiteSeerX 10.1.1.299.4261. doi:10.1137/11083109X. ISSN 1540-3459.
  2. Luo, Xiyang; Bertozzi, Andrea L. (2017-05-01). "Convergence of the Graph Allen–Cahn Scheme". Journal of Statistical Physics. 167 (3): 934–958. Bibcode:2017JSP...167..934L. doi:10.1007/s10955-017-1772-4. ISSN 1572-9613.
  3. van Gennip, Yves. Graph Ginzburg–Landau: discrete dynamics, continuum limits, and applications. An overview. In Ei, S.-I.; Giga, Y.; Hamamuki, N.; Jimbo, S.; Kubo, H.; Kuroda, H.; Ozawa, T.; Sakajo, T.; Tsutaya, K. (2019-07-30). "Proceedings of 44th Sapporo Symposium on Partial Differential Equations". Hokkaido University Technical Report Series in Mathematics. 177: 89–102. doi:10.14943/89899.
Categories: