Conduttanza (teoria dei grafi)

In teoria dei grafi, la conduttanza è una misura utilizzata per quantificare la qualità di un taglio e l'espansione dei grafi. Essa indica quanto un grafo sia "ben collegato" o, in alternativa, quanto presenti strozzature (bottleneck) che separano il grafo in sottostrutture scarsamente interconnesse. La conduttanza trova applicazioni in informatica teorica, nell'analisi delle reti e nello studio delle catene di Markov, in quanto fornisce indizi sulla velocità di convergenza dei processi stocastici ed è strettamente legata alle proprietà spettrali dei grafi.

Definizione

Sia ${\displaystyle G}$ un grafo ${\displaystyle d}$-regolare non diretto e con archi non pesati. La conduttanza ${\displaystyle \varphi (G)}$ è definita come ${\displaystyle \varphi (G)=h(G)/d}$, dove ${\displaystyle h(G)}$ è la .

Più in generale, sia ${\displaystyle G=\langle V,E\rangle }$ un grafo diretto con pesi reali ${\displaystyle a_{ij}\geq 0}$ su ciascun arco ${\displaystyle ij\in E}$. Sia ${\displaystyle S\subseteq V}$ in qualunque sottinsieme di vertici. La conduttanza ${\displaystyle \varphi (S)}$ del taglio ${\displaystyle (S,{\bar {S}})}$ è definita come

${\displaystyle \varphi (S)={\frac {\displaystyle a(S,{\bar {S}})}{\min(\mathrm {vol} (S),\mathrm {vol} ({\bar {S}}))}}\,,}$

dove

${\displaystyle a(S,T)=\sum _{i\in S}\sum _{j\in T}a_{ij}\,,}$

e quindi ${\displaystyle a(S,{\bar {S}})}$ è il peso totale degli archi attraversati dal taglio ${\displaystyle (S,{\bar {S}})}$ e

${\displaystyle \mathrm {vol} (S)=a(S,V)=\sum _{i\in S}\sum _{j\in V}a_{ij}}$

è il volume di ${\displaystyle S}$, ovvero, il peso totale di tutti gli archi che partono da ${\displaystyle S}$. Se ${\displaystyle \mathrm {vol} (S)}$ è uguale a ${\displaystyle 0}$, allora anche ${\displaystyle a(S,{\bar {S}})}$ è uguale ${\displaystyle 0}$ e ${\displaystyle \varphi (S)}$ vale ${\displaystyle 1}$ per definizione.

La conduttanza ${\displaystyle \varphi (G)}$ del grafo ${\displaystyle G}$ è quindi definita come la minima conduttanza tra tutti i possibili tagli:

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

In modo equivalente, la conduttanza soddisfa:

${\displaystyle \varphi (G)=\min \left\{{\frac {a(S,{\bar {S}})}{\mathrm {vol} (S)}}\;\colon \;{\mathrm {vol} (S)\leq {\frac {\mathrm {vol} (V)}{2}}}\right\}\,.}$

Bibliografia

• (EN) e , Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, ACM Press, 1988, DOI:10.1145/62212.62234, ISBN 978-0-89791-264-8.
• (EN) Bollobás Béla, Modern graph theory, GTM, vol. 184, Springer-Verlag, 1998, p. 321, ISBN 0-387-98488-7.
• (EN) Ravi Kannan, Santosh Vempala e Adrian Vetta, On clusterings: Good, bad and spectral, in Journal of the ACM, vol. 51, n. 3, 2004, pp. 497–515, DOI:10.1145/990308.990313, ISSN 0004-5411 (WC · ACNP).
• (EN) Fan R. K. Chung, Spectral Graph Theory, Providence (R. I.), American Mathematical Soc., 1997, ISBN 0-8218-0315-8.
• (EN) , Algorithms for Random Generation and Counting: A Markov Chain Approach, Boston, MA, Birkhäuser Boston, 1993, DOI:10.1007/978-1-4612-0323-0, ISBN 978-1-4612-6707-2.
• (EN) David A. Levin e Yuval Peres, : Second Edition, Providence, Rhode Island, American Mathematical Soc., 31 ottobre 2017, ISBN 978-1-4704-2962-1.
• (EN) Jeff Cheeger, A Lower Bound for the Smallest Eigenvalue of the Laplacian, in Problems in Analysis: A Symposium in Honor of Salomon Bochner (PMS-31), Princeton University Press, 1971, pp. 195–200, DOI:10.1515/9781400869312-013, ISBN 978-1-4008-6931-2.
• (EN) Persi Diaconis e Daniel Stroock, Geometric Bounds for Eigenvalues of Markov Chains, in The Annals of Applied Probability, vol. 1, n. 1, Institute of Mathematical Statistics, 1991, pp. 36–61, ISSN 10505164 (WC · ACNP), JSTOR 2959624. URL consultato il 14 aprile 2024.

Voci correlate

• Teoria della percolazione

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica