Conductancia (gráfico) - Conductance (graph)

Ciencia de la red
Teoría
Grafico Red compleja Contagio Mundo pequeño Sin escamas 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 redes
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neural artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Corte Ciclo Estructura de datos Borde Círculo Vecindario Sendero Vértice Lista  / matriz de adyacencia Lista  / matriz de incidencia Tipos Bipartito Completo Dirigido Hiper Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad La licenciatura Motivo Agrupación Distribución de titulaciones Assortividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős – Rényi Barabási – Albert Modelo de fitness Watts – Strogatz Aleatorio exponencial (ERGM) Geométrico aleatorio (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Modelado de bloques Entropía máxima Configuración suave Benchmark LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorías
Temas Software Científicos de la red Categoría: Teoría de redes Categoría: Teoría de grafos
v t mi

Un gráfico G no dirigido y algunos cortes de ejemplo con las conductancias correspondientes

En teoría de grafos, la conductancia de un grafo G = ( V , E ) mide qué tan "bien entrelazado" está el gráfico: controla qué tan rápido un paseo aleatorio en G converge a su distribución estacionaria . La conductancia de un gráfico a menudo se denomina constante de Cheeger de un gráfico como análogo de su contraparte en geometría espectral . Dado que las redes eléctricas están íntimamente relacionadas con paseos aleatorios con una larga historia en el uso del término "conductancia", este nombre alternativo ayuda a evitar posibles confusiones.

La conductancia de un corte en un gráfico se define como: ${\ displaystyle (S, {\ bar {S}})}$

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

donde son las entradas de la matriz de adyacencia para G , de modo que ${\ Displaystyle a_ {ij}}$

${\ Displaystyle a (S) = \ sum _ {i \ in S} \ sum _ {j \ in V} a_ {ij}}$

es el número total (o peso) del incidente bordes con S . también se denomina volumen del conjunto . ${\ Displaystyle a (S)}$${\ Displaystyle S \ subseteq V}$

La conductancia de todo el gráfico es la conductancia mínima sobre todos los cortes posibles:

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

De manera equivalente, la conductancia de un gráfico se define de la siguiente manera:

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

Para un gráfico d -regular, la conductancia es igual al número isoperimétrico dividido por d .

Generalizaciones y aplicaciones

En aplicaciones prácticas, a menudo se considera la conductancia solo sobre un corte. Una generalización común de 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 la roca porosa se puede modelar en términos de la conductancia de un gráfico, con pesos dados por el tamaño de los poros.

La conductancia también ayuda a medir la calidad de un agrupamiento espectral . El máximo entre la conductancia de los conglomerados proporciona un límite que se puede utilizar, junto con el peso del borde entre los conglomerados, para definir una medida de la calidad del conglomerado. Intuitivamente, la conductancia de un grupo (que puede verse 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 grupo (llamada "conductancia interna").

Cadenas de Markov

Para una cadena de Markov ergódica reversible con un gráfico subyacente G , la conductancia es una forma de medir qué tan difícil es dejar 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 . Alistair Sinclair demostró que la conductancia está estrechamente relacionada con el tiempo de mezcla en cadenas de Markov ergódicas reversibles. También podemos ver la conductancia de una manera más probabilística, como la probabilidad mínima de dejar un pequeño conjunto de nodos dado que comenzamos en ese conjunto para empezar. Escribiendo para la probabilidad condicional de dejar un conjunto de nodos S dado que estábamos en ese conjunto para empezar, la conductancia es el mínimo sobre conjuntos que tienen una probabilidad estacionaria total de como máximo 1/2. ${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle S}$${\ Displaystyle \ Phi _ {S}}$${\ Displaystyle \ Phi _ {S}}$${\ Displaystyle S}$

La conductancia está relacionada con el tiempo de mezcla de la cadena de Markov en la configuración reversible.

Ver también

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

Referencias

• Béla Bollobás (1998). Teoría de grafos moderna . GTM . 184 . Springer-Verlag . pag. 321. ISBN 0-387-98488-7.
• Kannan, R .; Vempala, S .; Vetta, A. (mayo de 2004). "Sobre agrupaciones: bueno, malo y espectral" (PDF) . J. ACM . 51 (3): 497–515. doi : 10.1145 / 990308.990313 .
• Fan Chung (1997). Teoría del gráfico espectral . Notas de la conferencia del CBMS. 92 . Publicaciones AMS. pag. 212. ISBN 0-8218-0315-8.
• A. Sinclair. Algoritmos para generación y conteo aleatorios: un enfoque de cadena de Markov. Birkhauser, Boston-Basilea-Berlín, 1993.
• D. Levin, Y. Peres , EL Wilmer : Cadenas de Markov y tiempos de mezcla