Проводимость (график) - Conductance (graph)

Неориентированный граф G и несколько примеров разрезов с соответствующими проводимостью

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

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

${displaystyle varphi (S)={frac {sum _{iin S,jin {ar {S}}}a_{ij}}{min(a(S),a({ar {S}}))}}}$

где ${displaystyle a_{ij}}$ записи матрица смежности за грамм, так что

${displaystyle a(S)=sum _{iin S}sum _{jin V}a_{ij}}$

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

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

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

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

${displaystyle phi (G):=min _{Ssubseteq V;0leq a(S)leq a(V)/2}{frac {sum _{iin S,jin {ar {S}}}a_{ij}}{a(S)}}.,}$

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

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

В практических приложениях часто учитывают проводимость только над разрезом. Обычное обобщение проводимости - рассмотрение случая весов, присвоенных ребрам: затем веса добавляются; если вес имеет форму сопротивления, то добавляются обратные веса.

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

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

Цепи Маркова

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

Поведение связано с Время перемешивания цепи Маркова в обратимой настройке.

Смотрите также

• Расстояние сопротивления
• Перколяция
• Коэффициент Кракхардта E / I

Рекомендации

• Béla Bollobás (1998). Современная теория графов. GTM. 184. Springer-Verlag. п. 321. ISBN  0-387-98488-7.
• Kannan, R .; Vempala, S .; Ветта, А. (май 2004 г.). «О кластеризации: хорошее, плохое и призрачное» (PDF). J. ACM. 51 (3): 497–515. Дои:10.1145/990308.990313.
• Фань Чанг (1997). Теория спектральных графов. Конспект лекций CBMS. 92. Публикации AMS. п. 212. ISBN  0-8218-0315-8.
• А. Синклер. Алгоритмы случайной генерации и подсчета: подход цепей Маркова. Биркхаузер, Бостон-Базель-Берлин, 1993.
• Д. Левин, Ю. Перес, Э. Л. Вильмер: Марковские цепи и времена перемешивания