Conductancia (teoría de grafos)

En informática teórica , teoría de grafos y matemáticas , la conductancia es un parámetro de una cadena de Markov estrechamente ligado a su tiempo de mezcla , es decir, a la rapidez con la que la cadena converge a su distribución estacionaria , si esta existe. De forma equivalente, la conductancia puede considerarse un parámetro de un grafo dirigido , en cuyo caso puede utilizarse para analizar la rapidez con la que convergen los paseos aleatorios en dicho grafo.

La conductancia de un grafo está estrechamente relacionada con la constante de Cheeger del grafo, también conocida como expansión de aristas o número isoperimético. Sin embargo, debido a sutiles diferencias en las definiciones, la conductancia y la expansión de aristas generalmente no coinciden si los grafos no son regulares . Por otro lado, la noción de conductancia eléctrica que aparece en las redes eléctricas no guarda relación con la conductancia de un grafo.

La conductancia fue definida por primera vez por Mark Jerrum y Alistair Sinclair en 1988 para demostrar que el permanente de una matriz con entradas de {0,1} tiene un esquema de aproximación en tiempo polinomial . ^{[ 1 ]} En la demostración, Jerrum y Sinclair estudiaron la cadena de Markov que alterna entre emparejamientos perfectos y casi perfectos en grafos bipartitos mediante la adición o eliminación de aristas individuales. Definieron y utilizaron la conductancia para demostrar que esta cadena de Markov es de mezcla rápida . Esto significa que, después de ejecutar la cadena de Markov durante un número polinomial de pasos, se garantiza que la distribución resultante sea cercana a la distribución estacionaria, que en este caso es la distribución uniforme en el conjunto de todos los emparejamientos perfectos y casi perfectos. Esta cadena de Markov de mezcla rápida permite extraer en tiempo polinomial muestras aleatorias aproximadamente uniformes del conjunto de todos los emparejamientos perfectos en el grafo bipartito, lo que a su vez da lugar al esquema de aproximación en tiempo polinomial para calcular el permanente.

Para grafos d -regulares no dirigidos${\displaystyle G}$sin pesos en los bordes, la conductancia${\displaystyle \varphi (G)}$es igual a la constante de Cheeger${\displaystyle h(G)}$dividido por d , es decir, tenemos${\displaystyle \varphi (G)=h(G)/d}$.

En términos más generales, dejemos${\displaystyle G}$ser un grafo dirigido con${\displaystyle n}$vértices, conjunto de vértices${\displaystyle V}$, conjunto de bordes${\displaystyle E}$y pesos reales${\displaystyle a_{ij}\geq 0}$en cada borde${\displaystyle ij\in E}$. Dejar${\displaystyle S\subseteq V}$sea ​​cualquier subconjunto de vértices. La conductancia${\displaystyle \varphi (S)}$del corte${\displaystyle (S,{\bar {S}})}$se define mediante$${\displaystyle \varphi (S)={\frac {\displaystyle a(S,{\bar {S}})}{\min(\mathrm {vol} (S),\mathrm {vol} ({\bar {S}}))}}\,,}$$dónde$${\displaystyle a(S,T)=\sum _{i\in S}\sum _{j\in T}a_{ij}\,,}$$y entonces${\displaystyle a(S,{\bar {S}})}$es el peso total de todos los bordes que cruzan el corte desde${\displaystyle S}$a${\displaystyle {\bar {S}}}$y$${\displaystyle \mathrm {vol} (S)=a(S,V)=\sum _{i\in S}\sum _{j\in V}a_{ij}}$$es el volumen de${\displaystyle S}$, es decir, el peso total de todas las aristas que comienzan en${\displaystyle S}$. Si${\displaystyle \mathrm {vol} (S)}$igual${\displaystyle 0}$, entonces${\displaystyle a(S,{\bar {S}})}$también es igual a${\displaystyle 0}$y${\displaystyle \varphi (S)}$se define como${\displaystyle 1}$.

La conductancia${\displaystyle \varphi (G)}$del gráfico${\displaystyle G}$Ahora se define como la conductancia mínima sobre todos los cortes posibles:$${\displaystyle \varphi (G)=\min _ {S\subseteq V}\varphi (S).}$$De forma equivalente, la conductancia satisface$${\displaystyle \varphi (G)=\min \left\{{\frac {a(S,{\bar {S}})}{\mathrm {vol} (S)}}\;\colon \;{\mathrm {vol} (S)\leq {\frac {\mathrm {vol} (V)}{2}}}\right\}\,.}$$

En aplicaciones prácticas, a menudo se considera la conductancia solo sobre un corte. Una generalización común de la conductancia consiste en tratar el caso de pesos asignados a los bordes: entonces se suman los pesos; si el peso es una resistencia, se suman los pesos recíprocos.

La noción de conductancia es fundamental para el estudio de la percolación en física y otras áreas aplicadas; así, por ejemplo, la permeabilidad del petróleo a través de rocas porosas puede modelarse en términos de la conductancia de un gráfico, con ponderaciones dadas por el tamaño de los poros.

La conductancia también ayuda a medir la calidad de un agrupamiento espectral . El valor máximo de la conductancia entre los clústeres proporciona un límite que, junto con el peso de las aristas entre clústeres, permite definir una medida de la calidad del agrupamiento. Intuitivamente, la conductancia de un clúster (que puede considerarse como un conjunto de vértices en un grafo) debería ser baja. Además, también se puede utilizar la conductancia del subgrafo inducido por un clúster (denominada "conductancia interna").

Para una cadena de Markov reversible ergódica con un grafo subyacente G , la conductancia es una forma de medir cuán difícil es abandonar un pequeño conjunto de nodos. Formalmente, la conductancia de un grafo se define como el mínimo sobre todos los conjuntos.${\displaystyle S}$de la capacidad de${\displaystyle S}$dividido por el flujo ergódico de salida de${\displaystyle S}$Alistair Sinclair demostró que la conductancia está estrechamente ligada al tiempo de mezcla en cadenas de Markov reversibles ergódicas. También podemos ver la conductancia de una manera más probabilística, como la probabilidad de abandonar un conjunto de nodos dado que comenzamos en ese conjunto. Esto también se puede escribir como

${\displaystyle \Phi =\min _{S\subseteq V,0<\pi (S)\leq {\frac {1}{2}}}\Phi _{S}=\min _{S\subseteq V,0<\pi (S)\leq {\frac {1}{2}}}{\frac {\sum _{x\in S,y\in {\bar {S}}}\pi (x)P(x,y)}{\pi (S)}},}$

dónde${\displaystyle \pi }$es la distribución estacionaria de la cadena. En algunos textos, esta cantidad también se denomina relación de cuello de botella de G.

La conductancia está relacionada con el tiempo de mezcla de la cadena de Markov en el entorno reversible. Precisamente, para cualquier cadena de Markov reversible e irreducible con probabilidades de bucle propio${\displaystyle P(y,y)\geq 1/2}$para todos los estados${\displaystyle y}$y un estado inicial${\displaystyle x\in \Omega }$,

${\displaystyle {\frac {1}{4\Phi }}\leq \tau _{x}(\delta )\leq {\frac {2}{\Phi ^{2}}}{\big (}\ln \pi (x)^{-1}+\ln \delta ^{-1}{\big )}}$.

• Relación E/I de Krackhardt
• teoría de la percolación
• Distancia de resistencia