Проводимость графа

Проводимость графа G=(V,E) — это измерение плотности графа, которое контролирует, насколько быстро случайное блуждание на G сходится к равномерному распределению. Проводимость графа часто называется константой Чигера графа как аналог его двойника в спектральной геометрии^[англ.]. Поскольку электрические цепи тесно связаны со случайными блужданиями и имеют длинную историю применения термина «проводимость», это альтернативное название помогает избежать возможную путаницу.

Проводимость разреза ${\displaystyle (S,{\bar {S}})}$ графа определяется как:

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

где ${\displaystyle a_{ij}}$ являются элементами матрицы смежности графа G, так что

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

является полным числом (или весом) рёбер, инцидентных S. Значение ${\displaystyle a(S)}$ также называется объёмом множества ${\displaystyle S\subseteq V}$.

Проводимость всего графа равна минимальной проводимости по всем возможным разрезам:

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

Эквивалентно, проводимость графа определяется следующим образом:

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

Для d-регулярного графа проводимость равна изопериметрическому числу, делённому на d.

Обобщения и приложения

В практических приложениях часто рассматривается проводимость только по разрезу. Частым обобщением проводимости является учёт весов, назначенных рёбрам — тогда складываются веса. Если веса употребляются в виде сопротивления, то складываются обратные весам величины.

Понятие проводимости подводит основу к перколяции в физике и другим областям. Тогда, например, проницаемость масла через поры камня можно моделировать в терминах проводимости графа с весами, заданными размерами пор.

Проводимость помогает также измерить качество спектральной кластеризации. Максимум проводимостей кластеров даёт границу, которая может быть использована вместе с весами внутри кластера для определения меры качества кластеризации. Интуитивно проводимость кластера (который можно рассматривать как множество вершин в графе) должна быть низкой. Кроме того, может также использоваться проводимость подграфа, порождённого кластером (называемая «внутренней проводимостью»).

Марковские цепи

Для эргодичной обратимой цепи Маркова с графом G, проводимость является способом измерения, насколько трудно покинуть малое множество узлов. Формально проводимость графа определяется как минимум по всем множествам ${\displaystyle S}$ ёмкости множества ${\displaystyle S}$, делённой на эргодический поток^[англ.] из ${\displaystyle S}$. Алистер Синклер показал, что проводимость тесно связана с временем смешивания^[англ.] в эргодичной обратимой цепи Маркова. Мы можем также рассматривать проводимость в более вероятностном смысле, как минимальную вероятность покинуть малый набор узлов, если мы начинаем из узла внутри этого множества. Обозначим через ${\displaystyle \Phi _{S}}$ условную вероятность покинуть множество узлов S, проводимость тогда равна минимальному ${\displaystyle \Phi _{S}}$ по всем множествам ${\displaystyle S}$, которые имеют полную стационарную вероятность, не превосходящую 1/2.

Проводимость связана с временем смешивания^[англ.] в обратимых условиях.

См. также

• Резистивное расстояние