Conductancia (teoría de grafos)

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de red
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neurona artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Bucle Vecindario Camino Vértice Lista  / matriz de adyacencia Listado  / matriz de incidencias Tipos Bipartito Completo Dirigido Hiper Etiquetado Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad Grado Motivo Agrupamiento Distribución de grados Asortatividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős–Rényi Barabási–Albert Bianconi–Barabási Modelo de fitness Watts-Strogatz Aleatorio exponencial (ERGM) Geometría aleatoria (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Modelado de bloques Entropía máxima Configuración suave Punto de referencia LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorías
Temas Software Científicos de redes Categoría:Teoría de redes Categoría:Teoría de grafos
en a mi

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.

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.

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

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").

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 )}}$.

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