Laplaciánská matice - Laplacian matrix

V matematický pole teorie grafů, Laplaciánská matice, také nazývaný graf Laplacian, přijímací matice, Kirchhoffova matice nebo diskrétní Laplacian, je matice zastoupení a graf. Laplaciánskou matici lze použít k vyhledání mnoha užitečných vlastností grafu. Dohromady s Kirchhoffova věta, lze jej použít k výpočtu počtu klenout se nad stromy pro daný graf. The nejmenší řez grafu lze aproximovat druhým nejmenším vlastním číslem jeho laplaciánu o Cheegerova nerovnost. Lze jej také použít ke konstrukci nízkodimenzionální vložení, což může být užitečné pro různé strojové učení aplikace.

Definice

Laplaciánská matice pro jednoduché grafy

Vzhledem k tomu, jednoduchý graf ${ displaystyle G}$ s ${ displaystyle n}$ vrcholy, jeho lalaciánská matice ${ textstyle L_ {n krát n}}$ je definován jako:^[1]

${ displaystyle L = D-A,}$

kde D je stupeň matice a A je matice sousedství grafu. Od té doby ${ textstyle G}$ je jednoduchý graf, ${ textový styl A}$ obsahuje pouze 1 s nebo 0 s a jeho diagonální prvky jsou všechny 0 s.

V případě řízené grafy, buď indegree nebo outgree může být použit, v závislosti na aplikaci.

Prvky ${ textstyle L}$ jsou dány

${ displaystyle L_ {i, j}: = { begin {cases} deg (v_ {i}) & { mbox {if}} i = j - 1 & { mbox {if}} i neq j { mbox {a}} v_ {i} { mbox {sousedí s}} v_ {j} 0 & { mbox {jinak}} end {případů}}}$

kde ${ displaystyle operatorname {deg} (v_ {i})}$ je stupeň vrcholu ${ displaystyle i}$.

Symetrický normalizovaný Laplacian

Symetrická normalizovaná laplaciánská matice je definována jako:^[1]

${ displaystyle L ^ { text {sym}}: = D ^ {- { frac {1} {2}}} LD ^ {- { frac {1} {2}}} = ID ^ {- { frac {1} {2}}} REKLAMA ^ {- { frac {1} {2}}}}$,

Prvky ${ textstyle L ^ { text {sym}}}$ jsou dány

${ displaystyle L_ {i, j} ^ { text {sym}}: = { begin {cases} 1 & { mbox {if}} i = j { mbox {and}} deg (v_ {i} ) neq 0 - { frac {1} { sqrt { deg (v_ {i}) deg (v_ {j})}}} & { mbox {if}} i neq j { mbox {and}} v_ {i} { mbox {sousedí s}} v_ {j} 0 & { mbox {jinak}}. end {cases}}}$

Náhodná chůze normalizovala Laplacian

Laplaciánská matice normalizovaná na náhodnou chůzi je definována jako:

${ displaystyle L ^ { text {rw}}: = D ^ {- 1} L = I-D ^ {- 1} A}$

Prvky ${ textstyle L ^ { text {rw}}}$ jsou dány

${ displaystyle L_ {i, j} ^ { text {rw}}: = { begin {cases} 1 & { mbox {if}} i = j { mbox {and}} deg (v_ {i} ) neq 0 - { frac {1} { deg (v_ {i})}} & { mbox {if}} i neq j { mbox {and}} v_ {i} { mbox {sousedí s}} v_ {j} 0 & { mbox {jinak}}. end {cases}}}$

Zobecněný Laplacian

Zobecněný Laplacian ${ displaystyle Q}$ je definován jako:^[2]

${ displaystyle { begin {cases} Q_ {i, j} <0 & { mbox {if}} i neq j { mbox {and}} v_ {i} { mbox {sousedí s}} v_ { j} Q_ {i, j} = 0 & { mbox {if}} i neq j { mbox {a}} v_ {i} { mbox {nesousedí s}} v_ {j} { mbox {libovolné číslo}} & { mbox {jinak}}. end {případy}}}$

Všimněte si, že obyčejný Laplacian je zobecněný Laplacian.

Příklad

Zde je jednoduchý příklad označeného, ​​neorientovaného grafu a jeho laplaciánské matice.

Označený graf	Titulní matice	Matice sousedství	Laplaciánská matice
	${ textstyle left ({ begin {array} {rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 0 & 3 & 0 & 0 & 0 & 0 0 & 0 & 2 & 0 & 0 & 0 0 & 0 & 0 & 3 & 0 & 0 0 & 0 & 0 & 0 & 3 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 a 0$	${ textstyle left ({ begin {array} {rrrrrr} 0 & 1 & 0 & 0 & 1 & 0 1 & 0 & 1 & 0 & 1 & 0 0 & 1 & 0 & 1 & 0 & 0 0 & 0 & 1 & 0 & 1 & 1 1 & 1 & 0 & 1 & 0 & 0 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0$	${ textstyle left ({ begin {array} {rrrrrr} 2 & -1 & 0 & 0 & -1 & 0 - 1 & 3 & -1 & 0 & -1 & 0 0 & -1 & 2 & -1 & 0 & 0 0 & 0 & -1 & 3 & -1 & -1 - 1 & -1 & 0 & -1 & 3 & 0 0 & 0 & 0 & -1 & 0 & 1 end {array}} right)}$

Vlastnosti

Pro (neorientovaný) graf G a jeho laplaciánská matice L s vlastní čísla ${ textstyle lambda _ {0} leq lambda _ {1} leq cdots leq lambda _ {n-1}}$:

• L je symetrický.
• L je kladně semidefinitní (to je ${ textstyle lambda _ {i} geq 0}$ pro všechny ${ textový styl i}$). Toto je ověřeno v matice výskytu část (níže). To je patrné také ze skutečnosti, že Laplacian je symetrický a diagonálně dominantní.
• L je M-matice (jeho off-diagonální položky jsou nepozitivní, ale skutečné části jeho vlastních čísel jsou nezáporné).
• Součet všech řádků a sloupců L je nula. V součtu je stupeň vrcholu součten s „-1“ pro každého souseda.
• V důsledku, ${ textstyle lambda _ {0} = 0}$, protože vektor ${ textstyle mathbf {v} _ {0} = (1,1, tečky, 1)}$ splňuje ${ textstyle L mathbf {v} _ {0} = mathbf {0}.}$ To také znamená, že laplaciánská matice je singulární.
• Počet připojené komponenty v grafu je rozměr prázdný prostor Laplacian a algebraická multiplicita vlastního čísla 0.
• Nejmenší nenulová vlastní hodnota L se nazývá spektrální mezera.
• Druhá nejmenší vlastní hodnota L (může být nula) je algebraická konektivita (nebo Fiedlerova hodnota ) z G a přibližuje nejmenší řez grafu.
• The Laplacian je operátor na n-rozměrném vektorovém prostoru funkcí ${ textstyle f: V to mathbb {R}}$, kde ${ textový styl}$ je vrcholová množina G a ${ textstyle n = | V |}$.
• Když G je k-pravidelné, normalizovaný Laplacian je: ${ textstyle { mathcal {L}} = { tfrac {1} {k}} L = I - { tfrac {1} {k}} A}$, kde A je matice sousedství a I je matice identity.
• Pro graf s více připojené komponenty, L je úhlopříčka bloku matice, kde každý blok je příslušná lalaciánská matice pro každou složku, případně po změně pořadí vrcholů (tj. L je permutace podobná blokové diagonální matici).
• Stopa laplaciánské matice L je rovný ${ textstyle 2m}$ kde ${ textstyle m}$ je počet hran uvažovaného grafu.

Matice výskytu

Definovat ${ textstyle | e | times | v |}$ orientované matice výskytu M s prvkem M_ev pro hranu E (spojovací vrchol i a j, s i > j) a vrchol proti dána

${ displaystyle M_ {ev} = left {{ begin {array} {rl} 1, & { text {if}} v = i - 1, & { text {if}} v = j 0, & { text {jinak}}. End {pole}} vpravo.}$

Pak Laplacianská matice L splňuje

${ displaystyle L = M ^ { textyf {T}} M}$

kde ${ textstyle M ^ { textyf {T}}}$ je maticová transpozice z M.

Nyní zvažte vlastní složení z ${ textstyle L}$s vlastními jednotkovými normami ${ textstyle mathbf {v} _ {i}}$ a odpovídající vlastní čísla ${ textstyle lambda _ {i}}$:

${ displaystyle { begin {zarovnáno} lambda _ {i} & = mathbf {v} _ {i} ^ { textyf {T}} L mathbf {v} _ {i} & = mathbf {v} _ {i} ^ { textyf {T}} M ^ { textyf {T}} M mathbf {v} _ {i} & = left (M mathbf {v} _ {i } right) ^ { textyf {T}} doleva (M mathbf {v} _ {i} right). end {zarovnáno}}}$

Protože ${ textstyle lambda _ {i}}$ lze zapsat jako vnitřní produkt vektoru ${ textstyle M mathbf {v} _ {i}}$ to samo o sobě ukazuje ${ textstyle lambda _ {i} geq 0}$ a tak vlastní čísla ${ textstyle L}$ jsou všechny nezáporné.

Deformovaný Laplacian

The deformovaný Laplacian je obecně definována jako

${ displaystyle Delta (s) = I-sA + s ^ {2} (D-I)}$

kde Já je matice identity, A je matice sousedství, D je matice studia a s je (komplexní hodnota) číslo. ^[3]
Standardní Laplacian je spravedlivý ${ textstyle Delta (1)}$ a ${ textstyle Delta (-1) = D + A}$ je bezvýznamný Laplacian.

Signless Laplacian

The bezvýznamný Laplacian je definován jako

$${ displaystyle Q = D + A}$$

${ displaystyle D}$

${ displaystyle A}$

${ displaystyle L}$

${ displaystyle Q}$

$${ displaystyle Q = RR ^ {T}}$$

${ textstyle R}$

${ displaystyle Q}$

$${ displaystyle mathbf {x} ^ {T} Q mathbf {x} = mathbf {x} ^ {T} RR ^ {T} mathbf {x} implikuje R ^ {T} mathbf {x} = mathbf {0}.}$$

${ displaystyle mathbf {x} neq mathbf {0}}$

Symetrický normalizovaný Laplacian

The (symetrický) normalizovaný Laplacian je definován jako

${ displaystyle L ^ { text {sym}}: = D ^ {- { frac {1} {2}}} LD ^ {- { frac {1} {2}}} = ID ^ {- { frac {1} {2}}} REKLAMA ^ {- { frac {1} {2}}}}$

kde L je (nenormalizovaný) Laplacian, A je matice sousedství a D je matice stupňů. Protože matice stupňů D je úhlopříčka a kladná, jeho vzájemná odmocnina ${ textstyle D ^ {- { frac {1} {2}}}}$ je pouze diagonální matice, jejíž diagonální vstupy jsou převrácené hodnoty kladných odmocnin diagonálních vstupů D. Symetrický normalizovaný Laplacian je symetrická matice.

Jeden má: ${ textstyle L ^ { text {sym}} = SS ^ {*}}$, kde S je matice, jejíž řádky jsou indexovány vrcholy a jejichž sloupce jsou indexovány hranami G tak, že každý sloupec odpovídající hraně e ​​= {u, v} má záznam ${ textstyle { frac {1} { sqrt {d_ {u}}}}}$ v řádku odpovídajícímu u záznam ${ textstyle - { frac {1} { sqrt {d_ {v}}}}}$ v řádku odpovídajícímu v a má 0 položek jinde. (${ textstyle S ^ {*}}$ označuje transpozici S).

Všechna vlastní čísla normalizovaného Laplacianu jsou skutečná a nezáporná. Můžeme to vidět následovně. Od té doby ${ textstyle L ^ { text {sym}}}$ je symetrický, jeho vlastní čísla jsou skutečná. Jsou také nezáporné: zvažte vlastní vektor ${ textový styl}$ z ${ textstyle L ^ { text {sym}}}$ s vlastním číslem λ a předpokládejme ${ textstyle g = D ^ { frac {1} {2}} f}$. (Můžeme považovat g a f za skutečné funkce na vrcholech v.) Pak:

${ displaystyle lambda = { frac { langle g, L ^ { text {sym}} g rangle} { langle g, g rangle}} = { frac { left langle g, D ^ {- { frac {1} {2}}} LD ^ {- { frac {1} {2}}} g right rangle} { langle g, g rangle}} = { frac { langle f, Lf rangle} { left langle D ^ { frac {1} {2}} f, D ^ { frac {1} {2}} f right rangle} } = { frac { sum _ {u sim v} (f (u) -f (v)) ^ {2}} { sum _ {v} f (v) ^ {2} d_ { v}}} geq 0,}$

kde používáme vnitřní produkt ${ textstyle langle f, g rangle = součet _ {v} f (v) g (v)}$, součet za všechny vrcholy v, a ${ textstyle součet _ {u sim v}}$ označuje součet za všechny neuspořádané páry sousedních vrcholů {u, v}. Množství ${ textstyle sum _ {u, v} (f (u) -f (v)) ^ {2}}$ se nazývá Dirichletova suma f, zatímco výraz ${ textstyle { frac { levý langle g, L ^ { text {sym}} g pravý rangle} { langle g, g rangle}}}$ se nazývá Rayleighův kvocient g.

Nechat 1 být funkce, která předpokládá hodnotu 1 na každém vrcholu. Pak ${ textstyle D ^ { frac {1} {2}} 1}$ je vlastní funkce ${ textstyle L ^ { text {sym}}}$ s vlastním číslem 0.^[5]

Vlastní čísla normalizovaného symetrického laplaciánu ve skutečnosti splňují 0 = μ₀ ≤… ≤ μ_{n − 1} ≤ 2. Tato vlastní čísla (známá jako spektrum normalizovaného Laplacianu) se dobře vztahují k jiným invariantům grafů pro obecné grafy.^[6]

Náhodná chůze normalizovala Laplacian

The náhodná chůze normalizovaná Laplacian je definován jako

${ displaystyle L ^ { text {rw}}: = D ^ {- 1} L}$

kde D je matice stupňů. Protože matice stupňů D je diagonální, jeho inverzní ${ textstyle D ^ {- 1}}$ je jednoduše definována jako diagonální matice, která má diagonální záznamy, které jsou převrácenými hodnotami odpovídajících pozitivních diagonálních záznamů D.

Pro izolované vrcholy (ty se stupněm 0) je běžnou volbou nastavit odpovídající prvek ${ textstyle L_ {i, i} ^ { text {rw}}}$ na 0.

Tato konvence má za následek pěknou vlastnost, že multiplicita vlastního čísla 0 se rovná počtu připojených komponent v grafu.

Maticové prvky ${ textstyle L ^ { text {rw}}}$ jsou dány

${ displaystyle L_ {i, j} ^ { text {rw}}: = { begin {cases} 1 & { mbox {if}} i = j { mbox {and}} deg (v_ {i}) neq 0 - { frac {1} { deg (v_ {i})}} & { mbox {if}} i neq j { mbox {and}} v_ {i} { mbox {sousedí s}} v_ {j} 0 & { mbox {jinak}}. end {cases}}}$

Název randomizované chůze normalizovaný Laplacian pochází ze skutečnosti, že tato matice je ${ textstyle L ^ { text {rw}} = I-P}$, kde ${ textstyle P = D ^ {- 1} A}$ je prostě přechodová matice náhodného chodce v grafu. Například pojďme ${ textový styl e_ {i}}$ označit i-té standardní základ vektor. Pak ${ textstyle x = e_ {i} P}$ je vektor pravděpodobnosti představující distribuci umístění náhodného chodce po provedení jediného kroku od vrcholu ${ textový styl i}$; tj., ${ textstyle x_ {j} = mathbb {P} vlevo (v_ {i} až v_ {j} vpravo)}$. Obecněji, pokud vektor ${ textstyle x}$ je rozdělení pravděpodobnosti umístění náhodného chodce na vrcholech grafu ${ textstyle x '= xP ^ {t}}$ je rozdělení pravděpodobnosti chodce po ${ textový styl}$ kroky.

Jeden to může zkontrolovat

${ displaystyle L ^ { text {rw}} = ID ^ {- { frac {1} {2}}} vlevo (IL ^ { text {sym}} vpravo) D ^ { frac {1 } {2}}}$,

tj., ${ textstyle L ^ { text {rw}}}$ je podobný k normalizovanému Laplacianu ${ textstyle L ^ { text {sym}}}$. Z tohoto důvodu, i když ${ textstyle L ^ { text {rw}}}$ obecně není poustevník, má skutečná vlastní čísla. Jeho vlastní hodnoty skutečně souhlasí s vlastními hodnotami ${ textstyle L ^ { text {sym}}}$ (což je poustevník).

Grafy

Jako stranou asi náhodné procházky po grafech, zvažte jednoduchý neorientovaný graf. Zvažte pravděpodobnost, že se chodítko nachází na vrcholu i v čase t, vzhledem k rozdělení pravděpodobnosti, že byl na vrcholu j v čase t - 1 (za předpokladu jednotné šance na krok podél kterékoli z hran připojených k danému vrcholu):

${ displaystyle p_ {i} (t) = součet _ {j} { frac {A_ {ij}} { deg left (v_ {j} right)}} p_ {j} (t-1) ,}$

nebo v maticovém vektorovém zápisu:

${ displaystyle p (t) = AD ^ {- 1} p (t-1).}$

(Rovnováha, která se nastavuje jako ${ textstyle t rightarrow infty}$, je definováno ${ textstyle p = AD ^ {- 1} p}$.)

Tento vztah můžeme přepsat jako

${ displaystyle D ^ {- { frac {1} {2}}} p (t) = left [D ^ {- { frac {1} {2}}} AD ^ {- { frac {1 } {2}}} vpravo] D ^ {- { frac {1} {2}}} p (t-1).}$

${ textstyle A _ { text {redukovaný}} ekviv D ^ {- { frac {1} {2}}} AD ^ {- { frac {1} {2}}}}$ je symetrická matice zvaná snížená matice sousedství. Kroky na této náhodné procházce tedy vyžadují převzetí pravomocí ${ textstyle A _ { text {omezené}}}$, což je jednoduchá operace, protože ${ textstyle A _ { text {omezené}}}$ je symetrický.

Interpretace jako diskrétní Laplaceův operátor

Laplaciánskou matici lze interpretovat jako maticovou reprezentaci konkrétního případu diskrétní Laplaceův operátor. Taková interpretace umožňuje, např. Zobecnit lapovou matici na případy grafů s nekonečným počtem vrcholů a hran, což vede k lapovské matici nekonečné velikosti.

Předpokládat ${ textstyle phi}$ popisuje distribuci tepla napříč a graf, kde ${ textstyle phi _ {i}}$ je teplo na vrcholu ${ textový styl i}$. Podle Newtonův zákon chlazení, teplo přenesené z uzlu ${ textový styl i}$ do uzlu ${ textstyle j}$ je úměrný ${ textstyle phi _ {i} - phi _ {j}}$ pokud uzly ${ textový styl i}$ a ${ textstyle j}$ jsou připojeny (pokud nejsou připojeny, nedochází k přenosu tepla). Poté pro tepelnou kapacitu ${ textstyle k}$,

${ displaystyle { begin {aligned} { frac {d phi _ {i}} {dt}} & = - k sum _ {j} A_ {ij} left ( phi _ {i} - phi _ {j} right) & = - k left ( phi _ {i} sum _ {j} A_ {ij} - sum _ {j} A_ {ij} phi _ {j} right) & = - k left ( phi _ {i} deg (v_ {i}) - sum _ {j} A_ {ij} phi _ {j} right) & = -k sum _ {j} left ( delta _ {ij} deg (v_ {i}) - A_ {ij} right) phi _ {j} & = - k sum _ {j} left ( ell _ {ij} right) phi _ {j}. end {aligned}}}$

V maticovém vektorovém zápisu

${ displaystyle { begin {zarovnáno} { frac {d phi} {dt}} & = - k (D-A) phi & = - kL phi, end {zarovnáno}}}$

který dává

${ displaystyle { frac {d phi} {dt}} + kL phi = 0.}$

Všimněte si, že tato rovnice má stejnou formu jako rovnice tepla, kde matice -L nahrazuje laplaciánského operátora ${ textstyle nabla ^ {2}}$; tedy „graf Laplacian“.

Chcete-li najít řešení této diferenciální rovnice, použijte standardní techniky řešení prvního řádu maticová diferenciální rovnice. To znamená, napište ${ textstyle phi}$ jako lineární kombinace vlastních vektorů ${ textstyle mathbf {v} _ {i}}$ z L (aby ${ textstyle L mathbf {v} _ {i} = lambda _ {i} mathbf {v} _ {i}}$) s časově závislými koeficienty, ${ textstyle phi (t) = součet _ {i} c_ {i} (t) mathbf {v} _ {i}.}$

Zapojení do původního výrazu (protože L je symetrická matice, její vlastní normové vlastní vektory ${ textstyle mathbf {v} _ {i}}$ jsou kolmé):

${ displaystyle { begin {aligned} 0 = & { frac {d left ( sum _ {i} c_ {i} (t) mathbf {v} _ {i} right)} {dt}} + kL left ( sum _ {i} c_ {i} (t) mathbf {v} _ {i} right) = & sum _ {i} left [{ frac {dc_ {i } (t)} {dt}} mathbf {v} _ {i} + kc_ {i} (t) L mathbf {v} _ {i} right] = & sum _ {i} left [{ frac {dc_ {i} (t)} {dt}} mathbf {v} _ {i} + kc_ {i} (t) lambda _ {i} mathbf {v} _ {i} right] Rightarrow & { frac {dc_ {i} (t)} {dt}} + k lambda _ {i} c_ {i} (t) = 0, end {zarovnáno}} }$

jehož řešení je

${ displaystyle c_ {i} (t) = c_ {i} (0) e ^ {- k lambda _ {i} t}.}$

Jak je uvedeno výše, vlastní čísla ${ textstyle lambda _ {i}}$ z L jsou nezáporné, což ukazuje, že řešení difuzní rovnice se blíží rovnováze, protože se pouze exponenciálně rozpadá nebo zůstává konstantní. To také ukazuje, že dané ${ textstyle lambda _ {i}}$ a počáteční stav ${ textstyle c_ {i} (0)}$, řešení kdykoli t Může být nalezeno.^[7]

Najít ${ textstyle c_ {i} (0)}$ pro každého ${ textový styl i}$ z hlediska celkového počátečního stavu ${ textstyle phi (0)}$jednoduše promítněte ${ textstyle phi (0)}$ na vlastní jednotkové normy ${ textstyle mathbf {v} _ {i}}$;

${ displaystyle c_ {i} (0) = left langle phi (0), mathbf {v} _ {i} right rangle}$.

V případě neorientovaných grafů to funguje, protože ${ textstyle L}$ je symetrický a spektrální věta, jeho vlastní vektory jsou všechny ortogonální. Takže projekce na vlastní vektory ${ textstyle L}$ je jednoduše ortogonální transformace souřadnic počáteční podmínky na sadu souřadnic, které se exponenciálně a nezávisle na sobě rozpadají.

Rovnovážné chování

Rozumět ${ textstyle lim _ {t to infty} phi (t)}$, jediné podmínky ${ textstyle c_ {i} (t) = c_ {i} (0) e ^ {- k lambda _ {i} t}}$ zůstávají ty, kde ${ textstyle lambda _ {i} = 0}$, od té doby

${ displaystyle lim _ {t to infty} e ^ {- k lambda _ {i} t} = left {{ begin {pole} {rlr} 0 & { text {if}} & lambda _ {i}> 0 1 & { text {if}} & lambda _ {i} = 0 end {array}} right }}$

Jinými slovy, rovnovážný stav systému je zcela určen pomocí jádro z ${ textstyle L}$.

Protože podle definice ${ textstyle sum _ {j} L_ {ij} = 0}$, vektor ${ textstyle mathbf {v} ^ {1}}$ všech je v jádře. Pokud existují ${ textstyle k}$ disjunktní připojené komponenty v grafu lze tento vektor všech rozdělit na součet ${ textstyle k}$ nezávislý ${ textstyle lambda = 0}$ vlastní vektory jedniček a nul, kde každá připojená komponenta odpovídá vlastnímu vektoru s jednotkami u prvků v připojené složce a nulami jinde.

Důsledkem toho je to pro danou počáteční podmínku ${ textstyle c (0)}$ pro graf s ${ textstyle N}$ vrcholy

${ Displaystyle lim _ {t to infty} phi (t) = left langle c (0), mathbf {v ^ {1}} right rangle mathbf {v ^ {1}} }$

kde

${ displaystyle mathbf {v ^ {1}} = { frac {1} { sqrt {N}}} [1,1, ..., 1]}$

Pro každý prvek ${ textstyle phi _ {j}}$ z ${ textstyle phi}$, tj. pro každý vrchol ${ textstyle j}$ v grafu lze přepsat jako

${ displaystyle lim _ {t to infty} phi _ {j} (t) = { frac {1} {N}} součet _ {i = 1} ^ {N} c_ {i} ( 0)}$.

Jinými slovy, v ustáleném stavu hodnota ${ textstyle phi}$ konverguje ke stejné hodnotě u každého z vrcholů grafu, což je průměr počátečních hodnot u všech vrcholů. Jelikož se jedná o řešení rovnice šíření tepla, dává to intuitivně smysl. Očekáváme, že sousední prvky v grafu si budou vyměňovat energii, dokud se tato energie nerozloží rovnoměrně po všech prvcích, které jsou navzájem spojeny.

Příklad operátora na mřížce

Tento GIF ukazuje postup difúze, jak je řešen technikou laplacian grafu. Graf je sestaven přes mřížku, kde je každý pixel v grafu připojen k jeho 8 hraničním pixelům. Hodnoty v obraze pak prostřednictvím těchto spojení plynule difundují k sousedům. Tento konkrétní snímek začíná třemi hodnotami silných bodů, které se pomalu přelévají na jejich sousedy. Celý systém se nakonec ustálí na stejné hodnotě v rovnováze.

Tato část ukazuje příklad funkce ${ textstyle phi}$ rozptylující se v čase grafem. Graf v tomto příkladu je sestaven na 2D diskrétní mřížce, přičemž body v mřížce jsou spojeny s jejich osmi sousedy. Tři počáteční body jsou zadány tak, aby měly kladnou hodnotu, zatímco ostatní hodnoty v mřížce jsou nulové. V průběhu času exponenciální úpadek rozdělí hodnoty v těchto bodech rovnoměrně po celé mřížce.

Níže je uveden kompletní zdrojový kód Matlabu, který byl použit ke generování této animace. Ukazuje proces určování počátečních podmínek, promítání těchto počátečních podmínek na vlastní hodnoty Laplaciánské matice a simulace exponenciálního rozpadu těchto projektovaných počátečních podmínek.

N = 20; % Počet pixelů podél dimenze obrázkuA = nuly(N, N); % ObrázekAdj = nuly(N * N, N * N); % Matice sousedství% Použijte 8 sousedů a vyplňte matici sousedstvídx = [- 1, 0, 1, - 1, 1, - 1, 0, 1];dy = [- 1, - 1, - 1, 0, 0, 1, 1, 1];pro x = 1: N    pro y = 1: N        index = (X - 1) * N + y;        pro ne = 1: délka (dx)            newx = X + dx(ne);            newy = y + dy(ne);            -li newx> 0 && newx <= N && newy> 0 && newy <= N                index2 = (newx - 1) * N + newy;                Adj(index, index2) = 1;            koneckonec    koneckonec% NÍŽE JE KLÍČOVÝ KÓD, KTERÝ VÝPOČET ŘEŠENÍ DIFERENCIÁLNÍ ROVNICEDeg = diag(součet(Adj, 2)); % Vypočítejte matici stupňůL = Deg - Adj; % Vypočítejte laplaciánskou matici z hlediska stupňů a sousedních matic[PROTI, D] = eig(L); % Vypočítejte vlastní hodnoty / vektory laplaciánské maticeD = diag(D);% Počáteční podmínka (kolem a umístěte několik velkých kladných hodnot% vše ostatní nastaví na nulu)C0 = nuly(N, N);C0(2:5, 2:5) = 5;C0(10:15, 10:15) = 10;C0(2:5, 8:13) = 7;C0 = C0(:);C0V = PROTI'*C0; % Transformujte počáteční stav do souřadnicového systémuvlastních vektorůpro t = 0:0.05:5    % Procházejte časy a rozkládejte každou počáteční složku    Phi = C0V .* exp(- D * t); % Exponenciálního rozpadu pro každou složku    Phi = PROTI * Phi; % Transformace z vlastního souřadnicového systému do původního souřadnicového systému    Phi = přetvarovat(Phi, N, N);    % Zobrazte výsledky a zapište do souboru GIF    imagesc(Phi);    caxis([0, 10]);     titul(sprintf('Difúze t =% 3f', t));    rám = getframe(1);    im = frame2im(rám);    [vadí mi to, cm] = rgb2ind(im, 256);    -li t == 0        napiš(vadí mi to, cm, 'out.gif', 'gif', „Loopcount“, inf, 'Zpoždění', 0.1);    jinýimwrite (imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0,1);    koneckonec

Aproximace na záporný spojitý Laplacian

Na graf Laplaciánova matice lze dále pohlížet jako na maticovou formu aproximace k (kladnému semitečnému) Laplacian operátor získaný metoda konečné diference.(Vidět Diskrétní Poissonova rovnice )^[8] V této interpretaci je každý vrchol grafu považován za bod mřížky; lokální konektivita vrcholu určuje aproximaci konečných rozdílů šablona v tomto bodě mřížky je velikost mřížky vždy jedna pro každou hranu a na žádných bodech mřížky nejsou žádná omezení, což odpovídá případu homogenní Neumannova okrajová podmínka, tj. volná hranice.

Řízené multigrafy

Analog laplaciánské matice lze definovat pro směrované multigrafy.^[9] V tomto případě laplaciánská matice L je definován jako

${ displaystyle L = D-A}$

kde D je diagonální matice s D_i,i rovná se převýšení vrcholu i a A je matice s A_i,j roven počtu hran od i na j (včetně smyček).

Viz také

• Matice tuhosti
• Vzdálenost odporu
• Matice přechodové rychlosti
• Počet na konečných vážených grafech
• Graf Fourierova transformace

Reference

• T. Sunada, "Diskrétní geometrická analýza", Sborník sympozií z čisté matematiky, (ed. P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev), 77 (2008), 51–86.
• B. Bollobás, Teorie moderních grafůSpringer-Verlag (1998, opraveno vyd. 2013), ISBN  0-387-98488-7, Kapitoly II.3 (Vektorové prostory a matice spojené s grafy), VIII.2 (Matice sousedství a Laplacian), IX.2 (Elektrické sítě a náhodné procházky).