Kaavioiden spektriteoria

On matematiikka , spektrin teoriaa kaavioita on kiinnostunut väliset suhteet spektrien eri matriiseja , jotka voivat liittyä kaavio ja sen ominaisuuksia. Se on osa algebrallista graafiteoriaa . Olemme yleensä kiinnostuneita vierekkäisyysmatriisista ja normalisoidusta Laplacin-matriisista .

Kaaviota kuvaavat matriisit

Adjacency-matriisi

Antaa olla kaavio , jossa merkitsee joukko pisteitä ja joukko reunoja. Kuvaaja on kärkipisteet, huomattava ja reunat, huomattava . Kaavion vierekkäisyysmatriisin jokaisen elementin määrittelee: $G = (V, E)$ $V$ $E$ $| V | = n$ $v_ {1}, \ cdots, v_ {n} \ V: ssä$ $| E | = m$ ${\ displaystyle e_ {ij}, v_ {i} \ V, v_ {j} \ V}$ $AT$ $G$

{\ displaystyle a_ {ij} = \ vasen \ {{\ begin {array} {rl} 1 & {\ mbox {si}} e_ {ij} \ E \\ 0: ssa ja {\ mbox {muuten.}} \ lopeta {array}} \ right.}

Kaavio	Esitys vierekkäisyysmatriisin avulla	Esitys Laplacian-matriisilla (ei normalisoitu)
	${\ 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}}$	${\ alkaa {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}}$

Asteiden matriisi ja Laplacian

Matriisi astetta on diagonaalinen matriisi , jossa elementit vastaavat useita linkkejä päälaen , toisin sanoen sen asteen . Tämän ja edellisen matriisin avulla voimme määritellä myös normalisoimattoman Laplacian-matriisin . $D.$ $D _ {{ii}}$ $i$ $L = DA$

Saamme sen normalisoitu muodon mukaan , missä on identiteetti matriisi . Saamme myös suoraan jokaisella sen elementillä: $L '$ $L '= D ^ {{- 1/2}} LD ^ {{- 1/2}} = ID ^ {{- 1/2}} AD ^ {{- 1/2}}$ $Minä$ $L '$

\ ell _ {{i, j}}: = {\ aloita {tapaukset} 1 & {\ mbox {si}} \ i = j \ {\ mbox {ja}} \ \ deg (v_ {i}) \ neq 0 \\ - {\ frac {1} {{\ sqrt {\ deg (v_ {i}) \ deg (v_ {j})}}}}} ja {\ mbox {si}} \ i \ neq j \ { \ mbox {ja}} \ v_ {i} {\ text {on}} v_ {j} \\ 0 ja {\ text {muuten}} vieressä. \ end {cases}}

Ilmaantuvuusmatriisi

Lopuksi kuvaajan esiintymämatriisi on ulottuvuuksien matriisi, jossa elementti on yhtä suuri kuin 1, jos piste on reunan pää , ja muutoin 0. Meillä on seuraavat joukko suhteita, joissa tarkoittaa identiteettimatriisiksi : $M$ $G = (V, E)$ $| V | \ kertaa | E |$ $b _ {{ij}}$ $v_ {i}$ $x_ {j}$ $Minä$

$A = MM ^ {T} -D$
Vierusmatriisin matriisin viivakuvaaja , $L (G)$ $A = M ^ {T} M-2I$
Vierusmatriisin matriisin osa-kaavio , $S (G)$ $A = {\ begin {pmatrix} 0 ja M ^ {T} \\ M & 0 \\\ end {pmatrix}}$

Spektrin käsite ja tyypillinen polynomi

Spektri matriisi on joukko sen ominaisarvot ; jos ne ovat todellisia, olemme sopineet listalla: . Laajennuksena puhumme kaavion spektristä . Muistutamme, että algebrallinen moninaisuus on ominaisarvo on voima monomi on tunnusomainen polynomi (eli moninaisuus juurta karakteristisen polynomin). On myös mahdollista muuttaa tunnusomainen polynomi ottamaan huomioon muita ominaisuuksia kuvaaja: oletuksena pidämme polynomi (kutsutaan karakteristisen polynomin kuvaajan ), mutta voimme myös olla kiinnostunut varianttien, kuten tai . $\ 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 |$

Adjacency-matriisispektri

Kuvaajan matriisi on positiivinen , eikä sitä voida pienentää, jos kaavio on kytketty. Tapauksessa suuntaamattoman graafin, matriisi on symmetrinen ja hermiittinen, että on, jossa on lisä matriisi on . Jälki matriisin on yhtä suuri määrä silmukoita: todellakin, elementti lävistäjä osoittaa, että läsnä on silmukan ja jälki on summa nämä elementit. Meillä on seuraavat ominaisuudet: $A ^ {\ tikari} = A$ $A ^ {\ tikari}$ $AT$

Matriisin spektrisäde , toisin sanoen sen suurin ominaisarvo, tyydyttää yhdistetyn kuvaajan. Alempi raja saavutetaan, jos kaavio on polku, ja ylempi saavutetaan koko kuvaajalle. $\ rho (A)$ ${\ displaystyle 2 \ cdot \ cos \ vasen ({\ frac {\ pi} {n + 1}} \ oikea) \ leq \ rho (A) \ leq n-1}$
Jos kaavio on epäsäännöllinen ja moninkertaisuus antaa yhdistettyjen komponenttien määrän. $k$ $\ rho (A) = k$ $\ rho (A)$
Kaavio sisältää parittoman jakson vain, jos se on myös ominaisarvo . $- \ rho (A)$
Jos on olemassa erillisiä ominaisarvoja, halkaisija tyydyttää . $m$ $D.$ $D \ leq m-1$
Koko on enintään vakaa täyttää jossa ovat vastaavasti määrä ominaisarvojen alentaa, yhtä suuri tai suurempi kuin 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$ missä on kromaattinen numero ja pienin ominaisarvo. $\ chi (G)$ $q$

Normalisoitu Laplacian matriisispektri

Ominaisarvoa kutsutaan kaavion algebralliseksi liitettävyydeksi . Taajuuden olennaiset ominaisuudet on tiivistetty alla: $\ lambda _ {1}$

$\ lambda _ {0} = 0$ .
$\ sum _ {i} \ lambda _ {i} \ leq n$ jos kaavio on kytketty .
Jos ja G on täydellinen kaavio sitten , muuten . $n \ geq 2$ $\ lambda _ {1} = {\ frac {n} {n-1}}$ $\ lambda _ {1} \ leq {\ frac {n} {n-1}}$
Jos kaavio on kytketty, niin . Jos ja sitten on tarkalleen komponentteja ( ts. Yhdistettyjä kuvaajia). $\ lambda _ {1}> 0$ $\ lambda _ {i} = 0$ $\ lambda _ {{i + 1}} \ neq 0$ $G$ $i + 1$
$\ lambda _ {i} \ leq 2$ $\ kaikki i \ leq n-1$ .

Lause Kirchhoffin (kutsutaan myös matriisi-puu teoreema ) antaa suhde määrä ulottuu puiden ja Laplacen matriisi.

Sovellukset

Verkkoanalyysi

Suurin osa verkoissa suoritetuista mittauksista koskee klusteroitumiskerrointa , keskimääräistä etäisyyttä tai asteiden jakaumaa: spektritekniikoiden käyttö on vähäistä, mutta "käytännön kokeiden perusteella spektrianalyysi voidaan mukauttaa hyvin tietoihin epäsäännöllinen [...], kun taas ryhmittymiskerroin soveltuu hyvin säännöllisempiin tietoihin (ja siksi fyysikot ovat käyttäneet sitä laajasti ruudukkojen, kiteiden jne. tutkimiseen) ". Erityisesti mitattiin Internetin eri näytteiden spektrit reitittimen tasolla: tutkimuksen tekijät havaitsivat eroja maantieteellisellä tasolla, mikä viittaa selityksenä siitä, että verkko Pohjois-Amerikassa on edistyneempi. Aasia ja Eurooppa; näitä mittauksia verrattiin myös malleihin, jotka otettiin edustamaan Internetissä löydettyjä ominaisuuksia, eikä olennaisesti yksikään malleista vastannut Internetiä spektritasolla.

Kaavioiden osiointi

Kuvaajan Laplacian-matriisin ominaisvektorien analysointi spektrimenetelmänä mahdollistaa graafin osion löytämisen . Puhumme spektrin osioinnista . Tällä menetelmällä on sovelluksia niin monipuolisilla aloilla kuin tehtävien jakaminen rinnakkaislaskennassa, kuvan segmentointi, lineaaristen järjestelmien resoluutio jne.

Huomautuksia ja viitteitä

(en) Dragos M. Cvetkovic, Michael Doob ja Horst Sachs - Spectra of Graphs, Heidelberg , Leipzig, 1994, ( ISBN 3335004078 ) .
(in) Fan Chung - Spectral Graph Theory, Matematiikan alueellinen konferenssisarja , nro 92, julkaissut American Mathematical Society 1997
(en) Christos Gkantsidis, Milena Mihail ja Ellen Zegura - Internet-topologioiden spektrianalyysi, IEEE Infocom , 2003.
(FR) Charles-Edmond Bichot - monitasoista menetelmä, luvussa kirjan Partitionnement de graphe koordinoi Charles-Edmond Bichot ja Patrick Siarry, Hermes-Lavoisier, p51-87, 2010. ( ISBN 9782746230057 )

Ulkoiset linkit

Daniel Spielman , " Spectral Graph Theory (kurssisivu, linkit muistiinpanoihin) " , Yalen yliopisto ,2012