A grafikonok spektrális elmélete

A matematika , a spektrális elmélet grafikonok érintett a kapcsolatok közötti spektrumok a különböző mátrixok , hogy lehet társított gráf és annak tulajdonságait. Ez az algebrai gráfelmélet egyik ága . Általában a szomszédsági mátrix és a normalizált Laplac-mátrix érdekel minket .

Egy gráfot leíró mátrixok

Adjacencia mátrix

Legyen egy grafikon , ahol a csúcsok és az élek halmazát jelöli. A grafikon csúcsokkal rendelkezik, megjegyzett és élekkel rendelkezik . A grafikon szomszédsági mátrixának minden elemét a következők határozzák meg: $G = (V, E)$ $V$ $E$ $| V | = n$ $v_ {1}, \ cdots, v_ {n} \ a V-ben$ $| E | = m$ ${\ displaystyle e_ {ij}, v_ {i} \ V-ben, v_ {j} \ V-ben}$ $NÁL NÉL$ $G$

{\ displaystyle a_ {ij} = \ balra \ {{\ begin {tömb} {rl} 1 és {\ mbox {si}} e_ {ij} \ az E \\ 0 és {\ mbox {különben.}} \ vége {tömb}} \ jobb.}

Grafikon	A szomszédsági mátrix ábrázolása	Laplaciánus mátrix ábrázolása (nem normalizált)
	${\ begin {pmatrix} 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 \\\ end {pmatrix}}$	${\ begin {pmatrix} 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 {pmatrix}}$

Fokmátrix és Laplacian

A fokmátrix egy átlós mátrix, ahol az elemek megfelelnek a csúcs linkjeinek számának , vagyis annak fokának . Ezen és az előző felhasználásával meghatározhatjuk a nem normalizált laplaci mátrixot is . $D$ $D _ {{ii}}$ $én$ $L = DA$

Normalizált formáját azáltal kapjuk meg , hol van az identitásmátrix . Minden elemével közvetlenül megszerezzük : $A$ $L '= D ^ {{- 1/2}} LD ^ {{- 1/2}} = ID ^ {{- 1/2}} AD ^ {{- 1/2}}$ $én$ $A$

\ ell _ {{i, j}}: = {\ begin {esetben} 1 & {\ mbox {si}} \ i = j \ {\ mbox {és}} \ \ deg (v_ {i}) \ neq 0 \\ - {\ frac {1} {{\ sqrt {\ deg (v_ {i}) \ deg (v_ {j})}}}}} és {\ mbox {si}} \ i \ neq j \ { \ mbox {és}} \ v_ {i} {\ text {a}} v_ {j} \\ 0 és {\ text {egyébként}} szomszédságában van. \ end {esetben}}

Incidencia mátrix

Végül egy gráf incidencia mátrixa az a dimenzió mátrix, amelyben az elem egyenlő 1-vel, ha a csúcs az él vége , és egyébként 0-val. A következő relációval rendelkezünk, ahol az identitásmátrixot jelöljük : $M$ $G = (V, E)$ $| V | \ alkalommal | E |$ $b _ {{ij}}$ $v_ {i}$ $x_ {j}$ $én$

$A = MM ^ {T} -D$
A a szomszédsági mátrix, a vonal grafikon , $L (G)$ $A = M ^ {T} M-2I$
A a szomszédsági mátrix a felosztás grafikon , $S (G)$ $A = {\ begin {pmatrix} 0 és M ^ {T} \\ M & 0 \\\ end {pmatrix}}$

A spektrum fogalma és a jellegzetes polinom

A mátrix spektruma a sajátértékeinek összessége ; ha azok valódi, egyetértünk, hogy a rang: . Kiterjesztéssel a grafikon spektrumáról beszélünk . Felidézzük, hogy egy sajátérték algebrai sokasága a monomon ereje a jellegzetes polinomban (vagyis a gyök sokasága a jellegzetes polinomban). A karakterisztikus polinom módosítása a grafikon egyéb tulajdonságainak figyelembevétele érdekében is lehetséges: alapértelmezésben figyelembe vesszük a polinomot (amelyet a gráf jellegzetes polinomjának nevezünk ), de érdekelhetnek olyan változatok is, mint a vagy . $\ lambda _ {0} \ leq \ lambda _ {1} \ leq \ cdots \ leq \ lambda _ {{n-1}}$ $\ lambda$ $(X- \ lambda)$ $P_ {G} (\ lambda) = | \ lambda IA |$ $R_ {G} (\ lambda) = | \ lambda IDA |$ $Q_ {G} (\ lambda) = | D | ^ {{- 1}} \ cdot | \ lambda DA |$

Adjacencia mátrix spektrum

A gráf mátrixa pozitív , és nem csökkenthető, ha a gráf össze van kapcsolva. Abban az esetben, irányítatlan gráf, a mátrix szimmetrikus, és hermitikus, azaz, ahol a segédanyag mátrix a . A mátrix nyoma megegyezik a hurkok számával: valóban, az átlón egy elem jelzi a hurok jelenlétét, a nyom pedig ezen elemek összege. A következő tulajdonságokkal rendelkezünk: $A ^ {\ tőr} = A$ $A ^ {\ tőr}$ $NÁL NÉL$

A mátrix spektrális sugara , vagyis a legnagyobb sajátértéke kielégít egy összekapcsolt gráfot. Az alsó határt akkor érjük el, ha a gráf egy útvonal, és a felsőt elérjük a teljes gráfhoz. $\ rho (A)$ ${\ displaystyle 2 \ cdot \ cos \ bal ({\ frac {\ pi} {n + 1}} \ jobb) \ leq \ rho (A) \ leq n-1}$
Ha a gráf -rendszeres majd és a sok számát adja meg csatlakoztatott komponensek. $k$ $\ rho (A) = k$ $\ rho (A)$
A grafikon csak akkor tartalmaz páratlan hosszúságú ciklust, ha az szintén sajátérték . $- \ rho (A)$
Ha vannak külön sajátértékek, akkor az átmérő megelégszik . $m$ $D$ $D \ leq m-1$
A méret a maximális stabil kielégíti , ahol rendre száma sajátértékek alacsonyabb, azonos vagy magasabb, mint 0. $t$ $t \ leq p_ {0} + \ min (p _ {-}, p _ {+})$ $p _ {-}, p_ {0}, p _ {+}$
${\ frac {\ rho (A)} {- q}} + 1 \ leq \ chi (G) \ leq \ rho (A) +1$ hol van a kromatikus szám és a legkisebb sajátérték. $\ chi (G)$ $q$

Normalizált laplaci mátrix spektrum

A sajátérték az úgynevezett algebrai kapcsolat a grafikon. A spektrum alapvető tulajdonságait az alábbiakban foglaljuk össze: $\ lambda _ {1}$

$\ lambda _ {0} = 0$ .
$\ sum _ {i} \ lambda _ {i} \ leq n$ ha a gráf össze van kapcsolva .
Ha G és egy teljes gráf, akkor különben . $n \ geq 2$ $\ lambda _ {1} = {\ frac {n} {n-1}}$ $\ lambda _ {1} \ leq {\ frac {n} {n-1}}$
Ha a grafikon csatlakoztatva van, akkor . Ha és akkor pontosan vannak komponensei ( azaz összekapcsolt grafikonjai). $\ lambda _ {1}> 0$ $\ lambda _ {i} = 0$ $\ lambda _ {{i + 1}} \ neq 0$ $G$ $i + 1$
$\ lambda _ {i} \ leq 2$ $\ összes i \ leq n-1$ .

A Kirchhoff-tétel (más néven mátrixfa-tétel ) kapcsolatot ad az átívelő fák száma és a laplaci mátrix között.

Alkalmazások

Hálózati elemzés

A hálózatokon végzett mérések többsége a klaszterezési együtthatóra , az átlagos távolságra vagy a fokok eloszlására vonatkozik: a spektrális technikák alkalmazása kisebbségben van, de „a gyakorlati kísérletek azt sugallják, hogy a spektrális elemzés jól adaptálható az adatokhoz szabálytalan [...], miközben a klaszterezési együttható megfelelőbb a szabályosabb adatokhoz (és ezért a fizikusok kiterjedten használták rácsok, kristályok stb. vizsgálatára). Különösen az internet különböző mintáinak spektrumát mértük router szinten: a tanulmány szerzői földrajzi szinten figyeltek meg különbségeket, magyarázatként arra utalva, hogy Észak-Amerikában a hálózat fejlettebb. Ázsia és Európa; ezeket a méréseket összehasonlítottuk az interneten található tulajdonságokat reprezentálni hivatott modellekből vettekkel, és lényegében egyik modell sem felelt meg az internetnek spektrum szinten.

Grafikon particionálása

A grafikon laplaciánus mátrixának sajátvektorainak elemzése az úgynevezett spektrális módszerrel lehetővé teszi a grafikon partíciójának megtalálását . Spektrális felosztásról beszélünk . Ennek a módszernek olyan sokféle területen vannak alkalmazásai, mint a feladatok elosztása párhuzamos számítással, képszegmentálás, lineáris rendszerek felbontása stb.

Megjegyzések és hivatkozások

(en) Dragos M. Cvetkovic, Michael Doob és Horst Sachs - Spectra of Graphs, Heidelberg , Lipcse, 1994, ( ISBN 3335004078 ) .
(in) Fan Chung - Spektrális grafikon elmélet, Regionális matematikai konferencia-sorozat , 92. szám, az American Mathematical Society 1997 kiadása
(en) Christos Gkantsidis, Milena Mihail és Ellen Zegura - Internet topológiák spektrális elemzése, IEEE Infocom , 2003.
(fr) Charles-Edmond Bichot - A Partitionnement de graphe könyv többszintű módszere, fejezete Charles-Edmond Bichot és Patrick Siarry koordinálásával, Hermes-Lavoisier, 2010–51-87. ( ISBN 9782746230057 )

Külső linkek

Daniel Spielman , „ Spektrális grafika elmélete (tanfolyamoldal, jegyzetekre mutató linkekkel) ”, a Yale Egyetemen ,2012