Phase-Field Models On Graphs
From Handwiki 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 [math]\displaystyle{ \omega_{i,j} }[/math], the graph Ginzburg–Landau functional of a map [math]\displaystyle{ u:V\to \mathbb{R} }[/math] is given by
- [math]\displaystyle{ F_\varepsilon(u) = \frac\varepsilon2 \sum_{i,j\in V} \omega_{ij} (u_i-u_j)^2 + \frac1\varepsilon \sum_{i \in V} W(u_i), }[/math]
where W is a double well potential, for example the quartic potential W(x) = x2(1 − x2). 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 uj close to 0 or close to 1, and for small [math]\displaystyle{ \varepsilon }[/math], minimisers of [math]\displaystyle{ F_\varepsilon }[/math] 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 [math]\displaystyle{ F_\varepsilon }[/math], 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,
- [math]\displaystyle{ \frac{d}{dt} u_j = -\varepsilon (\Delta u)_j-\frac1\varepsilon W'(u_j), }[/math]
where [math]\displaystyle{ \Delta }[/math] 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]
See also
- Graph cuts in computer vision
References
- ↑ 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. doi:10.1137/11083109X. ISSN 1540-3459.
- ↑ Luo, Xiyang; Bertozzi, Andrea L. (2017-05-01). "Convergence of the Graph Allen–Cahn Scheme" (in en). Journal of Statistical Physics 167 (3): 934–958. doi:10.1007/s10955-017-1772-4. ISSN 1572-9613. Bibcode: 2017JSP...167..934L.
- ↑ 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. et al. (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: [Graph theory] [Mathematical modeling]
↧ Download as ZWI file | Last modified: 12/14/2024 18:48:32 | 3 views
☰ Source: https://handwiki.org/wiki/Phase-field_models_on_graphs | License: CC BY-SA 3.0
KSF