Konduktans (graf)

En oriktad graf

G

och några exempel skär med motsvarande konduktanser

I grafteorin mäter konduktansen för en graf $G = (V, E)$ hur "väl sammansatt" grafen är: den styr hur snabbt en slumpmässig promenad på $G$ konvergerar till dess stationära fördelning . Konduktansen av en graf kallas ofta Cheeger-konstanten för en graf som analog till dess motsvarighet i spektral geometri . Eftersom elektriska nätverk är intimt släkt med slumpmässiga promenader ^{med förvirring .} en lång historia i användningen av termen "konduktans", hjälper detta alternativa namn att undvika eventuell

Konduktansen för ett snitt $(S,{\bar {S}})$ i en graf definieras som:

\varphi (S)={\frac {\sum _{i\in S,j\in {\bar {S}}}a_{ij}}{\min(a(S),a({\bar {S}}))}}

där $a ij$ är ingångarna i närliggande matris för $G$ , så att

a(S)=\summa _{i\in S}\summa _{j\in V}a_{ij}

är det totala antalet (eller vikten) av de kanter som faller in med $S$ . $a (S)$ kallas också en volym av mängden $S\subseteq V$ .

Konduktansen för hela grafen är den minsta konduktansen över alla möjliga skärningar:

\phi (G)=\min _{S\subseteq V}\varphi (S).

På motsvarande sätt definieras konduktansen för en graf enligt följande:

\phi (G):=\min _{S\subseteq V;0\leq a(S)\leq a(V)/2}{\frac {\sum _{i\in S,j\ i {\bar {S}}}a_{ij}}{a(S)}}.\,

För en $d$ -reguljär graf är konduktansen lika med det isoperimetriska talet dividerat med $d$ .

Generaliseringar och tillämpningar

I praktiska tillämpningar betraktar man ofta konduktansen endast över ett snitt. En vanlig generalisering av konduktans är att hantera fallet med vikter tilldelade kanterna: sedan läggs vikterna till; om vikten är i form av ett motstånd, läggs de ömsesidiga vikterna till.

Konduktansbegreppet ligger till grund för studiet av perkolation i fysik och andra tillämpade områden; sålunda kan till exempel petroleums permeabilitet genom poröst berg modelleras i termer av konduktansen hos en graf, med vikter givna av porstorlekar.

Konduktans hjälper också till att mäta kvaliteten på ett spektralkluster . Maximum bland konduktansen hos kluster ger en gräns som kan användas, tillsammans med inter-klusterkantvikt, för att definiera ett mått på klustringskvaliteten. Intuitivt bör konduktansen för ett kluster (som kan ses som en uppsättning hörn i en graf) vara låg. Bortsett från detta kan konduktansen för subgrafen inducerad av ett kluster (kallad "intern konduktans") också användas.

Markov kedjor

För en ergodisk reversibel Markov-kedja med en underliggande graf G , är konduktansen ett sätt att mäta hur svårt det är att lämna en liten uppsättning noder. Formellt definieras konduktansen för en graf som minimum över alla uppsättningar $S$ av kapaciteten för $S$ dividerat med det ergodiska flödet ut från $S$ . Alistair Sinclair visade att konduktansen är nära kopplad till blandningstiden i ergodiska reversibla Markov-kedjor. Vi kan också se konduktans på ett mer probabilistiskt sätt, som den minimala sannolikheten att lämna en liten uppsättning noder givet att vi började i den uppsättningen till att börja med. Att skriva $\Phi _{S}$ för den villkorade sannolikheten att lämna en uppsättning noder S givet att vi var i den uppsättningen till att börja med, är konduktansen den minimala Φ S {\ $Phi _{S }}$ över uppsättningar $S$ som har en total stationär sannolikhet på högst 1/2.

Konduktansen är relaterad till Markov-kedjans blandningstid i reversibel inställning.

Se även

Béla Bollobás (1998). Modern grafteori . GTM . Vol. 184. Springer-Verlag . sid. 321. ISBN 0-387-98488-7 .
Kannan, R.; Vempala, S.; Vetta, A. (maj 2004). "Om klustringar: bra, dåliga och spektrala" (PDF) . J. ACM . 51 (3): 497–515. doi : 10.1145/990308.990313 .
Fan Chung (1997). Spektralgrafteori . CBMS föreläsningsanteckningar. Vol. 92. AMS-publikationer. sid. 212. ISBN 0-8218-0315-8 .
A. Sinclair. Algoritmer för slumpmässig generering och räkning: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
D. Levin, Y. Peres , EL Wilmer : Markov-kedjor och blandningstider