Algebraisk anslutning

En exempelgraf, med 6 hörn, diameter 3, anslutning 1 och algebraisk anslutning 0,722

Den algebraiska anslutningsmöjligheten (även känd som Fiedler-värde eller Fiedler-egenvärde efter Miroslav Fiedler ) för en graf G är det näst minsta egenvärdet (räknar flera egenvärden separat) i den laplaciska matrisen för G . Detta egenvärde är större än 0 om och endast om G är en sammankopplad graf . Detta är en följd av att antalet gånger 0 dyker upp som ett egenvärde i Laplacian är antalet anslutna komponenter i grafen. Storleken på detta värde återspeglar hur väl sammankopplat den övergripande grafen är. Den har använts för att analysera nätverkens robusthet och synkroniseringsbarhet .

Egenskaper

Den trunkerade icosahedron- eller Buckminsterfulleren -grafen har en traditionell anslutning på 3 och en algebraisk anslutning på 0,243.

Den algebraiska kopplingen för oriktade grafer med icke-negativa vikter, $a(G)\geq 0$ med olikheten strikt om och endast om G är ansluten. Den algebraiska anslutningen kan dock vara negativ för generella riktade grafer, även om G är en sammankopplad graf . Dessutom begränsas värdet av den algebraiska anslutningen ovan av grafens traditionella (vertex) anslutningsbarhet , ${\text{algebraisk anslutning}}\leq {\text{anslutning}}$ . Om antalet hörn av en oriktad sammankopplad graf med icke-negativa kantvikter är n och diametern är D , är den algebraiska anslutningen också känd för att vara begränsad nedanför av ${\text{algebraisk anslutning}} \geq {\frac {1}{nD}}$ , och faktiskt (i ett resultat på grund av Brendan McKay ) med ${\frac {4}{nD}}$ . För grafen med 6 noder som visas ovan (n=6,D=3) betyder dessa bundna medel, 4/18 = 0,222 ≤ algebraisk anslutning 0,722 ≤ anslutning 1.

Till skillnad från den traditionella kopplingen ^{[ förtydligande behövs ]} är den algebraiska kopplingen beroende av antalet hörn, såväl som det sätt på vilket hörn är anslutna. I slumpmässiga grafer minskar den algebraiska anslutningen med antalet hörn och ökar med den genomsnittliga graden .

Den exakta definitionen av den algebraiska anslutningen beror på vilken typ av Laplacian som används. Fan Chung har utvecklat en omfattande teori med hjälp av en omskalad version av Laplacian, vilket eliminerar beroendet av antalet hörn, så att gränserna är något annorlunda.

I modeller för synkronisering på nätverk, som Kuramoto-modellen , uppstår den Laplacian matrisen naturligt, så den algebraiska anslutningen ger en indikation på hur lätt nätverket kommer att synkroniseras. Andra mått, såsom det genomsnittliga avståndet (karakteristisk väglängd) kan också användas, och i själva verket är den algebraiska anslutningen nära relaterad till det (reciproka av) medelavståndet.

Den algebraiska anslutningen relaterar också till andra anslutningsattribut, såsom det isoperimetriska talet , som begränsas nedanför av halva den algebraiska anslutningen.

Fiedler vektor

Den ursprungliga teorin om algebraisk anslutning producerades av Miroslav Fiedler . Till hans ära egenvektorn associerad med den algebraiska anslutningen fått namnet Fiedler-vektorn . Fiedler-vektorn kan användas för att partitionera en graf.

Partitionering av en graf med Fiedler-vektorn

Uppdelning i två sammankopplade grafer.

För exempelgrafen i det inledande avsnittet är Fiedler-vektorn ${\textstyle {\begin{pmatrix}0.415&0.309&0.061&-0.221&-0.21pmatrix} }}$ . De negativa värdena är associerade med den dåligt anslutna vertex 6, och den angränsande artikulationspunkten , vertex 4; medan de positiva värdena är associerade med de andra hörnen. Tecknen , för värdena i Fiedler-vektorn kan därför användas för att dela upp denna graf i två komponenter: ${\textstyle \{1,2,3,5\$ . Alternativt kan värdet på 0,069 (vilket är nära noll) placeras i en klass för sig och dela upp grafen i tre komponenter: ${\textstyle \{1,2,5\},\{3\},\{4,6\}}$ eller flyttas till den andra partitionen ${\textstyle \{ 1,2,5\},\{3,4,6\}}$ , enligt bilden. Kvadratvärdena för komponenterna i Fiedler-vektorn, summerande till ett eftersom vektorn är normaliserad, kan tolkas som sannolikheter för att motsvarande datapunkter ska tilldelas den teckenbaserade partitionen.

Se även