Fasfältsmodeller på grafer

Fasfältsmodeller på grafer är en diskret analog till fasfältsmodeller, definierade på en graf . De används i bildanalys (för funktionsidentifiering) och för segmentering av sociala nätverk .

Graf Ginzburg–Landau funktionell

För en graf med hörn V och kantvikter $\omega _{i,j}$ , grafen Ginzburg–Landau funktionell för en karta $u:V\to \mathbb {R}$ ges av

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

där W är en dubbelbrunnspotential, till exempel den kvartiska potentialen W ( x ) = x ² (1 − x ² ). Grafen Ginzburg–Landau funktionell introducerades av Bertozzi och Flenner. I analogi med kontinuumfasfältsmodeller, där regioner med u nära 0 eller 1 är modeller för två faser av materialet, kan hörn klassificeras i de med u j _nära 0 eller nära 1, och för små ${\ displaystyle \varepsilon }$ , minimerare av $F_{\varepsilon }$ kommer att uppfylla att u _j är nära 0 eller 1 för de flesta noder, vilket delar upp noderna i två klasser.

Graf Allen–Cahns ekvation

För att effektivt minimera $F_{\varepsilon }$ är ett naturligt tillvägagångssätt genom gradientflöde ( brantaste nedstigning) . Detta innebär att införa en artificiell tidsparameter och att lösa grafversionen av Allen–Cahn-ekvationen ,

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

där $\Delta$ är grafen Laplacian . Allen–Cahn-ekvationens ordinarie kontinuum och grafen Allen–Cahn-ekvationen är naturliga motsvarigheter, som bara ersätter vanlig kalkyl med kalkyl på grafer . Ett konvergensresultat för en numerisk graf Allen–Cahn-schema har fastställts av Luo och Bertozzi.

Det är också möjligt att anpassa andra beräkningsscheman för medelkurvaturflöde , till exempel scheman som involverar tröskelvärden som Merriman-Bence-Osher-schemat, till en grafinställning, med analoga resultat.

Se även

• Grafsnitt i datorseende