Conductancia (teoría de grafos)

Una propiedad de mezcla de cadenas y gráficos de Markov

Un grafo no dirigido G y algunos cortes de ejemplo con las conductancias correspondientes

En informática teórica , teoría de grafos y matemáticas , la conductancia es un parámetro de una cadena de Markov que está estrechamente ligado a su tiempo de mezcla , es decir, la rapidez con la que la cadena converge a su distribución estacionaria , en caso de que exista. De manera 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 recorridos aleatorios en el grafo.

La conductancia de un grafo está estrechamente relacionada con la constante de Cheeger del grafo, que también se conoce como expansión de aristas o número isoperimetral. Sin embargo, debido a definiciones sutilmente diferentes, la conductancia y la expansión de aristas no suelen coincidir si los grafos no son regulares . Por otro lado, la noción de conductancia eléctrica que aparece en las redes eléctricas no está relacionada con la conductancia de un grafo.

Historia

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 de tiempo polinomial . ^{[1] En la prueba, Jerrum y Sinclair estudiaron la cadena de Markov que cambia entre} emparejamientos perfectos y casi perfectos en gráficos bipartitos agregando o eliminando aristas individuales. Definieron y usaron la conductancia para demostrar que esta cadena de Markov se mezcla rápidamente . 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 esté cerca de 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 hace posible en tiempo polinomial extraer muestras aleatorias aproximadamente uniformes del conjunto de todos los emparejamientos perfectos en el gráfico bipartito, lo que a su vez da lugar al esquema de aproximación de tiempo polinomial para calcular el permanente.

Definición

Para gráficos d -regulares no dirigidos sin pesos de arista, la conductancia es igual a la constante de Cheeger dividida por d , es decir, tenemos . ${\displaystyle G}$ ${\displaystyle \varphi (G)}$ ${\displaystyle h(G)}$ ${\displaystyle \varphi (G)=h(G)/d}$

De manera más general, sea un grafo dirigido con vértices, conjunto de vértices , conjunto de aristas y pesos reales en cada arista . Sea cualquier subconjunto de vértices. La conductancia del corte se define mediante donde y es el peso total de todas las aristas que cruzan el corte desde hasta y es el volumen de , es decir, el peso total de todas las aristas que comienzan en . Si es igual a , entonces también es igual a y se define como . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle a_{ij}\geq 0}$ ${\displaystyle ij\in E}$ ${\displaystyle S\subseteq V}$ ${\displaystyle \varphi (S)}$ ${\displaystyle (S,{\bar {S}})}$ $${\displaystyle \varphi (S)={\frac {\displaystyle a(S,{\bar {S}})}{\min(\mathrm {vol} (S),\mathrm {vol} ({\bar {S}}))}}\,,}$$ $${\displaystyle a(S,T)=\sum _{i\in S}\sum _{j\in T}a_{ij}\,,}$$ ${\displaystyle a(S,{\bar {S}})}$ ${\displaystyle S}$ ${\displaystyle {\bar {S}}}$ $${\displaystyle \mathrm {vol} (S)=a(S,V)=\sum _{i\in S}\sum _{j\in V}a_{ij}}$$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \mathrm {vol} (S)}$ ${\displaystyle 0}$ ${\displaystyle a(S,{\bar {S}})}$ ${\displaystyle 0}$ ${\displaystyle \varphi (S)}$ ${\displaystyle 1}$

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

Generalizaciones y aplicaciones

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

La noción de conductancia sustenta 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 una roca porosa se puede modelar en términos de la conductancia de un gráfico, con pesos dados por los tamaños de poro.

La conductancia también ayuda a medir la calidad de un agrupamiento espectral . El máximo entre la conductancia de los agrupamientos proporciona un límite que se puede utilizar, junto con el peso de los bordes entre agrupamientos, para definir una medida de la calidad del agrupamiento. Intuitivamente, la conductancia de un agrupamiento (que se puede ver como un conjunto de vértices en un gráfico) debería ser baja. Aparte de esto, también se puede utilizar la conductancia del subgrafo inducida por un agrupamiento (llamada "conductancia interna").

Cadenas de Markov

Para una cadena de Markov reversible ergódica con un gráfico subyacente G , la conductancia es una forma de medir lo difícil que es abandonar un pequeño conjunto de nodos. Formalmente, la conductancia de un gráfico se define como el mínimo sobre todos los conjuntos de la capacidad de dividido por el flujo ergódico de salida de . Alistair Sinclair demostró que la conductancia está estrechamente vinculada al tiempo de mezcla en las 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 para empezar. Esto también puede escribirse como ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

${\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)}},}$

donde es la distribución estacionaria de la cadena. En cierta literatura, esta cantidad también se denomina relación de cuello de botella de G . ${\displaystyle \pi }$

La conductancia está relacionada con el tiempo de mezcla de la cadena de Markov en el entorno reversible. Precisamente, para cualquier cadena de Markov irreducible y reversible con probabilidades de bucle propio para todos los estados y un estado inicial , ${\displaystyle P(y,y)\geq 1/2}$ ${\displaystyle y}$ ${\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 )}}$.

Véase también

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

Notas

1. Jerrum y Sinclair 1988, págs. 235–244.

Referencias

• Jerrum, Mark ; Sinclair, Alistair (1988). Conductancia y propiedad de mezcla rápida para cadenas de Markov: la aproximación de la resolución permanente . ACM Press. doi :10.1145/62212.62234. ISBN 978-0-89791-264-8.
• Béla, Bollobás (1998). Teoría de grafos moderna . GTM . vol. 184. Springer-Verlag . pag. 321.ISBN​ 0-387-98488-7.
• Kannan, Ravi; Vempala, Santosh; Vetta, Adrian (2004). "Sobre agrupamientos: buenos, malos y espectrales". Revista de la ACM . 51 (3): 497–515. doi :10.1145/990308.990313. ISSN  0004-5411.
• Chung, Fan RK (1997). Teoría de grafos espectrales . Providence (RI): American Mathematical Soc. ISBN 0-8218-0315-8.
• Sinclair, Alistair (1993). Algoritmos para la generación y el conteo aleatorios: un enfoque de cadena de Markov . Boston, MA: Birkhäuser Boston. doi :10.1007/978-1-4612-0323-0. ISBN 978-1-4612-6707-2.
• Levin, David A.; Peres, Yuval (31 de octubre de 2017). Cadenas de Markov y tiempos de mezcla : segunda edición . Providence, Rhode Island: American Mathematical Soc. ISBN 978-1-4704-2962-1.
• Cheeger, Jeff (1971). "Un límite inferior para el valor propio más pequeño del laplaciano". Problemas en análisis: un simposio en honor a Salomon Bochner (PMS-31) . Princeton University Press. págs. 195-200. doi :10.1515/9781400869312-013. ISBN . 978-1-4008-6931-2.
• Diaconis, Persi; Stroock, Daniel (1991). "Límites geométricos para valores propios de cadenas de Markov". Anales de probabilidad aplicada . 1 (1). Instituto de Estadística Matemática: 36–61. ISSN  1050-5164. JSTOR  2959624 . Consultado el 14 de abril de 2024 .